原文地址: http://blog.chinaunix.net/uid-26750235-id-3146005.html
让语法树跑起来－－开篇（1）
(一)简介
在前面几章中，讲了很多关于抽象语法树的知识，有文字常量节点，一元运算符节点，语句与复合语句节点。但这些都还只是停留在设计层次，不能真正看到实实在在的效果。在这一章中，会看到一个真正能运算，但功能极弱的Redy语言，只支持文字常量与一元运算符。
(二)yacc
Redy语言使用文法工具yacc为其生成LALR(1)分析表，在linux系统上，yacc的GUN版本为bison ，ubuntu的用户可以通过以下命令安装：
代码1.1
sudo apt-get install bison
在安装后使用下面命令所yacc文件转换为.c文件
代码1.2
yacc 或者 bison
(三)yylex
yacc在处理filename.y的文件后，将会输出一个名为y.tab.c的C程序文件，文件含有名为yyparse()的语法分析程序。主程序main调用yyparse对源程序文件进行语法分析。
在语法分析程序yyparse运行时，需要一个名为yylex的词法公析程序对其支持，每当yyparse调用yylex时，yylex就从输入字符流中识别出一个单词，并将该单词的内部码通过return语句回送给yyparse。
在词法分析那部分，讲述怎么从输入字符流中识别单词，以及构造输入缓冲区的方法，且并实现了字符流扫描器，扫描器的任务就是从输入字符流中识别出一个接一个的单词。下面来看yylex函数；
代码1.3
/*filename yylex.c*/ int yylex() { int token=TOKEN_WS; while(token==TOKEN_WS) /*如果单词为空白符，则抛弃*/ { /*yl_scanner为扫描器*/ token=sc_next_token(yl_scanner); /*从扫描器中取出一个单词*/ /*replace TOKEN_ANNO by TOKEN_NEWLINE*/ if(token==TOKEN_ANNO) /*如果为注释，则用换行符代替*/ { token=TOKEN_NEWLINE; } if(token==TOKEN_ID) /*如果为标识符，则需要再判断，看其是否为关键字*/ { token=symbol_type(sc_token_string(yl_scanner)); } } if(token!=EOF) { /*在yacc中自定义终节符的内部编码需要大于257，TOKEN_BASE的值为258*/ token+=TOKEN_BASE; } return token; }
(四)YSP文件
(1)说明部分
在说明部分，需要对终结符，也就是Redy源文件单词的类型进行申明；需要说明文法的开始符号
代码4.1
/*filename grammar.y */ %{ #include"yylex.h" #include"ast_nodes.h" #include"parser.h" #include<rtype/rtype.h> #define YYSTYPE AstObject* /*定义文法符号的默认类型为AstObject* */ %} /* redy token follow enum REDY_TOKEN from lexical/token.h */ %token tUNKOWN tERR /*文字常量：整数，长整数，浮点数，字符串，标识符 */ %token tINTEGER tLONG tFLAOT tSTRING tID /*符号:, . ( ) [ ] */ %token tCOMMA tPERIOD tL_RB tR_RB tL_SB tR_SB /*运算符 = *= /= %= += -= >>= <<= ^= $= |= */ %token tASSIGN tAMUL tADIV tAMOD tAPLUS tAMINUS tALS tARS tAAND tAOR tAXOR /*运算符 * / % + - >> << & | ^ ~ */ %token tMUL tDIV tMOD tPLUS tMINUS tLS tRS tAND tOR tXOR tNegated /*运算符 < <= != == >= > */ %token tLT tLE tNE tEQ tGE tGT /*分隔符 ; 换行符*/ %token tSEMI tNEWLINE /* 关键字*/ %token kAND kAS kAttr kBREAK kCATCH kCLASS kCONTINUE kDO kELIF %token kELSE kEND kFINALLY kFOR kFROM kFUNC kIF kIMPORT kIN %token kINHRIT kNOT kOR kPRINT kTHEN kTO KTRY kVFUNC kWHILE %token kTRUE kFALSE %start AstTree %%
(2)规则部分
代码4.2
AstTree : stmts{parser_set_root($1);} ; stmts: stmt tNEWLINE { /*创建复合词句节点*/ AstNodeStmts* stmts=ast_create_stmts(); ast_addto_pending(STMTS_TO_AST(stmts)); AstNodeStmt* node=AST_TO_STMT($1); /*添加语句node作为其子语句*/ ast_stmts_add(stmts,node); $$=STMTS_TO_AST(stmts); } | tNEWLINE{...} | stmts stmt tNEWLINE{...} | stmts tNEWLINE {$$=$1} ; ; literal: tINTEGER { /*创建文字常量*/ BtInt* bi=bt_int_from_str(yl_cur_string()); /*创建文字常量结点*/ AstNodeLiteral* t=ast_create_literal(I_TO_R(bi)); /*把所有的节点用键表连接在一起，如果语法分析失败， 可以遍历到每一个节点，以释放内存*/ ast_addto_pending(LITERAL_TO_AST(t)); /*因为文字常量bi已交给文字常量节点，所以这里需要减少其引用计数*/ robject_release(I_TO_R(bi)); /*把AstNodeLiteral转换为父类AstObject*/ $$=LITERAL_TO_AST(t); } /*下面几个和上面一样，所以就不结出代码*/ | tLONG{ ... } | tFLAOT{...} | tSTRING{...} | kFALSE{...} | kTRUE{...} ; primary_expr: literal {$$=$1;} ; /*一元运算符推导式*/ unary_expr:primary_expr{$$=$1;} |tPLUS unary_expr { /*创建节点AstNodePositive，参数$2表示产生式右部第 2个文法符号unary_expr，做为AstNodePositive的子结点*/ AstNodePositive* node=ast_create_positive($2); /*把AstNodePositive转换成AstObject*/ AstObject* ab=POSITIVE_TO_AST(node); ast_addto_pending(ab); $$=ab; } /*一元运算符- ~ 与+ 的代码基本一样，所以不给出*/ |tMINUS unary_expr{...} |tNegated unary_expr{...} ; stmt: unary_expr { /*创建语句节点*/ AstNodeStmt* node=ast_create_stmt($1); ast_addto_pending(STMT_TO_AST(node)); $$=STMT_TO_AST(node); }
(五)语法树实例
下面来看一段小代码
代码5.1
"a" 2.3 +1 ~1 +-1
为其构造语法树为：
在前介绍复合语句AstNodeStmts时，说过它的执行方式为依次执行其下面的每一条子语句。现在把它改为不仅执行子语句，还输出其子语句的结果。找码描述为（注意这是伪代码）：
代码5.2
AstNodeStmts.execute() for node in AstNodeStmts.s_chirldren /*遍历每一个子语句*/ node.execute() /*执行子语句*/ value=reg0 /*子语句的执行结果存在寄存器reg0中*/ print value /*输出结果*/ endfor end
(六)主函数main
代码6.1
int main(int argc ,char** argv) { if(argc!=2) /*判断参数个数*/ { printf("usage %s \n",argv[0]); exit(-1); } Scanner* sc=sc_create(argv[1]);/*创建扫描器*/ if(sc==NULL) { printf("open file %s failed\n",argv[1]); exit(-1); } ast_machine_init(); /*初始代虚拟机*/ yl_set_scanner(sc); /*设置yylex的扫描器为sc*/ int ret; ret=yyparse(); /*解析源文件，并为其构造语法树*/ AstObject* root=0; if(ret!=0) /*解析失败*/ { printf("parse <%s> failed\n",argv[1]); goto error; } else /*解析成功*/ { printf("parse <%s> success\n",argv[1]); root=parser_get_root(); /*得到语法构根节点*/ ast_execute(root); /*执行根节点*/ } sc_destory(sc); ast_machine_exit(); ast_free(root); return 0; error: sc_destory(sc); ast_machine_exit(); return -1; }
(七)运行结果
关于上面的代码可以在文件夹 tutorial/syntax/run_unary中找到，进入该目录，对工程编译make，就会在目录bin中生成可执行文件redy.exe，在终端输入 ./redy.exe filename 就可以运行了。
下面来看一下效果吧
文件uexpr.r的内容为:
"unary int " ----4 ---4 -+-+4 ~~~4 ~~~~4 "unary long" ----4L ---4l -+-+4L ~~~4L ~~~~4L "literal" 1 2.3 33333333333333L "abcd" false true
运行 ./redy.exe uexpr.r 后结果为:
返回文档首页
附: 代码下载: git clone git://git.code.sf.net/p/redy/code redy-code
本章内容位于tutorial/syntax/run_unary中
