构建抽象语法树需要考虑哪些要点

Question

我正在开发一种简单的玩具语言来描述 UI 小部件。我已经使用 bison/flex 来实现语法。我现在想根据语法规则创建一个 AST。但是，我不确定 AST 的 "level of granularity" 以及它应该包含什么。据我所知，AST 应该是 "minimal" 并且避免提供冗余信息。同时，显然我不应该丢失原始来源的任何信息。构建 AST 时是否有特定规则要遵循？

语法如下：

%{

#include <string>
#include <iostream>

void yyerror (const char *error);
int  yylex();

extern int yylineno;

%}

%code{
 //   int lineno;
}

%union {
  char* s;
  double d;
  int i;
}

/* declare tokens */


%token APPLICATION GEOMETRY
%token FORM BUTTON LABEL TEXTINPUT
%token ID NAME 
%token WIDTH HEIGHT TEXT ONCLICK
%token ABSOLUTELAYOUT LINEARLAYOUT GRIDLAYOUT
%token ABSOLUTE_LAYOUT_DOT_LEFT ABSOLUTE_LAYOUT_DOT_TOP   
%token EOL ENDOFFILE

%token<s> IDENTIFIER STRING
%token<d> INTEGER

%%


appDef: APPLICATION '{' NAME ':' STRING formdefList '}' {std::cout << "found app" << std::endl;}

iddef : ID ':' IDENTIFIER


formdefList : /* nothing */
    | formdefList formdef
    ;


formdef : FORM  '{' formbodydef '}' 
    ;

formbodydef : /*nothing*/
    | iddef
    | formbodydef layoutdef
    | error                     { 
                                  std::cout << "found error in form body near line: " << yylineno << std::endl;
                                  std::exit(1);  
                                }
    ;

layoutdef : ABSOLUTELAYOUT '{' layoutBody '}' 
    | GRIDLAYOUT '{' layoutBody '}'
    | LINEARLAYOUT '{' layoutBody '}'
    ;

layoutBody : /* nothing */
    | layoutBody layoutdef       /* Layouts can be embedded in one another */
    | layoutBody buttonDef
    | layoutBody labelDef
    | error { std::cout << "Was expecting a child control near line: " << yylineno << std::endl; std::exit(1);}
    ;

geometrydef : GEOMETRY ':' '{' geometrybody '}' { std::cout << "start of geometry def:" << std::endl;}
    ;

geometrybody : /*nothing*/                      { std::cout << "start of geometrybody def" << std::endl;}
    | geometrybody WIDTH ':' INTEGER             
    | geometrybody HEIGHT ':' INTEGER
    | geometrybody ABSOLUTE_LAYOUT_DOT_LEFT ':' INTEGER
    | geometrybody ABSOLUTE_LAYOUT_DOT_TOP ':' INTEGER
    | error { std::cout << "error near line: " << yylineno << std::endl; std::exit(1);}
    ;

buttonDef : BUTTON '{' buttonBody '}'
    ;

buttonBody : /*nothing*/
    | buttonBody iddef
    | buttonBody TEXT ':' STRING
    | buttonBody geometrydef
    ;

labelDef : LABEL '{' labelBody '}'
    ;

labelBody : /*nothing*/
    | labelBody iddef
    | labelBody TEXT ':' STRING
    | labelBody geometrydef
    ;        

%%


void yyerror (const char *error)
{
  std::cout << error << std::endl;
}

下面是一些用于验证语法的示例输入：

Application{
name: "HelloWorld"
   Form{
      id: MainForm
      LinearLayout{
         Button{
           geometry: {width:20 height:20}
         }
         AbsoluteLayout{
            Button{
               geometry:{
                  width:20
                  height:20
                  AbsoluteLayout.Top:10
                  AbsoluteLayout.Left:20
               }
            }
         }
      }
   }
   Form{
      id: Secondary
   }
}

我现在正在为语法构建 AST，需要一些关于其结构的建议：

我应该如何将语法规则映射到 AST 节点？每个终端符号一个 AST 节点？
- 节点之间的父子关系应该如何设计？
- formdef、formbodydef、formdefList 等语法规则的左侧是否明确出现在 AST 中？
- 我应该在节点中包含什么？仅包含终端令牌类型（ID、NAME 等）和令牌值就足够了吗？
- 我是否应该将所有标记值包含为字符串并在稍后阶段执行实际类型转换（例如字符串到整数等）？

感谢您的建议！

Answer 1

节点需要包含 "abstract" 语法类别（通常接近许多规则的 LHS）。有关 AST 与 CST 的讨论，请参阅，以及为什么您可能希望节点包含具体的语法类别（例如，恰好是规则的 LHS，或叶子的具体名称）。 link 讨论了何时应该在 AST 中保留终端。

它们还应该包含值，如果它们表示以语法不记录的方式变化的东西（例如，标识符名称、数字和字符串常量等），请参阅为什么你应该在 lex 时转换值，而不是稍后。

此处显示：是 AST 打印出来后的样子的示例（您最好构建一个 AST 打印机来帮助您调试它们）。

您需要在节点中保留多少信息取决于您最终打算用它做什么。如果你想从 AST 中重新生成源代码，你需要保留很多你可能从未考虑过的东西，例如转换数字的基数。有关详细信息，请参阅。

构建抽象语法树需要考虑哪些要点

What are the points to consider when building an Abstract Syntax Tree

bison

abstract-syntax-tree