Szukasz jasnej definicji tego, czym są „tokenizer”, „parser” i „leksery” oraz w jaki sposób są one ze sobą powiązane i używane?

151

Szukam jasnej definicji tego, czym są „tokenizer”, „parser” i „lexer” i jak są one ze sobą powiązane (np. Czy parser używa tokenizera lub odwrotnie)? Muszę utworzyć program, który przejdzie przez pliki źródłowe c / h, aby wyodrębnić deklarację danych i definicje.

Szukałem przykładów i mogę znaleźć trochę informacji, ale naprawdę staram się zrozumieć podstawowe pojęcia, takie jak reguły gramatyczne, drzewa parsowania i abstrakcyjne drzewo składniowe oraz ich wzajemne powiązania. Ostatecznie koncepcje te muszą zostać zapisane w rzeczywistym programie, ale 1) jak one wyglądają, 2) czy istnieją wspólne implementacje.

Patrzyłem na Wikipedię na te tematy i programy, takie jak Lex i Yacc, ale ponieważ nigdy nie przeszedłem przez klasę kompilatora (kierunek EE), trudno mi w pełni zrozumieć, co się dzieje.

parsing lexer tokenize Lordhog
źródło

Odpowiedzi:

166

Tokenizer dzieli strumień tekstu na tokeny, zwykle szukając białych znaków (tabulatory, spacje, nowe wiersze).

Lekser jest w zasadzie tokenizerem, ale zwykle dołącza dodatkowy kontekst do tokenów - ten token jest liczbą, ten token jest literałem ciągu, ten drugi token jest operatorem równości.

Parser pobiera strumień tokenów z leksera i przekształca go w abstrakcyjne drzewo składniowe reprezentujące (zwykle) program reprezentowany przez oryginalny tekst.

Kiedy ostatnio sprawdzałem, najlepszą książką na ten temat była „Kompilatory: zasady, techniki i narzędzia”, zwykle nazywana po prostu „Smoczą księgą”.

Roger Lipscombe
źródło
8
Bez wątpienia „The Dragon Book” to dobra książka, ale wymaga od czytelnika dobrego uziemienia w CS. Bardziej praktyczna książka to „Writing Compilers and Interpreters” Ronalda Maka, „Modern Compiler Implementation”, Andrew Appel; „Budowa kompilatora”, Niklaus Wirth; „Kompilowanie z C # i Javą” oraz „Kompilatory i generatory kompilatorów: wprowadzenie w C ++” autorstwa Pat Terry; i oczywiście „The Definitive ANTLR Reference” Terrence'a Parra.
Andre Artus
5
Dla pewności nie odrzucam twojej rekomendacji. „The Dragon Book” była moją pierwszą książką o technologii kompilatorów, ale była ciężka w porównaniu z, powiedzmy, książką Wirtha, którą można przeczytać w kilka godzin. Wtedy miałem kilka opcji, ponieważ była to jedyna książka, jaką mogłem dostać (był rok 1991, przed Amazon i WWW). Miałem to i kolekcję plików tekstowych wyprodukowanych przez Jacka W. Crenshawa pod tytułem „ZBUDUJEMY KOMPILER” (dzięki Jack!). Nadal jest to książka, w której można uzyskać pełniejsze zrozumienie zasad, ale większość programistów potrzebuje jedynie pragmatycznego wprowadzenia.
Andre Artus
10
Nie zgodziłbym się, że parser / z definicji / tworzy abstrakcyjne drzewo składni. Parsery mogą generować wiele różnych wyników. Na przykład często zdarza się, że parser tworzy sekwencję wywołań do interfejsu konstruktora - zobacz wzorzec konstruktora w książce Gang of Four patterns. Kluczową kwestią jest to, że parser analizuje sekwencję tokenów, aby określić, czy sekwencja jest zgodna z jakąś (zwykle bezkontekstową) gramatyką i może wygenerować pewne dane wyjściowe w oparciu o strukturę gramatyczną sekwencji.
Theodore Norvell
2
„Zbudujmy kompilator” jest tutaj: compilers.iecc.com/crenshaw . Odnalazłem link stąd: prog21.dadgum.com/30.html
Roger Lipscombe
1
@Pithkos: jeśli to są jedyne ograniczenia, wszystko, co powiedziałeś, to to, że funkcja pobiera dane wejściowe z jednej nienazwanej (matematycznej) domeny i produkuje i wyprowadza w innej nienazwanej domenie, np. F (X) -> Y Prawie to oznacza możesz to nazwać tylko „funkcją”. Jeśli upierasz się, że domeną X jest <StreamOfCharacter, Grammar>, a domeną Y jest Drzewo z tą właściwością, że odzwierciedla kształt gramatyki, to F (X, G) -> T byłoby czymś, co nazwałbym a parser. Często curry F w odniesieniu do G, ponieważ G nie zmienia się często, więc F [G] (X) -> T jest tym, co zwykle postrzegasz jako parser.
Ira Baxter
18

