lexers vs parsers

Tak, są one bardzo różne w teorii i w realizacji.

Leksery są używane do rozpoznawania "słów" składających się na elementy języka, ponieważ struktura takich słów jest na ogół prosta. Wyrażenia regularne są bardzo dobre w obsłudze tej prostszej struktury i istnieją bardzo wydajne silniki dopasowujące wyrażenia regularne używane do implementacji lexerów.

Parsery są używane do rozpoznawania "struktury" fraz językowych. Taka struktura jest generalnie daleko poza jakie" wyrażenia regularne " potrafią rozpoznać, więc trzeba parsery "wrażliwe na kontekst" do wyodrębniania takiej struktury. Parsery kontekstowe są trudne do zbudowania, więc kompromisem inżynierskim jest użycie" bezkontekstowych " gramatyk i dodać hacki do parserów ("tabele symboli", itp.) do obsługi części kontekstowej.

Ani technologia lexingu, ani parsingu prawdopodobnie wkrótce odejdzie.

Onemogą być zunifikowane, decydując się na użycie technologii "parsowania" do rozpoznawania "słów", jak to obecnie badany przez tzw. scannerless GLR parsery. To ma koszt wykonania, ponieważ stosujesz bardziej ogólne Maszyny do tego, co często jest problemem, który go nie potrzebuje, i zwykle płacisz za to w kosztach ogólnych. Tam, gdzie masz dużo darmowych cykli, które mogą nie mieć znaczenia. Jeśli przetwarzasz dużo tekstu, to narzut ma znaczenie i klasyczne parsery wyrażeń regularnych będą nadal używane.

Kiedy Lex wystarczy, kiedy potrzebujesz EBNF?

EBNF naprawdę niewiele dodaje do mocy gramatyk. To tylko wygoda / zapis skrócony / "cukier składniowy" ponad standardowymi regułami gramatyki postaci normalnej Chomsky ' ego (CNF). Na przykład alternatywa EBNF:

S --> A | B

S --> A      // `S` can be `A`,
S --> B      // or it can be `B`.

Opcjonalny element z EBNF:

S --> X?

Ty można osiągnąć w CNF używając nullable produkcji, czyli takiej, którą można zastąpić pustym ciągiem (oznaczonym tutaj tylko pustą produkcją; inni używają epsilon lub lambda lub skrzyżowanego okręgu):

S --> B       // `S` can be `B`,
B --> X       // and `B` can be just `X`,
B -->         // or it can be empty.

Produkcja w takiej formie jak ta ostatnia B powyżej nazywa się "erasure", ponieważ może wymazać to, co oznacza w innych produkcjach (wytworzyć pusty ciąg zamiast czegoś innego).

Zero-lub-więcej powtórzeń z EBNF:

S --> A*

Możesz obtan używając rekurencyjnej produkcji, czyli takiej, która osadza się gdzieś w niej. Można to zrobić na dwa sposoby. Pierwsza z nich to left recursion (której zwykle należy unikać, ponieważ odgórne parsery rekurencyjne nie mogą tego analizować):

S --> S A    // `S` is just itself ended with `A` (which can be done many times),
S -->        // or it can begin with empty-string, which stops the recursion.

Wiedząc, że generuje tylko pusty łańcuch (ostatecznie), po którym następuje zero lub więcej As, ten sam łańcuch (, ale nie ten sam język!) można wyrazić za pomocą prawo-rekurencja :

S --> A S    // `S` can be `A` followed by itself (which can be done many times),
S -->        // or it can be just empty-string end, which stops the recursion.

A jeśli chodzi o + jedno-lub-więcej powtórzeń z EBNF:

S --> A+

S --> A A*

, które możesz wyrazić w CNF jako takie (używam tutaj właściwej rekurencji; spróbuj sam obliczyć drugą jako ćwiczenie):

S --> A S   // `S` can be one `A` followed by `S` (which stands for more `A`s),
S --> A     // or it could be just one single `A`.

