让语法树跑起来－－开篇(1)

返回文档首页 

让语法树跑起来－－开篇（1）

(一)简介

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

(二)yacc

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

代码1.1

sudo apt-get install bison

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

代码1.2

yacc  filename.y
或者
bison  filename.y

(三)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中