目前，我正在学习有关分析，但我有点困惑，如何生成AST。 我写了一个解析器正确验证的表达是否符合语法（这是沉默的时候表达符合并抛出一个异常时，它不是）。 我在哪里可以从这里去建立一个AST？ 我发现我的建筑LL（1）语法分析器大量的信息，但随后事情打造AST很少。
我当前的代码（写的非常简单的红宝石，以及包括词法分析器和解析器）被发现这里在GitHub上： https://gist.github.com/e9d4081b7d3409e30a57
有人能解释我是如何从去什么我现在有一个AST？
另外，如果您不熟悉拼音，但要知道C，你能告诉我如何建立一个AST的在C代码递归下降解析维基百科的文章。
请注意，我不希望使用的解析器生成像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”，而不是“一”。
现在，让我们定义附加到第二个选择相匹配的规则回调。 这是非常相似的，除了它也有它传递的参数涉及：
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的很小部分常规的标记。
OK，所以我在这里再次（和不，这个答案已经无关Scintilla的本身，虽然这是一个编程语言/我的编译器设计的冒险，一次的一部分）。
你有没有考虑使用莱克斯 / Yacc的 ？ 这是它们的存在主要的原因是什么（=解析;编写词法分析器和解析器，因此，建路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; }
;
%%
旁注：很遗憾，我不能帮你红宝石什么具体的（因为我不仅是一个绝对的新手，但实际上-由于一些未知的原因-我恨它）; 但是，即使是在C，我希望这会给你一个粗略的想法... :-)