Przykład:

int x = 1;

Lekser lub tokeniser podzieli to na tokeny „int”, „x”, „=”, „1”, „;”.

Parser weźmie te tokeny i użyje ich do zrozumienia w jakiś sposób:

  • mamy oświadczenie
  • jest to definicja liczby całkowitej
  • liczba całkowita nazywa się „x”
  • „x” należy zainicjować wartością 1
Gra
źródło
9
Lekser zauważy, że „int”, „=” i „;” to tokeny bez dalszego znaczenia, że ​​„x” to nazwa identyfikatora lub coś w tym stylu, wartość „x”, a „1” to liczba całkowita lub liczba, wartość „1”. Tokenizer niekoniecznie to zrobi.
David Thornley
5

Powiedziałbym, że lekser i tokenizer to w zasadzie to samo i rozbijają tekst na części składowe („tokeny”). Następnie parser interpretuje tokeny za pomocą gramatyki.

Nie przejmowałbym się jednak zbytnio precyzyjnym użyciem terminologii - ludzie często używają „parsowania” do opisania jakiejkolwiek czynności polegającej na interpretacji fragmentu tekstu.

Will Dean
źródło
1
W przypadku parserów PEG różnica między tokenizatorem a parserem jest jeszcze mniej jasna.
Andre Artus
0

( dodawanie do podanych odpowiedzi )

  • Tokenizer usunie również wszelkie komentarze i zwróci tokeny tylko do Lexera.
  • Lexer zdefiniuje również zakresy dla tych tokenów (zmiennych / funkcji)
  • Parser następnie zbuduje strukturę kodu / programu
mcha
źródło
1
Witaj @downvoter, czy możesz wyjaśnić, dlaczego tak naprawdę zagłosowałeś przeciw?
Koray Tugay
1
Nie jestem przeciwnikiem, ale myślę, że głos przeciwny mógł wynikać z tego, że twoja odpowiedź nie wydaje się poprawna. Tokenizer może usuwać szum (zazwyczaj spacje, ale może także komentarze), ale często nie zasila leksera. Lekser oparty na DFA będzie tokenizować i identyfikować, jakie są tokeny (np. Liczba, ciąg znaków, identyfikator, ale także odstępy lub komentarz), ale nie może ich określać, ponieważ wymagałoby to drzewa składni, które jest później budowane przez parser.
Lucero
1) Nie rozumiem twojej wyraźnej różnicy między „lexer” a „tokenizer”. Zbudowałem parsery dla ponad 50 języków i nigdy nie miałem dwóch oddzielnych mechanizmów, które rozbijają tekst źródłowy na atomy, więc dla mnie to tylko synonimy. 2) Jeśli kompilujesz, usuwanie komentarzy i białych znaków ma sens w lekserze. Jeśli tworzysz narzędzia do przekształcania ze źródła do źródła, nie możesz utracić komentarzy, ponieważ muszą one ponownie pojawić się w przekształconym tekście. Dlatego ZAWSZE usuwanie komentarzy jest złe; możemy dyskutować o tym, jak udaje się zachować białe znaki. ...
Ira Baxter
1
... [Narzędzia, które buduję (zobacz moją biografię) wychwytują oba z odpowiednią wiernością, aby odtworzyć je w przekształconym kodzie; idziemy dalej i wychwytujemy format atomów, w tym dziwne rzeczy, takie jak cudzysłowy używane w ciągach znaków i podstawa / wiodące zero licznika, a wszystko to w celu uniknięcia odrzucenia przekształconego wyniku przez użytkownika. Więc to, co przeoczyłeś, to nie tylko to, że leksykacze niekoniecznie usuwają informacje, ale w rzeczywistości mogą potrzebować przechwycić informacje wykraczające poza surowy token]. ....
Ira Baxter
... 3) Leksery definiują „zakresy” tylko w beznadziejnie niezręcznych parserach, które mają trudności z obsługą niejednoznaczności składniowych. Parsery C i C ++ to kanoniczny przykład; zobacz moją dyskusję na stackoverflow.com/a/1004737/120163 ). Nie trzeba tego robić w ten (brzydki) sposób. Więc uważam, że twoja odpowiedź jest po prostu błędna.
Ira Baxter