Chinaunix首页 | 论坛 | 博客
  • 博客访问: 209401
  • 博文数量: 32
  • 博客积分: 424
  • 博客等级: 准尉
  • 技术积分: 465
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-02 10:23
文章分类

全部博文(32)

文章存档

2012年(32)

分类: Python/Ruby

2012-03-23 21:23:32

返回文档首页 

让语法树跑起来--开篇(1

()简介

在前面几章中,讲了很多关于抽象语法树的知识,有文字常量节点,一元运算符节点,语句与复合语句节点。但这些都还只是停留在设计层次,不能真正看到实实在在的效果。在这一章中,会看到一个真正能运算,但功能极弱的Redy语言,只支持文字常量与一元运算符。


()yacc

Redy语言使用文法工具yacc为其生成LALR(1)分析表,在linux系统上,yaccGUN版本为bison ubuntu的用户可以通过以下命令安装:

代码1.1

  1. sudo apt-get install bison

在安装后使用下面命令所yacc文件转换为.c文件

代码1.2

  1. yacc
  2. 或者
  3. bison

()yylex

yacc在处理filename.y的文件后,将会输出一个名为y.tab.cC程序文件,文件含有名为yyparse()的语法分析程序。主程序main调用yyparse对源程序文件进行语法分析。

在语法分析程序yyparse运行时,需要一个名为yylex的词法公析程序对其支持,每当yyparse调用yylex时,yylex就从输入字符流中识别出一个单词,并将该单词的内部码通过return语句回送给yyparse

在词法分析那部分,讲述怎么从输入字符流中识别单词,以及构造输入缓冲区的方法,且并实现了字符流扫描器,扫描器的任务就是从输入字符流中识别出一个接一个的单词。下面来看yylex函数;

代码1.3

  1. /*filename yylex.c*/
  2. int yylex()
  3. {
  4.         int token=TOKEN_WS;
  5.         while(token==TOKEN_WS) /*如果单词为空白符,则抛弃*/
  6.         {
  7.                 /*yl_scanner为扫描器*/
  8.                 token=sc_next_token(yl_scanner); /*从扫描器中取出一个单词*/

  9.                 /*replace TOKEN_ANNO by TOKEN_NEWLINE*/
  10.                 if(token==TOKEN_ANNO) /*如果为注释,则用换行符代替*/
  11.                 {
  12.                         token=TOKEN_NEWLINE;
  13.                 }
  14.                 if(token==TOKEN_ID) /*如果为标识符,则需要再判断,看其是否为关键字*/
  15.                 {
  16.                         token=symbol_type(sc_token_string(yl_scanner));
  17.                 }
  18.         }
  19.         if(token!=EOF)
  20.         { /*在yacc中自定义终节符的内部编码需要大于257,TOKEN_BASE的值为258*/
  21.                 token+=TOKEN_BASE;
  22.         }
  23.         return token;
  24. }


()YSP文件

(1)说明部分

在说明部分,需要对终结符,也就是Redy源文件单词的类型进行申明;需要说明文法的开始符号

代码4.1

  1. /*filename grammar.y */
  2. %{

  3. #include"yylex.h"
  4. #include"ast_nodes.h"
  5. #include"parser.h"
  6. #include<rtype/rtype.h>
  7. #define YYSTYPE AstObject* /*定义文法符号的默认类型为AstObject* */
  8. %}

  9. /* redy token follow enum REDY_TOKEN from lexical/token.h */

  10. %token tUNKOWN tERR
  11. /*文字常量:整数,长整数,浮点数,字符串,标识符 */
  12. %token tINTEGER tLONG tFLAOT tSTRING tID
  13. /*符号:, . ( ) [ ] */
  14. %token tCOMMA tPERIOD tL_RB tR_RB tL_SB tR_SB
  15. /*运算符 = *= /= %= += -= >>= <<= ^= $= |= */
  16. %token tASSIGN tAMUL tADIV tAMOD tAPLUS tAMINUS tALS tARS tAAND tAOR tAXOR
  17. /*运算符 * / % + - >> << & | ^ ~ */
  18. %token tMUL tDIV tMOD tPLUS tMINUS tLS tRS tAND tOR tXOR tNegated
  19. /*运算符 < <= != == >= > */
  20. %token tLT tLE tNE tEQ tGE tGT
  21. /*分隔符 ; 换行符*/
  22. %token tSEMI tNEWLINE

  23. /* 关键字*/
  24. %token kAND kAS kAttr kBREAK kCATCH kCLASS kCONTINUE kDO kELIF
  25. %token kELSE kEND kFINALLY kFOR kFROM kFUNC kIF kIMPORT kIN
  26. %token kINHRIT kNOT kOR kPRINT kTHEN kTO KTRY kVFUNC kWHILE
  27. %token kTRUE kFALSE

  28. %start AstTree
  29. %%

(2)规则部分

代码4.2

  1. AstTree : stmts{parser_set_root($1);}
  2. ;

  3. stmts: stmt tNEWLINE
  4.          {
  5.                 /*创建复合词句节点*/
  6.                 AstNodeStmts* stmts=ast_create_stmts();
  7.                 ast_addto_pending(STMTS_TO_AST(stmts));
  8.                 AstNodeStmt* node=AST_TO_STMT($1);
  9.                 /*添加语句node作为其子语句*/
  10.                 ast_stmts_add(stmts,node);
  11.                 $$=STMTS_TO_AST(stmts);
  12.          }
  13.          | tNEWLINE{...}
  14.          | stmts stmt tNEWLINE{...}
  15.          | stmts tNEWLINE {$$=$1}
  16. ;

  17.          ;
  18. literal: tINTEGER
  19.            {
  20.                 /*创建文字常量*/
  21.                 BtInt* bi=bt_int_from_str(yl_cur_string());
  22.                 /*创建文字常量结点*/
  23.                 AstNodeLiteral* t=ast_create_literal(I_TO_R(bi));
  24.                 /*把所有的节点用键表连接在一起,如果语法分析失败,
  25.                  可以遍历到每一个节点,以释放内存*/
  26.                 ast_addto_pending(LITERAL_TO_AST(t));
  27.                 /*因为文字常量bi已交给文字常量节点,所以这里需要减少其引用计数*/
  28.                 robject_release(I_TO_R(bi));
  29.                 /*把AstNodeLiteral转换为父类AstObject*/
  30.                 $$=LITERAL_TO_AST(t);
  31.            }
  32.           /*下面几个和上面一样,所以就不结出代码*/
  33.         | tLONG{ ... }
  34.         | tFLAOT{...}
  35.         | tSTRING{...}
  36.         | kFALSE{...}
  37.         | kTRUE{...}
  38. ;
  39. primary_expr: literal {$$=$1;}
  40.                         ;

  41. /*一元运算符推导式*/
  42. unary_expr:primary_expr{$$=$1;}
  43.                         |tPLUS unary_expr {
  44.                          /*创建节点AstNodePositive,参数$2表示产生式右部第
  45.                            2个文法符号unary_expr,做为AstNodePositive的子结点*/
  46.                         AstNodePositive* node=ast_create_positive($2);
  47.                         /*把AstNodePositive转换成AstObject*/
  48.                         AstObject* ab=POSITIVE_TO_AST(node);
  49.                         ast_addto_pending(ab);
  50.                         $$=ab;
  51.                         }
  52.                          /*一元运算符- ~ 与+ 的代码基本一样,所以不给出*/
  53.                         |tMINUS unary_expr{...}
  54.                         |tNegated unary_expr{...}
  55.                         ;

  56. stmt: unary_expr
  57.         {
  58.         /*创建语句节点*/
  59.         AstNodeStmt* node=ast_create_stmt($1);
  60.         ast_addto_pending(STMT_TO_AST(node));
  61.         $$=STMT_TO_AST(node);
  62.         }

()语法树实例

下面来看一段小代码

代码5.1

  1. "a"
  2. 2.3
  3. +1
  4. ~1
  5. +-1

为其构造语法树为:

在前介绍复合语句AstNodeStmts时,说过它的执行方式为依次执行其下面的每一条子语句。现在把它改为不仅执行子语句,还输出其子语句的结果。找码描述为(注意这是伪代码):

代码5.2

  1. AstNodeStmts.execute()
  2.     for node in AstNodeStmts.s_chirldren /*遍历每一个子语句*/
  3.         node.execute() /*执行子语句*/
  4.         value=reg0 /*子语句的执行结果存在寄存器reg0中*/
  5.         print value /*输出结果*/
  6.     endfor
  7. end

()主函数main

代码6.1

  1. int main(int argc ,char** argv)
  2. {
  3.         if(argc!=2) /*判断参数个数*/
  4.         {
  5.                 printf("usage %s \n",argv[0]);
  6.                 exit(-1);
  7.         }

  8.         Scanner* sc=sc_create(argv[1]);/*创建扫描器*/
  9.         if(sc==NULL)
  10.         {
  11.                 printf("open file %s failed\n",argv[1]);
  12.                 exit(-1);
  13.         }
  14.         ast_machine_init(); /*初始代虚拟机*/
  15.         yl_set_scanner(sc); /*设置yylex的扫描器为sc*/
  16.         int ret;
  17.         ret=yyparse(); /*解析源文件,并为其构造语法树*/
  18.         AstObject* root=0;
  19.         if(ret!=0) /*解析失败*/
  20.         {
  21.                 printf("parse <%s> failed\n",argv[1]);
  22.                 goto error;
  23.         }
  24.         else /*解析成功*/
  25.         {
  26.                 printf("parse <%s> success\n",argv[1]);
  27.                 root=parser_get_root(); /*得到语法构根节点*/
  28.                 ast_execute(root); /*执行根节点*/
  29.         }
  30.         
  31.         sc_destory(sc);
  32.         ast_machine_exit();
  33.         ast_free(root);
  34.         return 0;

  35. error:
  36.         sc_destory(sc);
  37.         ast_machine_exit();
  38.         return -1;
  39. }

()运行结果

关于上面的代码可以在文件夹 tutorial/syntax/run_unary中找到,进入该目录,对工程编译make,就会在目录bin中生成可执行文件redy.exe,在终端输入 ./redy.exe filename 就可以运行了。

下面来看一下效果吧

文件uexpr.r的内容为:

  1. "unary int "
  2. ----4
  3. ---4
  4. -+-+4
  5. ~~~4
  6. ~~~~4

  7. "unary long"
  8. ----4L
  9. ---4l
  10. -+-+4L
  11. ~~~4L
  12. ~~~~4L

  13. "literal"
  14. 1
  15. 2.3
  16. 33333333333333L
  17. "abcd"
  18. false
  19. true

运行 ./redy.exe uexpr.r 后结果为:

返回文档首页 

附:  代码下载: git clone git://git.code.sf.net/p/redy/code redy-code

本章内容位于tutorial/syntax/run_unary中


阅读(3743) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~