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

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