Как спроектировать части абстрактного синтаксического дерева?

Question

Я пишу интерпретатор C # с нуля для обучения, и до сих пор все прошло гладко.У меня есть полностью функциональный лексер C #, который выводит все виды токенов в анализатор.Я знаю, как собираюсь анализировать токены, но я не уверен, как мне структурировать AST (абстрактное синтаксическое дерево).

Например, если у меня есть простой фрагмент кода:

using System.Xml;

как будет выглядеть дерево при разборе?

Как это?

UsingDirective
   Identifier(System)
      Identifier(Xml)

или как это?

UsingDirective
   Identifier(System)
   Identifier(Xml)

Если бы я мог получить немногопредложения и / или примеры того, как я мог бы структурировать такие вещи, как идентификаторы с точками в них, операторы if / else if / else, объявление / присваивание переменной, объединенные в одном выражении (int i = 0;), определения функций и т. д., которые быбыть полезным.Мне просто нужно получить лучшее представление о том, как структурировать дерево, и я могу сам разобраться с остальными.Спасибо.

Answer 1

Я написал пару парсеров в прошлом, и я обычно хотел бы что-то вроде этого:

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

В случае этого using System.Collections.Generic

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

В отличие от Roslyn, я предпочитаю сохранять свои AST легкими, не включая токены, такие как точка с запятой, ключевое слово using и т. Д., Так как компилятору они не нужны.

Парсеры, которые я написал специально для IDE, выглядят по-разному - они несут всю эту дополнительную информацию вместе с дополнительной информацией, такой как номера строк и столбцов.

Answer 2

Вы можете посмотреть, как Microsoft делает это с Рослином. Там вы могли увидеть, как они объявляли синтаксические деревья для C # (и VB.NET), и, возможно, вы могли бы даже использовать их вместо частей вашего интерпретатора, прежде чем писать их.

В частности, синтаксическое дерево Roslyn для вашей директивы using выглядит следующим образом:

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

Итак, похоже на вашу вторую версию, но более подробно.

Я думаю, что ваша первая версия не имеет особого смысла. Xml не является потомком System на синтаксическом уровне (даже если позже у вас может быть понятие «родительское пространство имен» на семантическом уровне).