用 ANTLR 做一个四则运算器

　　开始把 D 的语法转换为 EBNF，发现 D 还支持中文变量名，也就是所谓的 UniversalAlpha，查看了一下 dmd front end 的源代码，检查字符是否 UniversalAlpha 的函数是这样的：

 

int isUniAlpha(unsigned u)
{
    static unsigned short table[][2] =
    {
 { 0x00AA, 0x00AA },
 { 0x00B5, 0x00B5 },
 { 0x00B7, 0x00B7 },
 ......
 ......
 ......
 { 0x3105, 0x312C },
 { 0x4E00, 0x9FA5 },
 { 0xAC00, 0xD7A3 },
    };
    if (u > 0xD7A3)
 goto Lisnot;

   // Binary search
    int mid;
    int low;
    int high;

  low = 0;
    high = sizeof(table) / sizeof(table[0]) - 1;
    while (low <= high)
    {
 mid = (low + high) >> 1;
 if (u < table[mid][0])
     high = mid - 1;
 else if (u > table[mid][1])
     low = mid + 1;
 else
     goto Lis;
    }

Lisnot:
    return 0;

Lis:
    return 1;
}

  

 

　　但是，怎么让 Grammatica 在分析过程中调用类似的函数，却是一点儿头绪也没有。虽然，理论上来说，用正则表达式，也可以表示上面的逻辑，不过，200多行的数据，要都转成正则表达式，不止运行速度慢，就只是转换的工作量，也让人不可接受。

 

　　而后，对于 D 中 string interger 和 float 的转换，再次发现 Grammatica 这种只用正则表达式的方式的严重不足，终于决定放弃 Grammatica。

 

　　本来，最好的办法其实是使用 dmd 的前端的源代码来解析，不过，几乎 1.6M 的代码，没有任何文档，都读过一遍的话，黄花菜都凉了。

 

　　一直不想用 ANTLR 的原因，是语法文件和嵌入的代码混编，看起来杂乱无章，但是 ANTLR 的强大和社区的活跃确实是很吸引人的。于是，决定用 ANTLR 来写 D Parser。（看到还有一个叫 coco/r 的生成器，据说比 ANTLR 清晰，不过也有语法能力不如 ANTLR 的问题，所以暂时也不考虑了。）

 

　　同样的，四则运算是一个比较好的例子，从 ANTLR 的主页的“五分钟教程”中，找到一个四则运算的语法文件，看了一下，不嵌入代码的话，还挺清晰的。既然用 ANTLR，就要体验一下它自动建立抽象语法树的能力，把那个语法文件做了一些修改，成为这个样子：

 

grammar SimpleCalc;

options {
    language=CSharp;
    output=AST;
    ASTLabelType=CommonTree;
}

tokens {
    PLUS     = '+' ;
    MINUS    = '-' ;
    MULT     = '*' ;
    DIV      = '/' ;
}

@members {
}

/*------------------------------------------------------------------
 * PARSER RULES
 *------------------------------------------------------------------*/

expr    : term ( ( PLUS^ | MINUS^ )  term )* ;
term    : factor ( ( MULT^ | DIV^ ) factor )* ;
factor  : NUMBER | '(' expr ')' -> expr ;

/*------------------------------------------------------------------
 * LEXER RULES
 *------------------------------------------------------------------*/

NUMBER     : (DIGIT)+ ;
WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+     { $channel = HIDDEN; } ;
fragment DIGIT    : '0'..'9' ;

  

 

　　做了修改的地方是，1.让它输出 AST，2.把运算符提取为根，3.支持括号。

 

　　生成文件后，在 Program 文件中加入创建分析器的代码，再加入深度优先的语法树访问函数，以及运算部分如下：

 

using System;
using System.Collections.Generic;
using System.Text;
using Antlr.Runtime;
using Antlr.Runtime.Tree;

namespace Expr
{
    class Program
    {
        private static Stack<int> numbers = new Stack<int>();

       static void Main(string[] args)
        {
            SimpleCalcLexer lex = new SimpleCalcLexer(new ANTLRFileStream(args[0]));
            CommonTokenStream tokens = new CommonTokenStream(lex);
            SimpleCalcParser parser = new SimpleCalcParser(tokens);

           try
            {
                CommonTree ct = (CommonTree)parser.expr().Tree;
                VisitTree(ct);
                Console.WriteLine("The result is: {0}", numbers.Pop());
                Console.Read();
            }
            catch (RecognitionException e)
            {
                Console.Error.WriteLine(e.StackTrace);
            }
        }

       static void VisitTree(ITree it)
        {
            for (int i = 0; i < it.ChildCount; i++)
            {
                ITree c = it.GetChild(i);
                VisitTree(c);
            }
            switch (it.Type)
            {
                case SimpleCalcLexer.PLUS:
                case SimpleCalcLexer.MINUS:
                case SimpleCalcLexer.MULT:
                case SimpleCalcLexer.DIV:
                    Operation(it.Text, numbers.Pop(), numbers.Pop());
                    break;
                case SimpleCalcLexer.NUMBER:
                    numbers.Push(int.Parse(it.Text));
                    break;
            }
        }

    static void Operation(string opCode, int v2, int v1)
        {
            int result;
            switch (opCode)
            {
                case "+":
                    result = v1 + v2;
                    break;
                case "-":
                    result = v1 - v2;
                    break;
                case "*":
                    result = v1 * v2;
                    break;
                case "/":
                    result = v1 / v2;
                    break;
                default:
                    throw new Exception();
            }
            Console.WriteLine("{1} {0} {2} = {3}", opCode, v1, v2, result);
            numbers.Push(result);
        }
    }
}

 

 

　　上面的代码，除了运算之外，还会把每一个计算步骤打印出来，在输入文件中输入“5-(3-2)+6*7”，编译运行程序，得到结果：

 

3 - 2 = 1
5 - 1 = 4
6 * 7 = 42
4 + 42 = 46
The result is: 46

 

　　ANTLR 帮助建立 AST 的功能确实很舒服，而且例子也多，嗯，以后就用它了。

评论

2 楼 梁利锋 2008-01-15  

也是。不过 C# 圈子好像没什么人气 

1 楼 oldrev 2008-01-15  

呵呵，老实说这4篇post其实应该发到 C# 圈子里