Wiedząc o tym, możesz teraz prawdopodobnie rozpoznać gramatykę dla wyrażenia regularnego (to jest gramatyka regularna) jako jeden które mogą być wyrażone w pojedynczej produkcji EBNF składającej się wyłącznie z symboli terminali. Ogólnie rzecz biorąc, można rozpoznać zwykłe gramatyki, gdy widzisz produkcje podobne do tych:]}

A -->        // Empty (nullable) production (AKA erasure).
B --> x      // Single terminal symbol.
C --> y D    // Simple state change from `C` to `D` when seeing input `y`.
E --> F z    // Simple state change from `E` to `F` when seeing input `z`.
G --> G u    // Left recursion.
H --> v H    // Right recursion.

To znaczy, używając tylko pustych łańcuchów, symboli terminali, prostych Nie-terminali dla podstawień i zmian stanu, i używając rekursji tylko do uzyskania powtórzeń(iteracja, która jest po prostu rekursją liniową - tą, która nie rozgałęzia się jak drzewo). Nic bardziej zaawansowanego ponad te, wtedy jesteś pewien, że to zwykła składnia i możesz użyć tylko lexera do tego.

Ale kiedy twoja składnia używa rekurencji w nietrywialny sposób, aby stworzyć podobne do drzewa, podobne do siebie, zagnieżdżone struktury, takie jak następująca: {]}

S --> a S b    // `S` can be itself "parenthesized" by `a` and `b` on both sides.
S -->          // or it could be (ultimately) empty, which ends recursion.

