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

Question

我正在开发一种简单的玩具语言来描述 UI 小部件。我使用 bison/flex 来实现语法。我现在想根据语法规则创建 AST。但是，我不确定 AST 的“粒度级别”以及其中应包含哪些内容。根据我的阅读，AST 应该是“最小的”并且避免提供冗余信息。同时显然我不应该丢失原始来源的任何信息。构建 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 中？
  • 我应该在节点中包含什么？仅仅包含终端 token 类型(ID、NAME 等)和 token 值就足够了吗？
  • 我是否应该将所有标记值包含为字符串并在稍后阶段执行实际的类型转换(例如字符串到整数等)？

感谢您的建议!

Answer 1

节点需要包含一个“抽象”语法类别(通常接近许多规则的 LHS)。 请参阅https://stackoverflow.com/a/1916687/120163讨论 AST 与 CST，以及为什么您可能希望节点包含具体的语法类别(例如，恰好是规则的 LHS，或叶子的具体名称)。 该链接讨论了何时应将终端保留在 AST 中。

如果它们表示的内容以语法未记录的方式变化(例如标识符名称、数字和字符串常量等)，则它们还应该包含值。请参阅 https://stackoverflow.com/a/6320259/120163为什么你应该在 lex 时转换值，而不是稍后。

此处显示:https://stackoverflow.com/a/17393852/120163是 AST 打印出来后可能是什么样子的示例(您最好构建一个 AST 打印机来帮助您调试它们)。

您需要在节点中保留多少信息取决于您最终打算用它做什么。如果你想从 AST 重新生成源代码，你需要保留很多你可能从未考虑过的东西，例如转换后的数字的基数。请参阅https://stackoverflow.com/a/5834775/120163了解更多详情。