9

私は現在解析について学んでいますが、AST を生成する方法について少し混乱しています。式が文法に準拠しているかどうかを正しく検証するパーサーを作成しました (式が準拠している場合はサイレントになり、準拠していない場合は例外が発生します)。AST を構築するには、ここからどこに行けばよいですか? LL(1) パーサーの構築に関する情報はたくさん見つかりましたが、AST を構築するための情報はほとんどありませんでした。

私の現在のコード (非常に単純な Ruby で記述され、レクサーとパーサーを含む) は、github にあります: https://gist.github.com/e9d4081b7d3409e30a57

現在持っているものからASTに移行する方法を誰かが説明できますか?

または、Ruby に慣れていなくても C は知っている場合は、ウィキペディアの再帰降下解析の記事で、C コードの AST を構築する方法を教えてください。

注意してください、yacc や antlr のようなパーサー ジェネレーターを使用して作業を実行したくありません。すべてをゼロから実行したいのです。

ありがとう!

4

2 に答える 2

6

一致する各シンボルを、ツリーのその小さな部分を構築するコールバックに関連付ける必要があります。たとえば、かなり一般的な構成要素であるネストされた関数呼び出しを見てみましょう。

a(b())

ここでの端末トークンは次のようなものです。

  • L_PAREN = '('
  • R_PAREN = ')'
  • IDENTIFIER = [az]+

そして、あなたの非終端記号は次のようなものです:

  • FUNCTION_CALL = IDENTIFIER、L_PAREN、R_PAREN
  • また;
  • FUNCTION_CALL = IDENTIFIER、L_PAREN、FUNCTION_CALL、R_PAREN

明らかに、ルールの上記の 2 番目の選択肢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()上記のものを返す最初のコールバックを認識しますが、「a」ではなく「b」を使用します。

次に、2 番目の選択肢に一致するルールに関連付けられたコールバックを定義しましょう。渡された引数も処理することを除いて、非常に似ています。

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 の非常に小さな部分を構築するルーチンに渡します。

于 2012-04-12T12:40:47.087 に答える
0

OK、それで私は再びここにいます(そして、いいえ、この答えはScintilla自体とは何の関係もありません;それはかつて私のプログラミング言語/コンパイラ設計の冒険の一部でしたが)。

Lex / Yaccの使用を検討しましたか?それが彼らの存在の主な理由です(=構文解析;レクサーとパーサーを書くこと、したがってASTsを構築する方法)、そしてそれらは絶対に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; }
    ;

%%

補足:残念ながら、Ruby固有のことは何もできません(私はまったくの初心者であるだけでなく、実際には-何らかの理由で-嫌いです)。しかし、Cでも、これで大まかなアイデアが得られることを願っています... :-)

于 2012-04-23T05:46:00.467 に答える