Как вручную построить AST?

Question

Как вручную построить AST?

В настоящее время я изучаю синтаксический анализ, но я немного запутался, как генерировать AST. Я написал синтаксический анализатор, который правильно проверяет, соответствует ли выражение грамматике (он молчит, когда выражение соответствует, и вызывает исключение, когда это не так). Куда мне идти отсюда, чтобы построить АСТ? Я нашел много информации о сборке моего LL(1) парсера, но очень мало потом собирал AST.

Мой текущий код (написанный на очень простом Ruby, включающий лексер и парсер) находится здесь на github: https://gist.github.com/e9d4081b7d3409e30a57

Может кто-нибудь объяснить, как я иду от того, что у меня есть в настоящее время к AST?

В качестве альтернативы, если вы не знакомы с Ruby, но знаете C, не могли бы вы рассказать мне, как я строю AST для кода C в статье в Википедии по анализу рекурсивного спуска.

Пожалуйста, обратите внимание, я не хочу использовать генератор синтаксических анализаторов, таких как yacc или antlr, чтобы сделать работу за меня, я хочу сделать все с нуля.

Спасибо!

9

ruby parsing abstract-syntax-tree lexer ll-grammar

Источник

user66725 12 апр '12 в 10:04

2 ответа

Решение

Хорошо, вот и я (и нет, этот ответ не имеет ничего общего со Scintilla как таковым; хотя когда-то он был частью моего приключения по языку программирования / разработке компиляторов).

Вы рассматривали возможность использования Lex / Yacc? Вот что является их основной причиной существования (= разбор; написание Lexers и парсеров, и, следовательно, способ построения AST s), плюс они абсолютно C-дружественные.

Вот грубый пример (взят из моего собственного открытого компилятора MathMachine).

mm_lexer.l (Лексер)

%{
/*
MathMachine
Copyright (C) 2009-2011 Dr.Kameleon

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>
*//*

MM_LEXER.L

*/

#include "mathmachine.h"

#include <stdio.h>
#include "y.tab.h"

void count();
%}

DIGIT           [0-9]
LETTER          [a-zA-Z_]
HEX         [a-fA-F0-9]
BINARY          [0-1]

%%
^[ \t]*"//".*\n             { /* This is a '//' single-line comment */ }
^[ \t]*"#!".*\n             { /* This is a '#!' single-line comment */ }
"use"                   { count(); return(USE); }
"set"                   { count(); return(SET); }
"let"                   { count(); return(LET); }
"ret"                   { count(); return(RET); }
"put"                   { count(); return(PUT); }
"get"                   { count(); return(GET); }
"if"                    { count(); return(IF); }
"else"                  { count(); return(ELSE); }
"loop"                  { count(); return(LOOP); }
"save"                  { count(); return(SAVE); }
"exec"                  { count(); return(EXEC); }


"true"                  { count(); return(TRUE); }
"false"                 { count(); return(FALSE); }

{LETTER}({LETTER}|{DIGIT})*     { count(); return(ID); }

{DIGIT}+                { count(); return(DECIMAL);     /* DECIMAL NUMBER */}
0"h"{HEX}+              { count(); return(HEXADECIMAL); /* HEXADECIMAL NUMBER */}
0"b"{BINARY}+               { count(); return(BINARY);  /* BINARY NUMBER */}  
{DIGIT}+"."{DIGIT}+         { count(); return(REAL);    /* REAL NUMBER */}

\"(\\.|[^\\"])*\"           { count(); return(STRING); }

"=="                    { count(); return(EQ_OP); }
"<="                    { count(); return(LE_OP); }
">="                    { count(); return(GE_OP); }
"<"                 { count(); return(LT_OP); }
">"                 { count(); return(GT_OP); }
"!="                    { count(); return(NE_OP); }

"-->"                   { count(); return(RANGE); }

"("                 { count(); return('('); }
")"                 { count(); return(')'); }
"{"                 { count(); return('{'); }
"}"                 { count(); return('}'); }
"["                 { count(); return('['); }
"]"                 { count(); return(']'); }

