構建抽象語法樹時需要考慮的要點

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節點？
  • 我應該如何設計節點之間的父子關係？
  • 文法規則的左手邊是否明確出現在AST中，如formdef,formbodydef,formdefList？
  • 我應該在節點中包含什麼？簡單地包括終端令牌類型（ID，NAME等）和令牌值是否足夠？
  • 我是否應該將所有標記值包含爲字符串，並在稍後階段執行實際類型轉換（如字符串到整數等）？

感謝您的諮詢！

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。