W jakim procesie występuje błąd składniowy? (tokenizacja lub parsowanie)

23

Próbuję zrozumieć kompilację i interpretację, krok po kroku, zastanawiając się nad całkowitym obrazem. Podszedłem więc do pytania podczas czytania http://www.cs.man.ac.uk/~pjj/farrell/comp3.html tego artykułu

To mówi :

Kolejny etap kompilatora nosi nazwę Parser. Ta część kompilatora rozumie gramatykę języka. Odpowiada za identyfikację błędów składniowych i tłumaczenie bezbłędnego programu na wewnętrzne struktury danych, które można interpretować lub zapisywać w innym języku.

Ale nie mogłem rozgryźć, w jaki sposób tokenizer może poprawnie tokenizować dany strumień, który zawiera błąd składniowy.

Powinien się tam utknąć lub przekazać parserowi błędne informacje. To znaczy, czy tokenizacja nie jest też rodzajem tłumacza?

Jak więc przezwyciężyć leksykalne, uszkodzone linie kodu podczas tokenizacji.

W powyższym linku znajduje się przykład tokena w nagłówku Tokenizera .

Rozumiem, że forma tokena wygląda na to, że jeśli coś jest nie tak z tokenem kodu, to również zostanie uszkodzony.

Czy mógłbyś wyjaśnić moje nieporozumienie?

FZE
źródło

Odpowiedzi:

32

Tokenizer to tylko optymalizacja parsera. Zupełnie możliwe jest wdrożenie parsera bez tokenizera.

Tokenizer (lub leksykon lub skaner) dzieli dane wejściowe na listę tokenów. Niektóre części ciągu (komentarze, białe znaki) są zwykle ignorowane. Każdy token ma typ (znaczenie tego ciągu w języku) i wartość (ciąg, który składa się na token). Na przykład fragment kodu źródłowego PHP

$a + $b

mogą być reprezentowane przez tokeny

Variable('$a'),
Plus('+'),
Variable('$b')

Tokenizer nie rozważa, czy token jest możliwy w tym kontekście. Na przykład dane wejściowe

$a $b + +

z przyjemnością wygenerowałby strumień tokenu

Variable('$a'),
Variable('$b'),
Plus('+'),
Plus('+')

Gdy parser zużyje następnie te tokeny, zauważy, że dwie zmienne nie mogą podążać za sobą, podobnie jak dwóch operatorów infix. (Należy pamiętać, że inne języki mają różne składnie, w których taki strumień tokenów może być legalny, ale nie w PHP).

Analizator składni może nadal zawieść na etapie tokenizera. Na przykład może występować niedozwolony znak:

$a × ½ — 3

Tokenizer PHP nie byłby w stanie dopasować tych danych wejściowych do swoich reguł i spowodowałby błąd przed rozpoczęciem głównej analizy.

Bardziej formalnie, tokenizery są używane, gdy każdy token można opisać jako zwykły język . Tokeny można następnie dopasować niezwykle wydajnie, być może zaimplementować jako DFA. Natomiast główna gramatyka jest zwykle pozbawiona kontekstu i wymaga bardziej skomplikowanego, mniej wydajnego algorytmu analizowania, takiego jak LALR.

amon
źródło
Moglibyśmy więc pomyśleć, że tokenizer jest częścią parsera, a błąd składniowy może wystąpić albo krok tokenizujący, albo etap parsowania zgodnie z formularzem błędu składniowego. Dziękuję za wyjaśnienie.
FZE,
4
@FZE: Możesz tak myśleć, ale jest to mylące. Lexing to nie tylko „optymalizacja parsera”. Zamiast tego leksykowanie odwzorowuje fizyczną reprezentację (pewną sekwencję znaków) na logiczną reprezentację (tokeny reprezentowane przez te postacie). To izoluje od drobiazgach jak parser jak koniec linii jest reprezentowana, czy zdecydujesz się stanowią logiczną-a jak andlub &&czy coś innego. Jest (głównie) osobny i różni się od parsowania. Optymalizacja (jeśli występuje) jest prawie przypadkowym efektem ubocznym.
Jerry Coffin
@JerryCoffin dzięki za dalsze wyjaśnienia, które mają teraz większy sens.
FZE,
2
@JerryCoffin, amon ma rację, to znaczy różnica nie jest fundamentalna. Możesz stworzyć spójną gramatykę BNF, która obejmuje zarówno części „leksykon”, jak i „parser”. Zazwyczaj dzielimy reguły na niski poziom (np. Liczba, operator dodawania) i wysoki poziom (sumowanie), ale sama gramatyka nie czyni takiego rozróżnienia.
Paul Draper,
1
@PaulDraper Nie jestem pewien, czy oddzielenie zwykłego języka jako pierwszej fazy jest właściwym wyborem. Na przykład pasujące pary (nieregularne) mogą być konieczne do opisania literałów łańcuchowych w niektórych językach, ale nadal warto je obsługiwać w pierwszej fazie. Unikanie / minimalizowanie śledzenia wstecznego wydaje się lepszą wytyczną.
CodesInChaos
16

Którą zwykle oczekiwać większość błędów składni, aby przyjść z parsera, a nie Lexer.

Lexer wygeneruje błąd, jeśli (i głównie tylko wtedy), jeśli na wejściu jest coś, czego nie można tokenizować. Jednak w wielu językach prawie każda sekwencja znaków może być zamieniona na tokeny, więc błędy tutaj są dość niezwykłe.

Analizator składni wygeneruje błąd, jeśli dane wejściowe zawierają prawidłowe tokeny, ale te tokeny nie są ułożone, więc tworzą prawidłowe instrukcje / wyrażenia w języku docelowym. Z reguły jest to o wiele bardziej powszechne.

Jerry Coffin
źródło
11

Tokenizer dzieli tylko strumień znaków na tokeny. Z tokenizera POV jest to całkowicie poprawne:

1 * * 1

i tłumaczy się na coś takiego: ["1", MULTIPLY, MULTIPLY, "1"] Tylko parser może odrzucić takie wyrażenia - wie, że operator mnożenia nie może podążać za innym operatorem mnożenia. Na przykład w JavaScript daje to:

Uncaught SyntaxError: Unexpected token *(…)

Istnieją błędy, które mogą zostać wykryte przez tokenizer. Dla przykładu: niedokończone literały ciągów znaków "abclub nieprawidłowe numery: 0x0abcdefg. Nadal mogą być zgłaszane jako błędy składniowe:

Uncaught SyntaxError: Unexpected token ILLEGAL

Należy jednak pamiętać, że token nie został rozpoznany i jest zgłaszany jako ILLEGAL.

Banthar
źródło