"-"                 { count(); return('-'); }
"+"                 { count(); return('+'); }
"*"                 { count(); return('*'); }
"/"                 { count(); return('/'); }

"="                 { count(); return('='); }
";"                 { count(); return(';'); }
","                 { count(); return(','); }
":"                 { count(); return(':'); }
"."                 { count(); return('.'); }
"?"                 { count(); return('?'); }
"%"                 { count(); return('%'); }
"&"                 { count(); return('&'); }
"$"                 { count(); return('$'); }
"#"                 { count(); return('#'); }
"@"                 { count(); return('@'); }
"|"                 { count(); return('|'); }
"!"                 { count(); return('!'); }
"~"                 { count(); return('~'); }
"^"                 { count(); return('^'); }

[ \t\v\n\f]             { count(); }
.                   { /* ignore it */ } 



%%

int yycolumn = 0;

void count()
{
    int i;

    for (i = 0; yytext[i] != '\0'; i++)
        if (yytext[i] == '\n')
            yycolumn = 0;
        else if (yytext[i] == '\t')
            yycolumn += 8 - (yycolumn % 8);
        else
            yycolumn++;

    // ECHO;
    yylval.str=strdup(yytext);
}

mm_parser.y (Парсер)

%{
/*
MathMachine
Copyright (C) 2009-2011 Dr.Kameleon

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>
*//*

MM_PARSER.Y

*/

#include "mathmachine.h"
#include <stdio.h>
#include <string.h>

void yyerror(const char *str)
{
    fflush(stdout);
    printf("\n%*s\n%*s\n", yycolumn, "^", yycolumn, str);
}

int yywrap()
{
    return 1;
}
%}

%union 
{
    char* str;
    mm_st_exec*         _st_exec;
    mm_st_use*          _st_use;
    mm_st_set*          _st_set;
    mm_st_ret*          _st_ret;
    mm_st_let*          _st_let;
    mm_st_get*          _st_get;
    mm_st_loop*             _st_loop;
    mm_st_if*           _st_if;
    mm_st_put*          _st_put;
    mm_st_save*         _st_save;
    mm_condition*           _condition;
    mm_argument*            _argument;
    mm_function_call*       _function_call;
    mm_expression_node*     _expression_node;
    mm_statement*           _statement;
    mm_statement_list*      _statement_list;
    mm_expression_list*     _expression_list;
    mm_id_list*         _id_list;
    comparison_operator_type    _comparison_op_type;
}

%token <str> SET LET PUT GET IF ELSE LOOP USE SAVE LOAD TIME RET EXEC
%token <str> ID DECIMAL HEXADECIMAL BINARY REAL STRING
%token <str> EQ_OP LE_OP GE_OP LT_OP GT_OP NE_OP RANGE
%token <str> TRUE FALSE

%type <str> number boolean 

%type <_comparison_op_type> comparison_operator

%type <_function_call> function_call

%type <_id_list> id_list

%type <_condition> condition
%type <_argument> argument

%type <_expression_node> expression

%type <_expression_list> expression_list

%type <_st_exec> exec_statement
%type <_st_use> use_statement
%type <_st_ret> ret_statement
%type <_st_let> let_statement
%type <_st_get> get_statement
%type <_st_loop> loop_statement
%type <_st_if> if_statement
%type <_st_put> put_statement
%type <_st_set> set_statement
%type <_st_save> save_statement

%type <_statement> statement

%type <_statement_list> statement_list block main

%left '+' '-'
%left '*' '/' '%'
%nonassoc UMINUS

%expect 11

%start main

%%

//---------------------------
// The Basic Elements
//---------------------------

number
    :   DECIMAL     { $$ = $1; }                
    |   HEXADECIMAL { $$ = $1; }            
    |   BINARY      { $$ = $1; }            
    |   REAL        { $$ = $1; }            
    ;

boolean
    :   TRUE        { $$ = $1; }
    |   FALSE       { $$ = $1; }
    ;

function_call
    :   ID '(' ')'          { $$ = new mm_function_call($1,NULL); }
    |   ID '(' expression_list ')'  { $$ = new mm_function_call($1,$3); }
    ;

