[体验编译原理]编写简易计算器

2018-06-23 22:34:15来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Demo: CaculationTest

 

前言

有想过自己写一个计算器么?输入一些数学表达式就能自己计算解析生成结果。

如果没有,可以现在开始想想,也许你会发现自己计算要不了几秒钟的表达式,让程序计算却没这么简单。

本文以简化版的计算器为例,采用了编译原理的token解析及分析的方式,旨在让初学者了解和感受编译原理的基本思维。

【如果有一定的基础,可以阅读此文:http://www.codeproject.com/Articles/246374/A-Calculation-Engine-for-NET】

 

假定

为了便于理解,我们现在简化需求,数据类型只有整数,运算符只有加减乘除,没有括号。运行结果如图所示:

 

解析过程

逐个分析表达式字符串的每一个char,将其解析为一系列的token(记号)。然后根据token代表的不同含义进行相应的操作,直到计算出最终结果。

(本例中并没有全部解析完token,再遍历token,而是边解析边进行操作。这样做效率稍微高一点,但不能直接查看解析出来的全部token。)

这和我们阅读也比较接近:我们从左往右依次读取信息,读的过程中,我们会根据上下文即前后组成,形成一定的语义,如“其实不忍”,你可能会理解为”他实在不忍心“,或者理解为”他其实是不忍心的“,这得依照你对上下文的理解去选择了。

对照刚才的比喻,可以得出,token是语义的基本组成,或者说对字符组成的一种抽象。程序中将token抽象为以下数据结构:

 enum TokenType
   {
       Add,Sub,
       Mul,Div,
       Int,
       Start,End
   }

   class Token
   {
       public TokenType Type;
       public object Value;

       public Token(TokenType type , object value = null)
       {
           Type = type;
           Value = value;
       }
   }

 

 

Token和表达式

Token必须解析为表达式才会有意义。有了表达式,我们才能计算出最终结果。一个表达式,是能表示明确意义的一个或一组token。

在C#中,我们有一元表达式,二元表达式;表达式中有不同的运算,如加减法;在此例中,所有的表达式都可以计算出某个值,而且表达式之间可以相互计算形成新的表达式,如”表达式(1*2)+表达式(2*3)”。基于此,有Expression类,也并不复杂:

abstract class Expression
    {
        public abstract int GetValue();
    }

    class UnaryExpress : Expression
    {
        int _value;

        public UnaryExpress(int value)
        {
            _value = value;
        }


        public override int GetValue()
        {
            return _value;
        }
    }


    class BinaryExpression : Expression
    {
        TokenType _tokenType;
        int _left;
        int _right;


        public BinaryExpression(TokenType tokenType, Expression left, Expression right)
        {
            _tokenType = tokenType;
            _left = left.GetValue();
            _right = right.GetValue();
        }

        public override int GetValue()
        {
            switch (_tokenType)
            {
                case TokenType.Add:
                    return _left + _right;
                case TokenType.Sub:
                    return _left - _right;
                case TokenType.Mul:
                    return _left * _right;
                case TokenType.Div:
                    return _left / _right;
                default:
                    throw new Exception("unexceptional token!");
            }
        }
    }

 

此例中,并没有真正意义上的“一元表达式”,仅将数字看作它而已。二元表达式的值计算相对复杂,但类别也不多。

 

算法优先级

如果不算括号,恐怕对我们来说,用自己的“原始方式”解析表达式,最大的麻烦就是解决算法优先级的问题。

为什么“1+2*3” 不解析为1+2再乘以3呢,如何才能将其正确解析为2*3再和1相加呢?

首先我们需要顺序分析每个token, 表达式的解析顺序决定了最后的运算顺序,看下原代码中比较重要的这3个方法:

        //解析加减
        Expression ParseAddSub()
        {
            //左操作数为优先级较高的运算符
            var l = ParseMulDiv();
            while (_token.Type == TokenType.Add || _token.Type == TokenType.Sub)
            {
                var t = _token.Type;
                ParseToken();
                var r = ParseMulDiv();//解析右操作数
                l = new BinaryExpression(t, l, r);
            }
            return l;
        }

        //解析乘除
        Expression ParseMulDiv()
        {
            var l = ParseUnary();
            while (_token.Type == TokenType.Mul || _token.Type == TokenType.Div)
            {
                var t = _token.Type;
                ParseToken();
                var r=ParseUnary();
                l = new BinaryExpression(t, l, r);
            }
            return l;
        }

        //解析一元表达式(目前只有单个整数)
        Expression ParseUnary()
        {
            Expression ret = null;
            if (_token.Type == TokenType.Int)
            {
                ret= new UnaryExpress((int)_token.Value);
            }

            //解析完int后,移到下一个token处,即+-*/
            ParseToken();
            return ret;
        }

 

1*2+2*2,我们可以看作两个乘法表达式相加,所以,解析加法运算的左右操作符前,程序尝试读取其是否是乘法表达式。

如果是1+2*3呢,左操作符当乘法运算解析时,并没有匹配上,由最高优先级的一元表达式决定其值,返回1,所以左操作数就是1了,当解析到+时,程序尝 试解析右操作数,从优先级比加法高一级的乘除开始,往上搜索匹配。很明显,2*3命中了乘法表达式,计算出右操作数的结果后,再和1相加,结果就正确了。

 

练习

如果研究透了demo,可以尝试把括号,取模运算,一元表达式(正负号)。

 

扩展

在IL代码和LinqExpression API中,“表达式”,“二元表达式”,“赋值表达式”,“成员获取表达式(.运算)”等,都很常见,解析的表达后对应的操作也很多,新建实例,引用实 例,访问局部变量等,赋值等。有兴趣可以查看一下Dynamic Linq的原代码(后续章节中,我们会写一个简单易版的Dynamic Linq动态计算 IQueryable.Where(string))。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:使用Telerik控件搭建Doubanfm频道部分

下一篇:应用小算法