Lexer Hack - The lexer hack

W programowania , lexer siekać (w przeciwieństwie do „lexer hak”) opisuje wspólnego rozwiązania dla problemów występujących podczas analizowania ANSI C , w wyniku odniesienia gramatyki będącego kontekstową. W C, klasyfikowanie ciąg znaków w postaci zmiennych lub nazwa typu wymaga kontekstowe informacje o strukturze frazy, która powstrzymuje jedną z konieczności bezkontekstowych lexer .

Problem

Problem polega na tym, że w poniższym kodzie leksykalny klasa Anie może być określona bez dalszych informacji kontekstowych: 

(A)*B

Kod ten może być mnożenie dwóch zmiennych, w tym przypadku Ajest to zmienna; napisane jednoznacznie: 

A * B

Alternatywnie, może to być odlewania dereferencjonowane wartość Bod typu A, w tym przypadku Ajest nazwą typedef; napisane jednoznacznie: 

(A) (*B)

Bardziej szczegółowo, w kompilatorze , lexer wykonuje jeden z najwcześniejszych etapów przekształcania kodu źródłowego do programu. Skanuje tekst wyciągnąć sensowne znaki , takie jak słów, liczb i łańcuchów. Parser analizuje sekwencje tokenów próbujących dopasować je do reguł składniowych reprezentujących struktur językowych, takich jak pętle i deklaracji zmiennych. Problem pojawia się tutaj, jeśli pojedyncza sekwencja żetonów może niejednoznacznie dopasować więcej niż jedną regułę składni.

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

(A) * B

lexer mogą znaleźć te znaki:

  1. lewy nawias
  2. Identyfikator „A”
  3. prawy nawias
  4. Operator '*'
  5. Identyfikator „B”

Problemem jest to, że właśnie słownikowa klasa A nie może być określona bez dalszego kontekstu: parser można zinterpretować jako zmiennej A pomnożonej przez B lub typu A odlewu dereferencjonowane wartości B . Jest to znane jako „typedef-name: identyfikator” problem, ze względu na imię problematycznego reguły produkcji .

Rozwiązanie Hack

Rozwiązanie polega na ogół podawanie informacji z semantycznej tablicy symboli z powrotem do lexer. Oznacza to, że zamiast funkcjonować jako czysta jednokierunkowej rurociągu z lexer do parsera, jest osobnym kanale z analizy semantycznej powrotem do lexer. To mieszanie parsowania i analizy semantycznej jest powszechnie uważany za nieeleganckie, dlatego nazywany jest „hack”.

Bez dodatku kontekście lexer nie można odróżnić od innych identyfikatorów typu identyfikatorów ponieważ wszystkie identyfikatory mają ten sam format. Z hack w powyższym przykładzie, kiedy lexer odnajduje identyfikator A powinien móc klasyfikować token jako identyfikator typu. Reguły języka byłoby wyjaśnić poprzez określenie, że typecasts wymaga identyfikatora typu i dwuznaczność znika.

Problem występuje również w C ++ i parser może korzystać z tego samego siekać.

Alternatywne rozwiązania

Ten problem nie występuje (a więc nie potrzebuje „hack” w celu rozwiązania) przy użyciu lexerless analizowania techniki, ponieważ są nierozerwalnie kontekstowe. Są to na ogół postrzegane jako mniej eleganckich wzorów, jednak ze względu na brak modularność o współbieżne lexer i analizatora składni w rurociągu.

Niektóre generatory parser, takie jak yacc pochodzące z A BtYacc ( „Backtracking Yacc”), dać generowanego analizatora możliwość wypróbowania wielu prób analizowania tokenów. W problem opisany tutaj, jeśli próba nie powiedzie się z powodu semantycznej informacji na temat identyfikatora, może wracać i próbować innych reguł.

Clang parser obsługuje sytuacja zupełnie inny sposób, a mianowicie za pomocą gramatyki Niereferencyjne leksykalny. Lexer dzyń za nie próbuje odróżnić nazw typów i nazw zmiennych: to po prostu informuje bieżącego tokenu jako identyfikator. Parser następnie wykorzystuje dzyń za analizy semantycznej biblioteki w celu określenia charakteru identyfikatora. Pozwala to znacznie czystsze separacji obawy i hermetyzacji w lexer i analizatora i dlatego jest uważany za znacznie bardziej eleganckie rozwiązanie niż Lexer Hack przez większość nowoczesnych metryk projektowania oprogramowania. Jest to również podejście stosowane w większości innych języków nowożytnych, które nie rozróżniają różne klasy identyfikatorów w gramatyce leksykalnym, ale zamiast odroczenia ich do analizowania lub semantycznej fazie analizy, gdy dostępne są informacje.

Zobacz też

Referencje

cytowania