我目前正在学习解析，但我对如何生成 AST 有点困惑。我编写了一个解析器，可以正确验证表达式是否符合语法（当表达式符合时它是沉默的，当它不符合时会引发异常）。我该从哪里开始构建 AST？我发现了很多关于构建我的 LL(1) 解析器的信息，但在构建 AST 方面却很少。
我当前的代码（用非常简单的 Ruby 编写，包括词法分析器和解析器）可以在 github 上找到：https ://gist.github.com/e9d4081b7d3409e30a57
有人能解释一下我是如何从目前拥有的东西变成 AST 的吗？
或者，如果您不熟悉 Ruby，但知道 C，您能否告诉我如何在递归下降解析维基百科文章中为 C 代码构建 AST。
请注意，我不想使用像 yacc 或 antlr 这样的解析器生成器来为我完成工作，我想从头开始做所有事情。
谢谢！
您需要将匹配的每个符号与构造树的那一小部分的回调相关联。例如，让我们采用一个相当常见的构造：嵌套函数调用。
a(b())
您在此处的终端令牌类似于：
您的非终结符号类似于：
显然，上述规则的第二种选择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 部分的例程中。
好的，所以我又来了（不，这个答案与 Scintilla 本身无关；虽然它曾经是我的编程语言/编译器设计冒险的一部分）。
你考虑过使用Lex / Yacc吗？这就是它们存在的主要原因（= 解析；编写 Lexers 和 Parsers，因此是构建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 中，我希望这会给你一个粗略的想法...... :-)