Jak skonstruować abstrakcyjne drzewo składni
Mam ogólne pojęcie, czym jest AST, ale chcę wiedzieć, jak go skonstruować.
Jeśli masz gramatykę i drzewo parse, jak skonstruować AST?
Jak to zrobić, jeśli dostajesz gramatykę i wyrażenie?
2 answers
Cóż, po pierwsze, gramatyka jest używana do konstruowania drzewa parsującego z wyrażenia. Więc jeśli masz już drzewo parse, nie potrzebujesz gramatyki.
W zależności od tego, ile pracy wykonuje Twój parser, wynikowe drzewo utworzone z parsowania wyrażenia może być już abstrakcyjnym drzewem składni. Albo może to być proste drzewo parsowania, które wymaga drugiego przejścia do skonstruowania ast.
Aby skonstruować drzewo parsowania z gramatyki i wyrażenia, musisz najpierw konwersja gramatyki do kodu roboczego. Zwykle dzielimy pracę na tokenizer, który dzieli strumień wejściowy reprezentujący wyrażenie na listę tokenów, oraz parser, który pobiera listę tokenów i konstruuje z niej drzewo parsowania\AST.
Więc wyrażenie 1 + 2*(3+4) może być podzielone na listę tokenów, jak to:
1 - int
+ - add_operator
2 - int
* - mul_operator
( - lparen
3 - int
+ - add_operator
4 - int
) - rparen
Pierwsza kolumna jest rzeczywistą wartością tekstu. Drugi reprezentuje typ tokena. Tokeny te są przekazywane do parsera, który zbudowany jest z twoja gramatyka i rozpoznaje tokeny i buduje drzewo parse.
Więc, jak można napisać Tokenizer leksykalny i rzeczywisty parser? Możesz toczyć własne ręcznie. Lub, częściej, używać generatora parsera jak coco lub antlr lub lex / yacc. Te narzędzia pobierają opis gramatyki i generują kod dla tokenziera i parsera. (Generatory kodu istnieją również dla większości popularnych języków i niektórych niepopularnych.)
Sposób konstruowania parsera zależy w dużej mierze od tego, co język, którego używasz. Sposób pisania parsera w Haskell jest zupełnie inny niż w, powiedzmy, C.
Oto samouczek, który pokazuje, jak zbudować własny rekurencyjny Parser descent .
Jeśli Python jest dla ciebie, to pyparsing może dla Ciebie.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-10-04 13:58:29
Odpowiem na to z ogólnej perspektywy, nie próbując mówić o lexerach i parserach.
Drzewo parsowania zawiera symbole nie-terminalowe, które są częścią gramatyki bezkontekstowej i pokazuje Łańcuch produkcji, aby uzyskać ciąg składający się z symboli terminalowych, rekurencyjnie lub nie. Więc kiedy masz drzewo parse nie potrzebujesz gramatyki - możesz czerpać gramatykę z drzewa parse.
AST nie zawiera żadnych symboli nieterminalnych. Zawiera tylko symbole.
Przykład:
E
|
E + T
| |
T M * M
| | |
M a b
|
a
, która jest bardzo szybką wersją pokazywania a+a*b. Uwaga, sposób interpretowania abstrakcyjnego drzewa składniowego zależy od pierwszeństwa drzewa, rodzaju przejścia (w kolejności, pre-order, post-order) będzie to ogólna funkcja, którą kodujesz w swoim drzewie wyszukiwania. Jednak, ogólnie rzecz biorąc, AST dla tego drzewa parsowania może wyglądać tak:
+
| |
a *
| |
a b
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-01-24 19:20:22