argument
    :   number      { $$ = new mm_argument($1,number); }
    |   STRING      { $$ = new mm_argument($1,alpha); }
    |   boolean     { $$ = new mm_argument($1,boolean); }
    |   function_call   { $$ = new mm_argument($1,function); }
    |   ID      { $$ = new mm_argument($1,variable); }  
    ;

comparison_operator
    :   EQ_OP       { $$ = eq_operator; }
    |   LT_OP       { $$ = lt_operator; }
    |   GT_OP       { $$ = gt_operator; }
    |   LE_OP       { $$ = le_operator; }
    |   GE_OP       { $$ = ge_operator; }
    |   NE_OP       { $$ = ne_operator; }
    ;

//---------------------------
// The Building Blocks
//---------------------------

id_list
    :   ID              { $$ = new mm_id_list(); 
                          $$->addId($1); }                      
    |   id_list ',' ID          { $1->addId($3); $$=$1; }
    ;

expression
    :   argument                    { $$ = new mm_expression_node($1);  }
    |   '(' expression ')'              { $$ = $2;  }
    |   expression '+' expression           { $$ = new mm_expression_node(new mm_argument((char*)"+",oper),$1,$3,operator_node); }
    |   expression '-' expression           { $$ = new mm_expression_node(new mm_argument((char*)"-",oper),$1,$3,operator_node); }
    |   expression '*' expression           { $$ = new mm_expression_node(new mm_argument((char*)"*",oper),$1,$3,operator_node); }
    |   expression '/' expression           { $$ = new mm_expression_node(new mm_argument((char*)"/",oper),$1,$3,operator_node); }
    |   expression '%' expression           { $$ = new mm_expression_node(new mm_argument((char*)"%",oper),$1,$3,operator_node); }
    |   expression '^' expression           { $$ = new mm_expression_node(new mm_argument((char*)"^",oper),$1,$3,operator_node); }
    |   '-' argument %prec UMINUS           {  }
    ;

expression_list
    :   expression              { $$ = new mm_expression_list(); 
                              $$->addExpression(new mm_expression($1)); }                       
    |   expression_list ',' expression      { $1->addExpression(new mm_expression($3)); $$=$1; }
    ;

condition
    :   expression                  { $$ = new mm_condition(new mm_expression($1),empty_operator,NULL); }
    |   expression comparison_operator expression       { $$ = new mm_condition(new mm_expression($1), $2, new mm_expression($3)); }
    ;

//---------------------------
// The Statements
//---------------------------

exec_statement
    :   EXEC STRING ';'             { $$ = new mm_st_exec($2); }
    ;

use_statement
    :   USE STRING ';'              { $$ = new mm_st_use($2); /*printf("USE statement : %s\n",$2);*/ }
    ;

set_statement
    :   SET ID '(' id_list ')' '=' expression ';'   { 
                                    mm_st_ret* rt = new mm_st_ret(new mm_expression($7));
                                    mm_statement_list* stlist = new mm_statement_list();
                                    mm_statement* st = new mm_statement(ret_statement,rt);
                                    stlist->addStatement(*st);
                                    $$ = new mm_st_set($2,$4,stlist); 
                                }
    |   SET ID '(' id_list ')' '=' block        { $$ = new mm_st_set($2,$4,$7); }
    ;

let_statement
    :   LET ID '=' expression ';'           { $$ = new mm_st_let($2,new mm_expression($4)); }
    ;

get_statement
    :   GET ID ';'                  { $$ = new mm_st_get($2); }
    ;

ret_statement
    :   RET expression ';'              { $$ = new mm_st_ret(new mm_expression($2)); }
    ;

put_statement
    :   PUT expression_list ';'             { $$ = new mm_st_put($2); }
    ;

if_statement
    :   IF '(' condition ')' block          { $$ = new mm_st_if($3,$5,NULL); }
    |   IF '(' condition ')' block ELSE block       { $$ = new mm_st_if($3,$5,$7); }
    ;

loop_statement
    :   LOOP '(' condition ')' block            { $$ = new mm_st_loop($3,$5); }
    ;

save_statement
    :   SAVE expression_list '@' STRING ';'     { $$ = new mm_st_save($2,$4); }
    ;

