Włamanie do Lexera

W programowaniu komputerowym hack lexer jest powszechnym rozwiązaniem problemów związanych z analizą ANSI C , ponieważ gramatyka odniesienia jest zależna od kontekstu . W C sklasyfikowanie sekwencji znaków jako nazwy zmiennej lub nazwy typu wymaga kontekstowej informacji o strukturze frazy, co uniemożliwia posiadanie leksykonu bezkontekstowego .

Problem

Problem polega na tym, że w poniższym kodzie klasy leksykalnej A nie można określić bez dalszych informacji kontekstowych:

 (  A  )  *  B

Ten kod może być mnożeniem dwóch zmiennych, w którym to przypadku A jest zmienną; napisane jednoznacznie:

   A  *  B

Alternatywnie może to być rzutowanie wyłuskanej wartości B na typ A , w którym to przypadku A jest nazwą typedef; napisane jednoznacznie:

  (  ZA  )  (  *  B  )

Bardziej szczegółowo, w kompilatorze leksykon wykonuje jeden z najwcześniejszych etapów konwersji kodu źródłowego na program. Skanuje tekst, aby wyodrębnić znaczące tokeny , takie jak słowa, liczby i ciągi znaków. Parser analizuje sekwencje tokenów próbując dopasować je do reguł składniowych reprezentujących struktury językowe, takie jak pętle i deklaracje zmiennych. Problem występuje tutaj, jeśli pojedyncza sekwencja tokenów może niejednoznacznie pasować do więcej niż jednej reguły składni.

Ta niejednoznaczność może się zdarzyć w C, jeśli leksykon nie rozróżnia identyfikatorów zmiennych i typedef . Na przykład w wyrażeniu C:

   (  A  )  *  B

Lekser może znaleźć te żetony:

lewy nawias
identyfikator „A”
prawy nawias
operator '*'
identyfikator „B”

Problem polega właśnie na tym, że klasy leksykalnej A nie można określić bez dalszego kontekstu: parser może to zinterpretować jako zmienną A pomnożoną przez B lub jako typ A rzutujący wyłuskaną wartość B . Jest to znane jako problem „typedef-name: identifier”, ze względu na nazwę problematycznej reguły produkcyjnej .

Rozwiązanie hakerskie

Rozwiązanie zasadniczo polega na wprowadzeniu informacji z tablicy symboli semantycznych z powrotem do leksera. Oznacza to, że zamiast działać jako czysty potok jednokierunkowy od leksera do parsera, istnieje kanał zwrotny z analizy semantycznej z powrotem do leksera. To mieszanie parsowania i analizy semantycznej jest ogólnie uważane za nieeleganckie, dlatego nazywa się je „hackowaniem ” .

Bez dodanego kontekstu leksykon nie może odróżnić identyfikatorów typu od innych identyfikatorów, ponieważ wszystkie identyfikatory mają ten sam format. W przypadku hacka w powyższym przykładzie, gdy leksyk znajdzie identyfikator A , powinien być w stanie sklasyfikować token jako identyfikator typu. Reguły języka zostałyby wyjaśnione poprzez określenie, że typy wymagają identyfikatora typu, a niejednoznaczność znika.

Problem występuje również w C++ , a parsery mogą używać tego samego hacka.

Alternatywne rozwiązania

Ten problem nie pojawia się (a zatem nie wymaga „hakowania” w celu rozwiązania) podczas korzystania z technik analizowania bez leksera , ponieważ są one wewnętrznie kontekstowe. Są one jednak ogólnie postrzegane jako mniej eleganckie projekty, ponieważ brakuje im modułowości posiadania równoczesnego leksera i parsera w potoku. ^{[ potrzebne źródło ]}

Niektóre generatory parserów, takie jak wywodzący się z byacc BtYacc („Backtracking Yacc”), dają wygenerowanemu parserowi możliwość podjęcia wielu prób przeanalizowania tokenów. W opisanym tutaj problemie, jeśli próba nie powiedzie się z powodu informacji semantycznych o identyfikatorze, może się wycofać i wypróbować inne reguły.

Parser Clang radzi sobie z sytuacją w zupełnie inny sposób, a mianowicie używając gramatyki leksykalnej bez odniesienia. Lekser Clanga nie próbuje rozróżniać nazw typów od nazw zmiennych: po prostu zgłasza bieżący token jako identyfikator. Następnie parser używa analizy semantycznej Clanga , aby określić naturę identyfikatora. Pozwala to na znacznie czystsze oddzielenie obaw i enkapsulacji leksera i parsera, dlatego niektórzy twórcy kompilatorów uważają go za znacznie bardziej eleganckie rozwiązanie niż The Lexer Hack. Jest to również podejście stosowane w większości innych współczesnych języków, które nie rozróżniają różnych klas identyfikatorów w gramatyce leksykalnej, ale zamiast tego odkładają je do fazy analizy składniowej lub analizy semantycznej, gdy dostępne są wystarczające informacje. ^{[ potrzebny przykład ]}

Zobacz też

Wiszące inaczej

Cytaty