loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

实现一种解释性脚本语言(四)

author: Kevin Lynx email: zmhn320#163.com date: 3.9.2009

语法分析

    语法分析接收词法分析阶段的token集合为输入,将这些没有关系的tokens整理为相互
之间有关系的结构。书面点的说法叫语法树。
    每一次让我写这些文绉绉的概念真让我受不了:D。

语法树

    语法树简单来说就是一个以token作为每个节点的树型结构。例如我们有表达式age =
age + 1;,在词法阶段它被整理为token集合:age, =, age, +, 1。那么在经过语法分析后
,这些tokens将被整理为大致如下的树形结构:
        =
      /   \
    age    +
         /   \
       age     1

    整理成这样的结构有什么好处?就kl解释器而言,最直接的好处就是我可以递归地解释
这棵树执行。例如:

    value compute( TreeNode *root )
    {
        /* child[0]保存结果值age,child[1]是那个+表达式 */
        return op_exp( root->child[1] );
    }

    value op_exp( TreeNode *node )
    {
        switch( node->op )
        {
            case '+':
            {
                /* + 表达式必然有左右操作数 */
                value left = factor( node->child[0] );
                value right = factor( node->child[1] );
                return left + right;
            }
        }
    }
    value factor( TreeNode *node )
    {
        switch( node->type )
        {
            case ID:
                /* 查找age的值 */
                return age;

            case CONST:
                /* 1 是常量 */
                return node->cvalue;
        }
    }

    如你所见,当我们完成了语法分析阶段,我们就可以完成我们的解释器了。后面我会单
独讲解下整个解释过程,包括每个模块是如何协作的。我不知道其他解释器是怎么做的,但
是我这样做,起码结果是对的。

如何整理出语法树?

    这里不得不提到所谓的BNF文法,很明显你还是无法从我这里获取编译原理里某个概念
的讲解。我这里提这个概念完全是方便我提到这个东西。
    每一种语言都有其自己的BNF文法,因为万恶的先知告诉我们,每一门语言都需要建立
其语法树。- -!
    就像词法分析一样,因为大部分语言的结构都差不多,所以我觉得词法分析和语法分析
基本上都没有任何特别之处。也就是说,别的语言的BNF你可以直接拿来改改用。
    抄个BNF如下:
    exp -> exp adop term | term
    addop -> + | -
    term -> term mulop factor | factor
    mulop -> *
    factor -> (exp) | number
    这个BNF用来描述一般的算数表达式(+-*/)。简单来说,一门语言的BNF就是用于描述该
语言所有语句的东西,包括if、while、函数定义之类。建议你google一下C语言的BNF,并
改造之用于你自己的语言。

    那么有了BNF之后,该如何整理出语法树呢?
    通常,我们的代码里都会直接有对应exp、term、addop之类的函数。按照我这句话的意
思,上面抄的BNF被翻译为程序代码后,就可能为:
    exp()
    {
        if( ... ) left = exp()
        right = term();
        left addop right;
    }
    term()
    {
        if( ... ) left = term()
        right = factor();
        left mulop right;
    }
    factor()
    {
        if( ... ) return exp();
        else return number;
    }

    (可能还会涉及到EBNF,用于处理重复和选择的一些情况---不用管这句话)

    每一个函数基本上都会返回一个树节点,当然,该节点下可能会有很多子节点。   

总结

    语法分析基本上就是以上信息。它将词法分析输出的token集合整理成一颗语法树。为
了整理出这棵语法树,你需要找一份用于描述你语言的BNF,然后根据BNF翻译成处理代码。

代码导读

    kl中的整个语法分析代码位于klparser.c/klparser.h中,其BNF基本上取自<编译原理与
实践>附录中的C_语言。

posted on 2009-03-09 11:12 Kevin Lynx 阅读(3334) 评论(3)  编辑 收藏 引用 所属分类: kl脚本实现编译原理

评论

# re: 实现一种解释性脚本语言(四) 2009-03-09 22:17 陈梓瀚(vczh)

你的结构没有考虑语法错误的处理办法。  回复  更多评论   

# re: 实现一种解释性脚本语言(四) 2009-03-09 22:26 Kevin Lynx

@陈梓瀚(vczh)
貌似是的,后面对于错误的处理,甚至最基本的错误报告(定位)都存在问题。对这块不熟,没管了。
  回复  更多评论   

# re: 实现一种解释性脚本语言(四) 2009-03-10 13:29 陈梓瀚(vczh)

@Kevin Lynx
见【http://www.cppblog.com/vczh/archive/2008/06/15/53373.html】  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理