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?
Odpowiedzi:
Co łączy parserów i leksyków:
Odczytują symbole jakiegoś alfabetu ze swojego wejścia.
Analizują te symbole i starają się dopasować je do gramatyki języka, który rozumieją.
Łączą semantykę (znaczenie) ze znalezionymi fragmentami języka.
*
,==
,<=
,^
będą klasyfikowane jako „operator” znaków przez C / C ++ lexer.[number][operator][number]
,[id][operator][id]
,[id][operator][number][operator][number]
będą klasyfikowane jako „ekspresja” nieterminalowi przez C / C ++ parsera.Mogą przypisać dodatkowe znaczenie (dane) do rozpoznawanych elementów.
Wszystkie wytwarzają na swoim wyjściu właściwe zdania w języku, który rozpoznają.
[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 alfabetuM
(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
,bbb
ETD.) Lub alternatywne (npa|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+3
w jednym kontekściex
moż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.
źródło
STMT_END
w 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_END
jako;
mieć C / C ++ - jak kodzie źródłowym. Możesz też zdefiniować go tak,end
aby 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.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.
źródło
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:
możesz osiągnąć w CNF, wymieniając osobno każdą alternatywną produkcję:
Opcjonalny element z EBNF:
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):
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:
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ć):
Wiedząc, że generuje tylko pusty ciąg (ostatecznie), po którym następuje zero lub więcej
A
s, ten sam ciąg ( ale nie ten sam język! ) Można wyrazić za pomocą rekurencji w prawo :A jeśli chodzi
+
o jedno lub więcej powtórzeń z EBNF:można tego dokonać poprzez wyodrębnienie jednego z nich
A
i użycie*
jak poprzednio:które możesz wyrazić w CNF jako takim (korzystam z właściwej rekurencji tutaj; spróbuj sam obliczyć drugą jako ćwiczenie):
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:
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:
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
S
czas nieokreślony, który zawsze będzie dodać kolejnea
s ib
s 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ą, ilea
s było tam równych z tylomab
s. 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:
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
R
sięS
, ale tylko wtedy, gdy będzie pomiędzyA
iB
pozostawiając teA
iB
siebie 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.źródło
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.
źródło
Istnieje wiele powodów, dla których część kompilatora dotycząca analizy jest zwykle podzielona na fazy analizy leksykalnej i analizy (analizy składni).
ź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
źródło