Jak zaprojektować części drzewa składni abstrakcyjnej?

Piszę interpreter języka C# od podstaw dla doświadczenia uczenia się i do tej pory wszystko poszło gładko. Mam w pełni funkcjonalny lexer C#, który wysyła wszystkie rodzaje tokenów do analizatora składni. Wiem, jak mam zamiar parsować tokeny, ale nie jestem pewien, jak powinienem uporządkować moje AST (abstrakcyjne drzewo składniowe).Jak zaprojektować części drzewa składni abstrakcyjnej?

Na przykład, jeśli mam prosty fragment kodu:

using System.Xml;

co by drzewo wyglądać, gdy analizowany?

Podoba Ci się to?

UsingDirective 
    Identifier(System) 
     Identifier(Xml)

lubisz to?

UsingDirective 
    Identifier(System) 
    Identifier(Xml)

Jeśli mógłbym dostać jakieś sugestie i/lub przykłady jak to jak mógłbym zorganizować rzeczy jak identyfikatory z kropkami w nich, jeśli/else if/else, deklaracja zmiennej/cesja połączone w jednej instrukcji (int i = 0;), definicje funkcji itp., Które byłyby pomocne. Po prostu potrzebuję lepszego pomysłu na strukturę drzewa i sam mogę wymyślić resztę. Dzięki.

Źródło

2012-03-07 Cole Shepherd

To będzie długa nauka, jeśli chcesz zaimplementować całe C# :-) – svick

. Pomijam większość biblioteki klas. Zasadniczo po prostu wdrażam to, co musi zostać zaimplementowane w odniesieniu do podstawowych definicji klas/funkcji, zmiennych kreacji/użycia i wywołań funkcji. –

Pisałem parę parserami w przeszłości, a ja zwykle iść na coś takiego:

UsingDirective 
    IdentifierList 
    Identifier (LeftNode) (System) 
    Identifier (RightNode) (Xml)

W przypadku tego using System.Collections.Generic

UsingDirective 
    IdentifierList 
     IdentifierList (LeftNode) 
      Identifier (LeftNode) (System) 
      Identifier (RightNode) (Collections) 
     Identifier (RightNode) (Generic)

przeciwieństwie Roslyn, wolę utrzymywanie moich AST w świetle, nie wliczając w to żetonów, takich jak średnik, słowo kluczowe using itp., ponieważ kompilator nie potrzebuje ich.

Parsery, które napisałem specjalnie dla IDE, wyglądają inaczej - zawierają wszystkie dodatkowe elementy wraz z dodatkowymi informacjami, takimi jak numery linii i kolumn.

Źródło

2012-03-07 01:54:48 xbonez

Dlaczego Twój "IdentifierList" ma tylko dwoje dzieci? Dlaczego nie mieć jednego "IdentifierList" z tylu dzieci, ile to konieczne? – svick

Tak, myślę, że jeden Identyfikator z nieograniczoną liczbą dzieci byłby lepszy. W każdym razie, dzięki za odpowiedź xbonez. –

Jestem pewien, że to też zadziała. Osobiście łatwiej jest przechodzić w ten sposób (rekursywnie), niż gdyby była to tylko lista identyfikatorów. Ustawiłem funkcję 'traverIdentList':' if (identlist.leftnode is identlistnode) {traverseIdentList (leftnode); } else {traverseident (leftnode); } Traverseident (rightnode); ' – xbonez

Możesz sprawdzić, jak Microsoft radzi sobie z Roslyn. Można było zobaczyć, w jaki sposób zadeklarowano składnie drzewek dla C# (i VB.NET), a może nawet możesz użyć go zamiast części tłumacza, zanim je napiszesz.

szczególności Roslyn drzewo składnia dla dyrektywy using wygląda następująco:

UsingDirective 
    UsingKeyword 
    QualifiedName 
     IdentifierName (System) 
     DotToken 
     IdentifierName (Xml) 
    SemicolonToken

więc podobna do drugiej wersji, ale bardziej szczegółowy.

Myślę, że twoja pierwsza wersja nie ma większego sensu. Xml nie jest dzieckiem System na poziomie syntaktycznym (nawet jeśli możesz mieć pojęcie "nadrzędnej przestrzeni nazw" później na poziomie semantycznym).

Źródło

2012-03-07 01:41:24 svick

Ale to nie jest abstrakcyjne drzewo składniowe, to konkretne drzewo składniowe, ponieważ zawiera części kodu źródłowego, takie jak kropka i średnik. –

Tak, masz rację. Ale myślę, że mógłbyś oprzeć swoją AST na tym. – svick

Tak, dziękuję za odpowiedź! Pomogło. –

Jak zaprojektować części drzewa składni abstrakcyjnej?

Odpowiedz

Powiązane problemy