用 ANTLR 做一个四则运算器

simonhc 2008-01-15

开始把 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 的功能确实很舒服,而且例子也多,嗯,以后就用它了。用 ANTLR 做一个四则运算器

相关推荐