Jak zbudować abstrakcyjne drzewo składni

Question

Mam ogólne pojęcie o tym, czym jest AST, ale chcę wiedzieć, jak go zbudować.

Jeśli masz gramatykę i drzewo analizy, jak zbudować AST?

Jak to zrobić, jeśli otrzymujesz gramatykę i wyrażenie?

Answer 1

Po pierwsze, gramatyka jest używana do konstruowania drzewa analizy z wyrażenia. Jeśli masz już drzewo analizy, nie potrzebujesz gramatyki.

W zależności od tego, ile pracy wykona Twój analizator składni, wynikowe drzewo utworzone podczas przetwarzania wyrażenia może już być abstrakcyjnym drzewem składni. Lub może to być proste drzewo parse, które wymaga drugiego przejścia, aby zbudować ast.

Aby skonstruować drzewo parse z gramatyki i wyrażenia, należy najpierw przekonwertować gramatykę na działający kod. Zazwyczaj dzieli się pracę na tokenizer, który dzieli strumień wejściowy reprezentujący wyrażenie na listę tokenów, a także analizator składniowy, który pobiera listę tokenów i tworzy z nich drzewo składniowe \ ast.

Więc wyrażenie 1 + 2*(3+4) może być podzielony na liście tokenów tak:

1 - int 
+ - add_operator 
2 - int 
* - mul_operator 
(- lparen 
3 - int 
+ - add_operator 
4 - int 
) - rparen 

Pierwsza kolumna jest rzeczywista wartość tekstu. Druga reprezentuje typ tokena. Te żetony są podawane do parsera, który jest zbudowany na podstawie twojej gramatyki i rozpoznaje tokeny i buduje drzewo parsowania.

W jaki sposób można napisać tokenizator leksykalny i rzeczywisty parser? Możesz rzucić własną ręką. Lub, częściej, użyj generatora analizatora składni, takiego jak coco lub antlr lub lex/yacc. Narzędzia te opisują twoją gramatykę i generują kod dla tokenziera i parsera. (Generatory kodowe istnieją również w najpopularniejszych językach, a niektóre niepopularne).

Sposób tworzenia parsera zależy w dużym stopniu od języka, którego używasz. W jaki sposób można napisać parser w Haskell jest zupełnie inny od tego, jak ty w to, powiedzmy, C.

• Oto poradnik, który pokazuje jak build your own recursive descent parser.

• Coco to generator parsera dla różnych języków, który również zawiera wraz z dokumentacją, jak zacząć.

• Jeśli Python to twoja rzecz, to może dla ciebie jest pyparsing.

Answer 2

Będę odpowiadać na to z ogólnej perspektywy, nie próbując mówić o leksykach i parserach.

Drzewo analizatora zawiera nieterminalne symbole, które są częścią gramatyki bezkontekstowej i pokazuje łańcuch produkcji, aby uzyskać ciąg znaków składający się z symboli terminala, rekursywnie lub nie. Więc kiedy masz drzewo parse, nie potrzebujesz gramatyki - możesz uzyskać gramatykę z drzewa parse.

AST nie zawiera żadnych nieterminalnych symboli. Zawiera tylko symbole.

Przykład:

E 
| 
E + T 
| | 
T M * M 
| | | 
M a b 
| 
a 

który jest bardzo szybki wersję pokazując a+a*b. Zauważ, że sposób interpretacji abstrakcyjnego drzewa składni zależy od priorytetu drzewa, jakiego rodzaju przejścia wykonujesz (w kolejności, w przedsprzedaży, po zamówieniu). Jest to ogólna funkcja, którą kodujesz w drzewie wyszukiwania. Jednak ogólnie rzecz biorąc, AST dla tego drzewa parsowania może wyglądać następująco:

+ 
| | 
a * 
    | | 
    a b