leksykon kontra parsery

308

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?

Naveen
źródło
2
tak. Próbuję parsować autohotkey. Byłem w stanie bardzo szybko zbudować zakreślacz składni za pomocą pigmejów. Ale Antlr trwa znacznie dłużej ... Nie widziałem wiele zapylenia krzyżowego między tymi dwoma narzędziami.
Naveen
67
Modne jest nienawidzić wyrażeń regularnych, gdy są niewłaściwie używane. Wiele osób próbuje używać wyrażeń regularnych, gdy potrzebne jest parsowanie kontekstowe. Zawsze zawodzą. I obwiniają technologię wyrażeń regularnych. To tak, jakby narzekać, że twój młot to kiepska piła. To prawda, ale nie spotka cię wiele współczucia.
Ira Baxter,
2
Na szczęście zaczynam nabierać prędkości z antlr. Wiele leksykaliów jest pozbawionych kontekstu, a czasem nawet zależnych od kontekstu.
Naveen,
1
Jednym fundamentalnym aspektem problemu lexer vs. parser jest to, że lexery oparte są na automatach skończonych (FSA), a dokładniej skończonych przetwornikach (FST). Większość formalizmów parsujących (nie tylko bezkontekstowych) jest zamkniętych pod skrzyżowaniem z FSA lub zastosowaniem FST. Stąd użycie prostszego formalizmu opartego na wyrażeniach regularnych dla leksykonu nie zwiększa złożoności struktur składniowych bardziej złożonych formalizmów parsera. Jest to absolutnie poważny problem modułowości przy definiowaniu struktury i semantyki języków, na szczęście zignorowany przez wysoko głosowane odpowiedzi.
babou
Należy zauważyć, że leksery i parsery nie muszą się różnić, np. LLLPG, a wcześniejsze wersje ANTLR używają tego samego systemu analizowania LL (k) zarówno dla leksykonów, jak i parserów. Główną różnicą jest to, że wyrażenia regularne są zwykle wystarczające dla leksykonów, ale nie dla parserów.
Qwertie,

Odpowiedzi:

475

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.

SasQ
źródło
70
O tak? Czym więc są te „słowa lub tokeny”? Są to tylko zdania w zwykłym języku, składające się z liter alfabetu. A jakie są te „konstrukty” lub „drzewa” w parserze? Są to także zdania , ale w innym języku wyższego poziomu, dla którego poszczególne tokeny są symbolami alfabetycznymi. Różnica nie polega na tym, co powiedziałeś, ale na KOMPLEKSOWOŚCI UŻYWANEGO JĘZYKA . Skonfrontuj swoje -1 z dowolnym podręcznikiem dotyczącym teorii parsowania.
SasQ
3
@SasQ Czy uczciwie byłoby powiedzieć, że zarówno Lexery, jak i Parsery przyjmują gramatykę i serię tokenów jako dane wejściowe?
Parag
4
Właśnie. Obaj pobierają serię symboli z rozpoznanego alfabetu. W leksyrze ten alfabet składa się tylko z prostych znaków. W przypadku parsera alfabet składa się z symboli końcowych, niezależnie od ich definicji. Mogą to być również postacie, jeśli nie używasz leksykonu i używasz jednoznakowych identyfikatorów i jednocyfrowych liczb itp. (Całkiem przydatne na pierwszych etapach rozwoju). Ale zwykle są to tokeny (klasy leksykalne), ponieważ tokeny są dobrą abstrakcją: możesz zmienić rzeczywiste leksemy (ciągi znaków), które reprezentują, a parser nie widzi zmiany.
SasQ
6
Na przykład możesz użyć symbolu terminala STMT_ENDw swojej składni (dla analizatora składni), aby oznaczyć koniec instrukcji. Teraz możesz powiązać z nim token o tej samej nazwie, wygenerowany przez leksykon. Ale możesz zmienić rzeczywisty leksem, który on oznacza. Na przykład. można zdefiniować STMT_ENDjako ;mieć C / C ++ - jak kodzie źródłowym. Możesz też zdefiniować go tak, endaby był jakoś podobny do stylu Pascala. Możesz też zdefiniować to jako '\n'zakończenie instrukcji z końcem wiersza, jak w Pythonie. Ale składnia instrukcji (i parsera) pozostaje niezmieniona :-) Należy zmienić tylko lexer.
SasQ
24
Godziny na Wikipedii i Google nie pomogły, ale wyjaśniłeś gramatykę Chomsky'ego w 3 minuty. Dziękuję Ci.
enrey
107

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.