statement
    :   exec_statement              { $$ = new mm_statement(exec_statement,$1); }
    |   use_statement               { $$ = new mm_statement(use_statement,$1); }
    |   set_statement               { $$ = new mm_statement(set_statement,$1); }
    |   let_statement               { $$ = new mm_statement(let_statement,$1); }
    |   get_statement               { $$ = new mm_statement(get_statement,$1); }
    |   ret_statement               { $$ = new mm_statement(ret_statement,$1); }
    |   put_statement               { $$ = new mm_statement(put_statement,$1); }
    |   if_statement                { $$ = new mm_statement(if_statement,$1); }
    |   loop_statement              { $$ = new mm_statement(loop_statement,$1); }
    |   save_statement              { $$ = new mm_statement(save_statement,$1); }
    ;

//---------------------------
// The Main Loop
//---------------------------

statement_list
    :   statement               { $$ = new mm_statement_list(); $$->addStatement(*$1); }
    |   statement_list statement        { $1->addStatement(*$2); $$ = $1; }
    ;

block 
    :   '{' statement_list '}'          { $$ = $2; }
    ;

main
    :   statement_list              { Base->Statements = $1; }
    ;

%%

Sidenote: К сожалению, я не могу помочь вам с чем-нибудь специфичным для Ruby (поскольку я не только абсолютный новичок, но на самом деле - по неизвестной причине - я ненавижу это); но, даже в C, я надеюсь, что это даст вам грубую идею...:-)

-1

Источник

user1270812 23 апр '12 в 05:46

Другие вопросы по тегам ruby parsing abstract-syntax-tree lexer ll-grammar

user322122 12 апр '12 в 12:40 2012-04-12 12:40 · Accepted Answer · 2012-04-12 12:40

Вам необходимо связать каждый соответствующий символ с обратным вызовом, который создает эту маленькую часть дерева. Например, давайте возьмем довольно распространенную конструкцию: вызовы вложенных функций.

a(b())

Ваши терминальные токены здесь выглядят примерно так:

L_PAREN = '('
R_PAREN = ')'
ИДЕНТИФИКАТОР = [az]+

И ваши нетерминальные символы являются чем-то вроде:

FUNCTION_CALL = IDENTIFIER, L_PAREN, R_PAREN
или же;
FUNCTION_CALL = IDENTIFIER, L_PAREN, FUNCTION_CALL, R_PAREN

Очевидно второй вариант выше для правила FUNCTION_CALL является рекурсивным

У вас уже есть парсер, который знает, что нашел верный символ. Недостаток, который вам не хватает, - это присоединение обратного вызова к правилу, которое получает его компоненты в качестве входных данных и возвращает значение (обычно), представляющее этот узел в AST.

Представьте себе, если первая альтернатива от нашего FUNCTION_CALL Правило выше имеет обратный вызов:

Proc.new do |id_tok, l_paren_tok, r_paren_tok|
  { item: :function_call, name: id_tok, args: [] }
end

Это будет означать, что AST в результате сопоставления:

a()

Было бы:

{
  item: :function_call,
  name: "a",
  args: []
}

Теперь, чтобы экстраполировать это на более сложный a(b()), Поскольку синтаксический анализатор является рекурсивным, он распознает b() во-первых, обратный вызов, из которого возвращается то, что мы имеем выше, но с "b" вместо "a".

Теперь давайте определим обратный вызов, прикрепленный к правилу, которое соответствует второму варианту. Это очень похоже, за исключением того, что оно также имеет дело с аргументом, который был передан:

Proc.new do |id_tok, l_paren_tok, func_call_item, r_paren_tok|
  { item: :function_call, name: id_tok, args: [ func_call_item ] }
end

Потому что парсер уже распознал b() и эта часть AST была возвращена из вашего обратного вызова, результирующее дерево теперь:

{
  item: :function_call,
  name: "a",
  args: [
    {
      item: :function_call,
      name: "b",
      args: []
    }
  ]
}

Надеюсь, это даст вам пищу для размышлений. Передайте все токены, которые вам соответствуют, в рутину, которая создает очень маленькие части вашего AST.