Wtedy łatwo widać, że nie można tego zrobić za pomocą wyrażenia regularnego, ponieważ nie można go w żaden sposób rozwiązać w jedną produkcję EBNF; skończysz z zastąpieniem S w nieskończoność, co zawsze doda kolejne ai bs po obu stronach. Lexery (dokładniej: automaty skończone używane przez lexerów) nie mogą liczyć do dowolnej liczby (są skończone, pamiętacie?nie wiedzą więc, ile aS było tam, aby równomiernie dopasować je do tak wielu bs. gramatyki takie nazywane są gramatykami bezkontekstowymi (przynajmniej) i wymagają parsera.

Gramatyki Bezkontekstowe są dobrze znane do analizy, więc są szeroko stosowane do opisu składni języków programowania. Ale jest więcej. Czasami potrzebna jest bardziej ogólna gramatyka - gdy masz więcej rzeczy do policzenia w tym samym czasie, niezależnie. Na przykład, gdy chcemy opisać język, w którym można używać okrągłych nawiasów i kwadratowych aparatów ortodontycznych przeplatanych, ale muszą one być ze sobą prawidłowo sparowane(Aparat ortodontyczny z aparatami ortodontycznymi, okrągły z okrągłym). Ten rodzaj gramatyki nazywa się context-sensitive . Można go rozpoznać po tym, że ma więcej niż jeden symbol po lewej stronie(przed strzałką). Na przykład:

A R B --> A S B

Możesz myśleć o tych dodatkowych symbolach po lewej stronie jako o "kontekście" stosowania reguły. Mogą istnieć pewne warunki wstępne, warunki pocztowe itp. Na przykład powyższa reguła zastąpi R na S, ale tylko wtedy, gdy znajduje się pomiędzy A a B, pozostawiając te A i B same w sobie bez zmian. Ten rodzaj składni jest naprawdę trudny do przeanalizowania, ponieważ potrzebuje pełnowymiarowej maszyny Turinga. To zupełnie inna historia, więc skończę tutaj.

Odpowiedzieć na zadane pytanie (bez zbędnego powtarzania tego, co pojawia się w inne odpowiedzi)

Lexery i parsery nie różnią się zbytnio, jak sugeruje akceptuję odpowiedź. Oba oparte są na prostych formalizmach językowych: regularne języki dla lexerów i, prawie zawsze, języki bezkontekstowe (CF) dla parserów. Oba są związane z dość prostymi obliczeniowymi modele, automat skończonego stanu i automat stosu push-down. Języki regularne są szczególnym przypadkiem języki bez kontekstu, więc że lexery mogą być produkowane z nieco bardziej złożonym CF technologia. Ale to nie jest dobry pomysł z przynajmniej dwóch powodów.

Podstawowym punktem w programowaniu jest to, że komponent systemu powinien być buit z najbardziej odpowiednią technologią, dzięki czemu jest łatwy do produkować, rozumieć i utrzymywać. Technologia nie powinna być overkill (przy użyciu technik znacznie bardziej złożonych i kosztownych niż jest to konieczne), nie powinno też być na granicy swojej mocy, tym samym wymagając technicznych kontorcje do osiągnięcia pożądanego celu.

Dlatego "modne wydaje się nienawidzić wyrażeń regularnych". Choć mogą zrobić wiele, czasami wymagają bardzo nieczytelne kodowanie, aby go osiągnąć, nie wspominając o tym, że różne rozszerzenia i ograniczenia we wdrażaniu nieco ograniczają ich teoretyczne prostota. Leksery zazwyczaj tego nie robią i są zwykle prostym, wydajna i odpowiednia technologia do analizy tokena. Używanie parserów CF dla tokena byłoby przesadą, choć jest to możliwe.

Innym powodem nie używania formalizmu CF dla lexerów jest to, że może następnie bądź kuszący, aby użyć pełnej mocy CF. Ale to może podnieść problemy z czytaniem programów.

Zasadniczo większość struktury tekstu programu, z którego znaczenie jest wyodrębnione, jest strukturą drzewa. Wyraża sposób parsowania zdanie (program) jest generowane z reguł składni. Semantyka to pochodzące z technik kompozytorskich (homomorfizm na zorientowanych matematycznie) od sposobu komponowania reguł składniowych do zbuduj drzewo parsowania. Dlatego struktura drzewa jest niezbędna. Fakt, że tokeny są identyfikowane z prostownikiem opartym na regularnym zbiorze nie zmienia sytuacji, bo CF składa się z regularnych jeszcze daje CF (mówię bardzo luźno o zwykłych przetwornikach, że przekształcić strumień znaków w strumień tokenu).

Jednak CF składa się z CF (poprzez przetworniki CF ... przepraszam za matematyka), nie koniecznie daj CF, a może sprawi, że będzie więcej ogólne, ale mniej tractable w praktyce. Więc CF nie jest odpowiedni narzędzie do lexerów, mimo że można z niego korzystać.

Jedną z głównych różnic między regular A CF jest to, że regular Języki (i przetworniki) komponują się bardzo dobrze z niemal każdym formalizmu na różne sposoby, podczas gdy języki CF (i przetworniki) robią Nie, nawet ze sobą (z kilkoma wyjątkami).

(zauważ, że zwykłe przetworniki mogą mieć inne zastosowania, takie jak formalizacja niektórych technik obsługi błędów składni.)

BNF jest tylko specyficzną składnią do prezentacji gramatyk CF.

EBNF jest cukrem składniowym dla BNF , wykorzystującym funkcje zwykłego notacja dająca terserową wersję gramatyki BNF. Zawsze może być przekształcony w odpowiednik czystego BNF.

Jednak regularna notacja jest często używana w EBNF tylko po to, aby podkreślić te części składni, które odpowiadają strukturze leksykalnej elementy, i powinny być rozpoznawane z lekerem, podczas gdy reszta z być raczej przedstawione w prosty BNF. Ale to nie jest absolutna zasada.

Podsumowując, prostsza struktura tokena jest lepiej analizowana za pomocą prostszej technologii języków regularnych, natomiast drzewo zorientowane struktura języka (składni programu) jest lepiej obsługiwana przez CF grammars.

Proponuję również przyjrzeć się odpowiedzi AHR .

Ale to pozostawia pytanie otwarte: Dlaczego drzewa?

Drzewa są dobrą podstawą do określenia składni, ponieważ

• Nadają tekstowi prostą strukturę

• Są bardzo wygodne do kojarzenia semantyki z tekstem na podstawie tej struktury, z matematycznie dobrze rozumianej technologii (kompozycja poprzez homomorfizmy), jako wskazane powyżej. Jest podstawowym narzędziem algebraicznym do definiowania semantyka formalizmów matematycznych.

Stąd jest to dobry reprezentacji pośredniej, jak wynika z sukces abstrakcyjnych drzew składniowych (AST). Należy pamiętać, że AST są często różni się od drzewa parsowania, ponieważ technologia parsowania używana przez wielu professionals (np. LL lub LR) dotyczy tylko podzbioru CF gramatyki, wymuszając tym samym zniekształcenia gramatyczne, które później poprawiono w AST. Można tego uniknąć przy bardziej ogólnym parsowaniu technologia (oparta na programowaniu dynamicznym) akceptująca dowolną gramatykę CF.

Stwierdzenie o tym, że programowanie językami są context-sensitive (CS) zamiast CF są arbitralne i dyskusyjne.

Problem polega na tym, że rozdzielenie składni i semantyki jest / align = "left" / Deklaracje sprawdzające lub umowy typu mogą być postrzegane jako albo część składni, albo część semantyki. To samo dotyczy Umowa o płci i liczbie w językach naturalnych. Ale są naturalne języki, w których liczba mnoga zależy od rzeczywistej semantyki znaczenie słów, tak aby nie pasowało ono dobrze do składnia.

Wiele definicji języków programowania w semantyce denotacyjnej umieść deklaracje i sprawdzanie typu w semantyce. Więc stwierdzając jako done by Ira Baxter że parsery CF są hackowane, aby uzyskać kontekst czułość wymagana przez składnię jest co najwyżej arbitralnym widokiem sytuacja. Może być zorganizowany jako hack w niektórych kompilatorach, ale nie musi być.

Również nie chodzi tylko o to, że parsery CS (w sensie używanym w innych odpowiedziach tutaj) są trudne do budować i mniej wydajny. Są również niewystarczające do wyraźnego wyrażania kinf wrażliwości kontekstowej, która może być potrzebna. A oni nie naturalnie tworzą strukturę składniową (np. parse-trees), która jest wygodny do wyprowadzania semantyki programu, tzn. do generowania skompilowany kod.

Istnieje wiele powodów, dla których część analizy kompilatora jest zwykle podzielone na fazy analizy leksykalnej i analizy składniowej.

1. prostota projektowania jest najważniejsza. Rozdzielenie analizy leksykalnej i składniowej często pozwala uprościć przynajmniej jedno z tych zadań. Na przykład parser, który musiał radzić sobie z komentarzami i białymi spacjami jako jednostkami składni. Znacznie bardziej złożony niż ten, który może Załóżmy, że komentarze i białe spacje zostały już usunięte przez analizator leksykalny. Jeśli projektujemy nowy język, oddzielenie zagadnień leksykalnych i składniowych może prowadzić do czystszego ogólnego projektu języka.
Poprawiono wydajność kompilatora. Oddzielny analizator leksykalny pozwala nam stosować specjalistyczne techniki, które służą tylko zadaniu leksykalnemu, a nie analizie. Ponadto specjalistyczne techniki buforowania odczytu znaków wejściowych mogą przyspieszyć kompilator znacząco.
2. Poprawiono przenośność kompilatora. Specyfika urządzenia wejściowego może być ograniczona do analizatora leksykalnego.

Resource_ _ _ Kompilatory (wydanie 2) napisane przez- Alfred V. Abo Columbia University Monica S. Lam Uniwersytet Stanforda Ravi Sethi Avaya Jeffrey Ullman Stanford University