Какие моменты следует учитывать при создании абстрактного дерева синтаксиса

Question

Я работаю над простым языком игрушек для описания виджета пользовательского интерфейса. Я использовал bison/flex для реализации грамматики. Теперь я хотел бы создать АСТ из правил грамматики. Однако я не уверен в «уровне детализации» АСТ и о том, что должно быть включено в него. Из того, что я прочитал, АСТ должны быть «минимальными» и избегать предоставления избыточной информации. В то же время, очевидно, я не должен потерять информацию из исходного источника. Существуют ли конкретные правила для создания АСТ?

Грамматика приведен ниже:

%{ 

#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? Один узел АСТ на терминальный символ?
  • Как создать отношения между родителями и дочерними элементами между узлами?
  • В левой части правил грамматики, таких как formdef, formbodydef, formdefList, явным образом появляются в АСТ?
  • Что следует включать в узлы? Достаточно ли просто указать тип токена терминала (ID, NAME и т. Д.) И значение токена?
  • Должен ли я включать все значения токенов в виде строк и выполнять фактические преобразования типов, такие как строки, целые и т. Д. На более позднем этапе?

Спасибо за ваши советы!

Answer 1

Узлы должны содержать «абстрактную» синтаксическую категорию (что-то типично близко к LHS многих правил). См. https://stackoverflow.com/a/1916687/120163 для обсуждения AST и CST, и почему вы можете захотеть, чтобы узлы содержали конкретную категорию синтаксиса (например, именно LHS правил или конкретные имена листьев). Ссылка обсуждается, когда вы должны хранить терминалы в своем АСТ.

Они должны также содержать значения, если они представляют собой то, что изменяется таким образом, что грамматика не записывает (например, имена идентификаторов, числовые и строковые литералы константы и т.д.) См https://stackoverflow.com/a/6320259/120163 почему вы должны преобразовать значения, когда вы lex, не позднее.

Показаны здесь: https://stackoverflow.com/a/17393852/120163 - примеры того, как могут выглядеть АСТ, если вы распечатаете их (лучше создать принтер AST, чтобы помочь вам отлаживать их).

Сколько информации, необходимой для хранения в узле, зависит от того, что вы собираетесь с ней сделать в конечном итоге. Если вы хотите восстановить источник из AST, вам нужно сохранить много вещей, которые вы, возможно, никогда не рассматривали, например. радиус преобразованных чисел. См. https://stackoverflow.com/a/5834775/120163 для получения более подробной информации.