Ira Baxter
źródło
40
Ładne wyjaśnienie, Ira. Dodając do Twojej analogii: Podczas gdy leksykony mają na celu właściwe wyrazy, parsery mają na celu poprawne zdanie. „See spot run” i „spot run See” są ważne, jeśli chodzi o leksykon. Parser wymaga ustalenia, czy struktura frazy jest niepoprawna (w gramatyce angielskiej).
Alan
myślę, że parser jest dla leksera, tak jak chodzik dla drzewa jest dla parsera. Nie jestem przekonany, że teoria jest inna: antlr.org/wiki/display/~admin/ANTLR+v4+lexers, ale zaczynam rozumieć różnice w konwencjach między nimi ...
Naveen
4
Teoria jest zupełnie inna. Większość technologii parserów próbuje w pewnym stopniu obsługiwać języki bezkontekstowe (niektóre tylko częściowo, np. LALR, niektóre robią to wszystko, np. GLR). Większość technologii leksykalnych próbuje wykonywać wyrażenia regularne.
Ira Baxter,
3
Teoria jest inna, ponieważ została zaproponowana przez wiele różnych osób i stosuje inną terminologię i algorytmy. Ale jeśli przyjrzysz się im uważnie, zauważysz podobieństwa. Na przykład problem lewej rekurencji jest bardzo podobny do problemu niedeterminizmu w NFA, a usuwanie lewej rekurencji jest podobne do usuwania niedeterminizmu i przekształcania NFA w DFA. Tokeny są zdaniami dla tokenizera (wyjście), ale alfabetycznymi symbolami dla parsera (dane wejściowe). Nie zaprzeczam różnicom (poziomy Chomsky'ego), ale podobieństwa bardzo pomagają w projektowaniu.
SasQ
1
Mój urzędnik zajmował się teorią kategorii. Pokazał, w jaki sposób kategoryczna koncepcja krążków obejmuje wszystkie rodzaje dopasowywania wzorów, i był w stanie wyprowadzić analizę LR z abstrakcyjnej specyfikacji kategorycznej. Tak więc, jeśli pójdziesz wystarczająco abstrakcyjnie, możesz znaleźć takie podobieństwa. Istotą teorii kategorii jest to, że często można streścić „w górę”; Jestem pewien, że możesz zbudować parser teorii kategorii, który usunie różnice. Ale wszelkie praktyczne zastosowania tego rozwiązania muszą być tworzone w konkretnej dziedzinie problemowej, a następnie różnice stają się rzeczywiste.
Ira Baxter
32

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.

SasQ
źródło
1
Stwierdzasz, że EBNF jest „zwykłym zapisem / skrótem /„ cukrem syntaktycznym ”w porównaniu ze standardowymi regułami gramatycznymi Chomsky'ego (CNF)”. Ale CNF nie ma prawie nic wspólnego z tym tematem. EBNF można łatwo przekształcić w standardowy BNF. Kropka. Jest to cukier syntaktyczny dla standardowego BNF.
babou
11

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.

Babou
źródło
Tak, parsowanie drzew i AST są różne, ale w zasadzie nie w bardzo użyteczny sposób. Zobacz moją dyskusję na ten temat: stackoverflow.com/a/1916687/120163
Ira Baxter
@IraBaxter Nie zgadzam się z tobą, ale tak naprawdę nie mam teraz czasu na przygotowanie czystej odpowiedzi na Twój post. Zasadniczo przyjmujesz pragmatyczny punkt widzenia (a także, jak sądzę, bronisz własnego systemu). Jest to jeszcze łatwiejsze, ponieważ używasz ogólnych parserów CF (jednak GLR może nie być najbardziej wydajny), a nie deterministycznych, jak w niektórych systemach. Uważam AST za reprezentację odniesienia, która nadaje się do formalnie zdefiniowanego traktowania, możliwych do udowodnienia poprawnych przekształceń, matematycznych dowodów, nieparsowania na wiele konkretnych reprezentacji itp.
babou
„Pragmatyczny” pogląd jest powodem, dla którego twierdzę, że nie różnią się zbytnio w użyteczny sposób. I po prostu nie wierzę, że użycie (ad hoc AST) daje „możliwe do poprawnego przekształcenia”; twój ad hoc AST nie ma oczywistego związku z rzeczywistą gramatyką przetwarzanego języka (i tutaj, tak, mój system można obronić, ponieważ nasz „AST” jest w sposób udowodniony izomorficzny odpowiednikiem BNF). Ad hoc AST nie dają żadnej dodatkowej zdolności do odseparowania się od „wielu konkretnych reprezentacji). Sprzeciw wobec GLR (niezbyt skuteczny) wydaje się dość bezcelowy. Nie są też niedeterministyczni.
Ira Baxter
Tak więc nie rozumiem żadnej części twojego sprzeciwu wobec mojego komentarza. Musisz napisać „czystą odpowiedź”.
Ira Baxter,
@IraBaxter Komentarze są zbyt ograniczone, aby uzyskać poprawną odpowiedź (sugestia?). „Ad hoc” nie jest odpowiednimi kwalifikatorami dla rzecznika AST I, którym powinna być (czasem) składnia referencyjna. Jest to historycznie prawdziwe, biorąc pod uwagę zarówno historię pojęcia AST w informatyce, jak i historię systemów formalnych jako terminów (drzew) w posortowanej algebrze wraz z interpretacją. AST jest formą referencyjną, a nie pochodną. Zobacz także nowoczesne systemy sprawdzające i automatyczne generowanie programów. Możesz być stronniczy z powodu faktu, że musisz pracować z konkretnej składni zaprojektowanej przez innych.
babou
7

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

AHR
źródło