leksykon kontra parsery

Czy leksykon i parser tak naprawdę różnią się w teorii?

Modne wydaje się nienawidzić wyrażeń regularnych: kodowanie horroru , kolejny post na blogu .

Jednak popularne narzędzia oparte na leksykach: pigmety , geshi lub prettify , wszystkie używają wyrażeń regularnych. Wydaje się, że lex cokolwiek ...

Kiedy wystarczy leksykacji, kiedy potrzebujesz EBNF?

Czy ktoś używał tokenów wytworzonych przez te leksyksy z generatorami parsera bison lub antlr?

Co łączy parserów i leksyków:

1. Odczytują symbole jakiegoś alfabetu ze swojego wejścia.

   • Wskazówka: Alfabet niekoniecznie musi składać się z liter. Ale muszą to być symbole atomowe dla języka rozumianego przez parser / lexer.
   • Symbole dla leksera: znaki ASCII.
   • Symbole dla parsera: poszczególne tokeny, które są terminalnymi symbolami ich gramatyki.

2. Analizują te symbole i starają się dopasować je do gramatyki języka, który rozumieją.
   

   • Oto, gdzie zwykle leży prawdziwa różnica. Więcej informacji poniżej.
   • Gramatyka rozumiana przez leksykonów: gramatyka regularna (poziom Chomsky'ego 3).
   • Gramatyka rozumiana przez parsery: gramatyka bezkontekstowa (poziom Chomsky'ego 2).

3. Łączą semantykę (znaczenie) ze znalezionymi fragmentami języka.

   • Lexery przypisują znaczenie, klasyfikując leksemy (ciągi znaków z danych wejściowych) jako poszczególne tokeny . Np Wszystkie te leksemy: *, ==, <=, ^będą klasyfikowane jako „operator” znaków przez C / C ++ lexer.
   • Parsery przypisują znaczenie, klasyfikując ciągi znaków z danych wejściowych (zdań) jako poszczególne nieterminale i budując drzewo analizy . Np wszystkie te symboliczne ciągi: [number][operator][number], [id][operator][id], [id][operator][number][operator][number]będą klasyfikowane jako „ekspresja” nieterminalowi przez C / C ++ parsera.

4. Mogą przypisać dodatkowe znaczenie (dane) do rozpoznawanych elementów.

   • Gdy leksyker rozpozna sekwencję znaków składającą się z odpowiedniej liczby, może przekonwertować ją na wartość binarną i zapisać za pomocą tokena „liczba”.
   • Podobnie, gdy parser rozpozna wyrażenie, może obliczyć jego wartość i zapisać go w węźle „wyrażenie” drzewa składniowego.

5. Wszystkie wytwarzają na swoim wyjściu właściwe zdania w języku, który rozpoznają.

   • Lexery produkują tokeny , które są zdaniami w znanym im języku . Każdy token może mieć wewnętrzną składnię (choć poziom 3, a nie poziom 2), ale to nie ma znaczenia dla danych wyjściowych i dla tego, który je odczytuje.
   • Parsery produkować drzew składniowych , które są reprezentacje zdań w języku bezkontekstowych ich rozpoznać. Zwykle jest to tylko jedno duże drzewo dla całego pliku dokumentu / źródła, ponieważ cały plik dokumentu / źródła jest dla nich właściwym zdaniem . Ale nie ma żadnych powodów, dla których analizator składni nie mógł wygenerować serii drzew składniowych na swoim wyjściu. Np. Może to być parser, który rozpoznaje tagi SGML wklejone w zwykły tekst. Więc to tokenize dokument SGML do serii tokenów: [TXT][TAG][TAG][TXT][TAG][TXT]....

Jak widać, parsery i tokenizery mają wiele wspólnego. Jeden parser może być tokenizerem dla innego parsera, który odczytuje jego tokeny wejściowe jako symbole z własnego alfabetu (tokeny są po prostu symbolami jakiegoś alfabetu) w taki sam sposób, jak zdania z jednego języka mogą być symbolami alfabetycznymi innego, wyższego poziomu język. Na przykład, jeśli *i -są symbolami alfabetu M(jako „symbole kodu Morse'a”), możesz zbudować parser, który rozpoznaje ciągi tych kropek i linii jako litery zakodowane w kodzie Morse'a. Zdania w języku „Kod Morse'a” mogą być tokenami dla innego parsera, dla którego te tokenysą atomowymi symbolami jego języka (np. język „angielskich słów”). I te „angielskie słowa” mogą być tokenami (symbolami alfabetu) dla parsera wyższego poziomu, który rozumie język „angielskich zdań”. I wszystkie te języki różnią się jedynie na złożoność gramatyki . Nic więcej.

Więc o co chodzi z tymi „poziomami gramatyki Chomsky'ego”? Noam Chomsky podzielił gramatykę na cztery poziomy w zależności od ich złożoności:

• Poziom 3: Gramatyka regularna

  Oni używają wyrażeń regularnych, czyli mogą składać się wyłącznie z symboli alfabetu ( a, b), ich powiązań, ( ab, aba, bbbETD.) Lub alternatywne (np a|b).
  Można je zaimplementować jako automaty stanów skończonych (FSA), takie jak NFA (niedeterministyczny automat skończony) lub lepiej DFA (deterministyczny automat skończony).
  Zwykłe gramatyki nie radzą sobie z zagnieżdżoną składnią , np. Odpowiednio zagnieżdżone / dopasowane nawiasy (()()(()())), zagnieżdżone tagi HTML / BBcode, zagnieżdżone bloki itp. To dlatego, że automaty stanowe do radzenia sobie z tym powinny mieć nieskończenie wiele stanów do obsługi nieskończenie wielu poziomów zagnieżdżania.

• Poziom 2: Gramatyki bezkontekstowe

  Mogą mieć zagnieżdżone, rekurencyjne, samopodobne gałęzie w drzewach składniowych, dzięki czemu mogą dobrze obsługiwać zagnieżdżone struktury.
  Można je zaimplementować jako automat stanowy ze stosem. Ten stos służy do reprezentowania poziomu zagnieżdżenia składni. W praktyce są one zwykle implementowane jako analizator składający się z góry w dół, który używa stosu wywołań procedur w celu śledzenia poziomu zagnieżdżenia i używa rekurencyjnie wywoływanych procedur / funkcji dla każdego nieterminalnego symbolu w swojej składni.
  Ale nie mogą sobie poradzić z kontekstową składnią. Np. Gdy masz wyrażenie, x+3w jednym kontekście xmoże to być nazwa zmiennej, aw innym kontekście może to być nazwa funkcji itp.

• Poziom 1: Gramatyki kontekstowe

• Poziom 0: Gramatyka nieograniczona
  Zwane także gramatykami wymiennymi.

Tak, są bardzo różne w teorii i wdrażaniu.

Lexery są używane do rozpoznawania „słów”, które składają się na elementy językowe, ponieważ ich struktura jest na ogół prosta. Wyrażenia regularne są bardzo dobre w obsłudze tej prostszej struktury, a do implementacji leksyków wykorzystywane są bardzo wydajne silniki dopasowywania wyrażeń regularnych.

Parsery są używane do rozpoznawania „struktury” fraz językowych. Taka struktura zasadniczo wykracza poza to, co „wyrażenia regularne” mogą rozpoznać, dlatego do wyodrębnienia takiej struktury potrzebne są parsery „kontekstowe”. Parsery kontekstowe są trudne do zbudowania, więc kompromisem inżynieryjnym jest użycie gramatyki „bezkontekstowej” i dodanie hackerów do parserów („tabel symboli” itp.) Do obsługi części kontekstowej.

Ani technologia leksykalna, ani parsująca prawdopodobnie nie zniknie wkrótce.

Oni mogą być ujednolicone decydując się użyć „parsowania” technologię rozpoznawania „słowa”, jak to jest obecnie badane przez tzw scannerless parser glr. Ma to koszt działania, ponieważ nakładasz bardziej ogólne maszyny na to, co często stanowi problem, który ich nie potrzebuje, i zwykle płacisz za to narzutami. W przypadku dużej liczby bezpłatnych cykli koszty te mogą nie mieć znaczenia. Jeśli przetwarzasz dużo tekstu, narzut ma znaczenie i klasyczne parsery wyrażeń regularnych będą nadal używane.

Kiedy wystarczy leksykacji, kiedy potrzebujesz EBNF?

EBNF naprawdę nie wnosi zbyt wiele do potęgi gramatyki. Jest to po prostu wygoda / oznaczenie skrótu / „cukier syntaktyczny” w stosunku do standardowych reguł gramatycznych Chomsky'ego „Normalna forma” (CNF). Na przykład alternatywa dla EBNF:

S --> A | B

możesz osiągnąć w CNF, wymieniając osobno każdą alternatywną produkcję:

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

Opcjonalny element z EBNF:

S --> X?

można osiągnąć w CNF za pomocą zerowalnej produkcji, to znaczy takiej, którą można zastąpić pustą struną (oznaczoną tutaj pustą produkcją; inni używają epsilon lub lambda lub skrzyżowanego koła):

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 poprzednia B nazywa się „skasowaniem”, ponieważ może usunąć wszystko, co oznacza w innych produkcjach (produkuje pusty ciąg zamiast czegoś innego).

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

S --> A*

możesz uzyskać, używając produkcji rekurencyjnej , czyli takiej, która gdzieś się w niej osadza. Można to zrobić na dwa sposoby. Pierwszą jest pozostawiona rekurencja (której zwykle należy unikać, ponieważ parsery zstępującego rekurencyjnego zstępowania nie mogą jej przeanalizować):

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 ciąg (ostatecznie), po którym następuje zero lub więcej As, ten sam ciąg ( ale nie ten sam język! ) Można wyrazić za pomocą rekurencji w prawo :

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+

można tego dokonać poprzez wyodrębnienie jednego z nich Ai użycie *jak poprzednio:

S --> A A*

które możesz wyrazić w CNF jako takim (korzystam z właściwej rekurencji tutaj; 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, prawdopodobnie teraz możesz rozpoznać gramatykę wyrażenia regularnego (to znaczy gramatyki regularnej ) jako taką, która może być wyrażona w pojedynczej produkcji EBNF składającej się tylko z symboli końcowych. Mówiąc bardziej ogólnie, możesz rozpoznać gramatykę, gdy zobaczysz 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.

Oznacza to, że używa się tylko pustych ciągów, symboli terminali, prostych nieterminalnych podstawień i zmian stanu oraz używa rekurencji tylko w celu uzyskania powtórzenia (iteracja, która jest po prostu rekurencją liniową - ta, która nie rozgałęzia się jak drzewo). Nie ma nic bardziej zaawansowanego niż te, więc jesteś pewien, że jest to zwykła składnia i możesz do tego użyć tylko leksykonu.

Ale kiedy twoja składnia używa rekurencji w trywialny sposób, aby stworzyć podobne do drzewa, podobne do siebie, zagnieżdżone struktury, takie jak ta:

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 można zauważyć, że nie można tego zrobić za pomocą wyrażenia regularnego, ponieważ nie można go w żaden sposób przekształcić w jedną produkcję EBNF; będziesz skończyć z zastępując na Sczas nieokreślony, który zawsze będzie dodać kolejne as i bs po obu stronach. Lexery (a dokładniej: automaty stanów skończonych używane przez leksykonów) nie mogą się liczyć do dowolnej liczby (są skończone, pamiętasz?), Więc nie wiedzą, ile as było tam równych z tyloma bs. Gramatyki takie jak te nazywane są gramatykami bezkontekstowymi (przynajmniej) i wymagają parsera.

Gramatyki bezkontekstowe są dobrze znane z analizowania, więc są szeroko stosowane do opisywania składni języków programowania. Ale jest coś 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, jeśli chcesz opisać język, w którym można użyć przeplecionych okrągłych nawiasów i kwadratowych nawiasów klamrowych, ale należy je poprawnie ze sobą sparować (nawiasy klamrowe z okrągłymi nawiasami okrągłymi). Ten rodzaj gramatyki nazywa się kontekstowym . 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 pomyśleć o tych dodatkowych symbolach po lewej stronie jako „kontekście” dla zastosowania reguły. Mogą istnieć pewne warunki wstępne, dodatkowe itp. Na przykład powyższa reguła zastąpi Rsię S, ale tylko wtedy, gdy będzie pomiędzy Ai Bpozostawiając te Ai Bsiebie samych bez zmian. Tego rodzaju składnia jest naprawdę trudna do przeanalizowania, ponieważ wymaga pełnowymiarowej maszyny Turinga. To zupełnie inna historia, więc skończę tutaj.

Aby odpowiedzieć na zadane pytanie (bez nadmiernego powtarzania tego, co pojawia się w innych odpowiedziach)

Lexery i parsery nie różnią się bardzo, jak sugeruje przyjęta odpowiedź. Oba opierają się na prostych formalizmach językowych: zwykłych językach dla leksykalnych i prawie zawsze językach bezkontekstowych (CF) dla parserów. Oba są powiązane z dość prostymi modelami obliczeniowymi, automatem skończonym i automatem stosu push-down. Zwykłe języki to szczególny przypadek języków bezkontekstowych, dzięki czemu leksykon może być produkowany z nieco bardziej złożoną technologią CF. Ale to nie jest dobry pomysł z co najmniej dwóch powodów.

Podstawową kwestią w programowaniu jest to, że komponent systemu powinien być wyposażony w najbardziej odpowiednią technologię, aby można go było łatwo wyprodukować, zrozumieć i utrzymać. Technologia nie powinna być przesadna (przy użyciu technik o wiele bardziej złożonych i kosztownych niż jest to potrzebne), ani nie powinna być na granicy swoich możliwości, wymagając w związku z tym technicznych starań, aby osiągnąć zamierzony cel.

Dlatego „wydaje się modne nienawidzić wyrażeń regularnych”. Chociaż mogą wiele zrobić, czasem wymagają bardzo nieczytelnego kodowania, aby to osiągnąć, nie wspominając o tym, że różne rozszerzenia i ograniczenia w implementacji nieco zmniejszają ich teoretyczną prostotę. Lexery zwykle tego nie robią i są zwykle prostą, wydajną i odpowiednią technologią do parsowania tokena. Używanie parserów CF dla tokena byłoby przesadą, choć jest to możliwe.

Innym powodem, dla którego nie należy używać formalizmu CF dla leksykonów, jest to, że może być kuszące, aby użyć pełnej mocy CF. Ale może to powodować problemy strukturalne związane z czytaniem programów.

Zasadniczo większość struktury tekstu programu, z którego wyodrębnia się znaczenie, to struktura drzewa. Wyraża, w jaki sposób zdanie (program) parsowane jest generowane na podstawie reguł składniowych. Semantyka wyprowadzana jest za pomocą technik kompozytorskich (homomorfizm dla matematyki) ze sposobu, w jaki tworzone są reguły składniowe do budowania drzewa parsowania. Dlatego struktura drzewa jest niezbędna. Fakt, że tokeny są identyfikowane za pomocą leksykonu opartego na regularnym zestawie, nie zmienia sytuacji, ponieważ CF złożony z regularnym wciąż daje CF (mówię bardzo luźno o zwykłych przetwornikach, które przekształcają strumień znaków w strumień tokena).

Jednak CF skomponowany z CF (za pomocą przetworników CF ... przepraszam za matematykę), niekoniecznie daje CF i może sprawić, że rzeczy będą bardziej ogólne, ale mniej praktyczne. Tak więc CF nie jest odpowiednim narzędziem dla leksykonów, nawet jeśli można go użyć.

Jedną z głównych różnic między zwykłym a CF jest to, że zwykłe języki (i przetworniki) komponują się bardzo dobrze z prawie każdym formalizmem na różne sposoby, podczas gdy języki CF (i przetworniki) nie, nawet z sobą (z kilkoma wyjątkami).

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

BNF to tylko specyficzna składnia do prezentacji gramatyki CF.

EBNF jest cukrem syntaktycznym dla BNF , wykorzystującym funkcje regularnego notowania w celu uzyskania lepszej wersji gramatyki BNF. Zawsze można go przekształcić w równoważny czysty BNF.

Jednak regularna notacja jest często używana w EBNF tylko w celu podkreślenia tych części składni, które odpowiadają strukturze elementów leksykalnych i powinny być rozpoznawane za pomocą leksera, podczas gdy pozostałe powinny być raczej przedstawione w prostym BNF. Ale to nie jest absolutna zasada.

Podsumowując, prostsza struktura tokena jest lepiej analizowana za pomocą prostszej technologii zwykłych języków, podczas gdy drzewna struktura języka (składni programu) jest lepiej obsługiwana przez gramatyki CF.

Sugerowałbym również przyjrzenie się odpowiedzi AHR .

Ale to pozostawia otwarte pytanie: dlaczego drzewa?

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

• nadają tekstowi prostą strukturę

• bardzo wygodne jest powiązanie semantyki z tekstem na podstawie tej struktury, z matematycznie dobrze rozumianą technologią (składanie przez homomorfizmy), jak wskazano powyżej. Jest to podstawowe narzędzie algebraiczne do definiowania semantyki formalizmów matematycznych.

Dlatego jest to dobra reprezentacja pośrednia, o czym świadczy sukces drzew abstrakcyjnych składni (AST). Należy zauważyć, że AST często różnią się od drzewa parsowania, ponieważ technologia analizy używana przez wielu specjalistów (takich jak LL lub LR) ma zastosowanie tylko do podzbioru gramatyki CF, wymuszając w ten sposób zniekształcenia gramatyczne, które są później korygowane w AST. Można tego uniknąć dzięki bardziej ogólnej technologii analizowania (opartej na programowaniu dynamicznym), która akceptuje dowolną gramatykę CF.

Oświadczenie o tym, że języki programowania są wrażliwe na kontekst (CS), a nie CF, są arbitralne i dyskusyjne.

Problem polega na tym, że rozdzielenie składni i semantyki jest arbitralne. Sprawdzanie deklaracji lub zgodności typów może być postrzegane jako część składni lub semantyka. To samo dotyczy zgodności płci i liczby w językach naturalnych. Są jednak języki naturalne, w których zgodność w liczbie mnogiej zależy od faktycznego znaczenia semantycznego słów, więc nie pasuje do składni.

Wiele definicji języków programowania w semantyce denotacyjnej umieszcza deklaracje i sprawdzanie typu w semantyce. Stwierdzenie, jak zrobiono to Ira Baxter, że parsery CF są hakowane w celu uzyskania czułości kontekstu wymaganej przez składnię, jest w najlepszym razie arbitralnym obrazem sytuacji. Może być zorganizowany jako hack w niektórych kompilatorach, ale nie musi tak być.

Nie tylko parsery CS (w znaczeniu używanym w innych odpowiedziach tutaj) są trudne do zbudowania i mniej wydajne. Nie są one również wystarczające do wyraźnego wyrażenia wrażliwości kontekstu, która może być potrzebna. I nie wytwarzają naturalnie struktury syntaktycznej (takiej jak drzewa parsowania), która jest wygodna do uzyskania semantyki programu, tj. Do wygenerowania skompilowanego kodu.

Istnieje wiele powodów, dla których część kompilatora dotycząca analizy jest zwykle podzielona na fazy analizy leksykalnej i analizy (analizy składni).

1. Najważniejsza jest prostota projektowania. Rozdzielenie analizy leksykalnej i składniowej często pozwala uprościć przynajmniej jedno z tych zadań. Na przykład, parser, który miałby do czynienia z komentarzami i białymi spacjami jako jednostkami składniowymi, byłby. Analizator leksykalny usunął już znacznie bardziej złożone niż te, które mogą zakładać komentarze i białe znaki. Jeśli projektujemy nowy język, rozdzielenie problemów leksykalnych i składniowych może prowadzić do czystszego ogólnego projektu języka.
2. Poprawiona wydajność kompilatora. Oddzielny analizator leksykalny pozwala nam stosować specjalistyczne techniki, które służą jedynie zadaniu leksykalnemu, a nie analizie. Ponadto wyspecjalizowane techniki buforowania do odczytu znaków wejściowych mogą znacznie przyspieszyć kompilator.
3. Zwiększona przenośność kompilatora. Specyfika urządzenia wejściowego może być ograniczona do analizatora leksykalnego.

źródło ___ Kompilatory (wydanie drugie) - autor: Alfred V. Abo Columbia University Monica S. Lam Stanford University Ravi Sethi Avaya Jeffrey D. Ullman Stanford University