从编译原理看一个解释器的实现.docx

《从编译原理看一个解释器的实现.docx》由会员分享，可在线阅读，更多相关《从编译原理看一个解释器的实现.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、解释器在游戏领域的应用虽然解释器模式很少使用，但在在游戏开发中，还是很常见的。比方你在战斗 时，普通攻击和魔法攻击一定会产生不同的伤害，游戏设计者会为技能设计不 同的公式，简单如我方的攻击力敌方的防御力，同时公式还可以加入 参数，代表一个爆发率。故游戏的技能伤害如下列图所示：$atk*l -2*$critRate-Sdef魔法攻击State w (Satk+Smatk)* 1.2-(SdefH-Smdef)* 1. : wvw, cnblogs OceanEyes游戏里的公式本质上是字符串，很像数学表达式，但又比它更高级，可以 加入自定义的参数，所以公式更像是数学表达式的超集。既然谈到了数学

2、表达式，那么有必要知道怎样去解析一个数学表达式。千万不要小看这个任务，实际上要做一个计算器是非常复杂的。假设输入一个字符串：-a+便+效注意这是一个字符串。解决方案有两种： while遍历字符串，将括号、运算符、数字等取出来，根据运算符左结合以及优先级计算throw new Exception(Illegal Token);)break;.）值得一提的事情，怎样从字符串中获取数字，数字有两种形式：整数和小数点形式，通过有穷自动机在不同的状态间跳转并记录下数字的索引下标，直到遇到非数字退出,有穷自动机如下所示：有穷自动机输入 : cnblogs. com/OceanEy es一个有穷自动机的状态

3、判断代码如下：doisEndOfString = mathExpression. IsEndOfString;currentChar = mathExpression. CurrentChar;switch ( currentState)(case State. Init:if (char. IsDigit(currentChar)(currentState = State. Integer;if (!isEndOfString)(mathExpression. CurrentIndex+;)else(Init状态非数字那么退出_currentState= State. Quit;)break

4、;case State. Integer:if (currentChar =.)(currentState = State. Float;输入小数点,状态转移到 Float if (!isEndOfString)(mathExpression. CurrentIndex+;elseif (! char. IsDigit (curr6ntehar) 既不是数字也不是小数currentstate = State. Quit;)else(if (!isEndOfString)mathExpression. Current 1 ndex+;/读取下个字符)break;case State. Float

5、:if (! char. IsDigit (currentChar) 非数字，退出(currentstate = State. Quit;)else(if (!isEndOfString)(mathExpression. CurrentIndex+;)break;case State. Quit:break; while (currentstate != State.Quit & !isEndOfString);3 .)通过语法解析器Parser构建表达式树，每个节点都是一个抽象Expressionpublic abstract class Expression public abstract

6、 double Evaluate(Context context);Expression根据类型不同有常量表达式，二元表达式,一元表达式等，一个常见的二元表达式如下：public class BinaryExpression:Expression(private Expression _leftExpression;private Expression _rightExpression;private Operator _operator;public BinaryExpression(Expression leftExpression,Expression righExpressio n,

7、Operator op)(_leftExpression = leftExpression;_rightExpression = righExpression;_operator = op;public override double Evaluate (Context context)(switch (_operator)(case Operator. Plus:return leftExpression. Evaluate(context) + rightExpression.Eva luate(context);case Operator. Minus:return _leftExpre

8、ssion. Evaluate(context) 一 _rightExpression.Eva luate (context);case Operator. Mui:return leftExpression. Evaluate(context) * _rightExpression. Eva luate(context);case Operator. Div:return _leftExpression. Evaluate(context) / _rightExpression. Eva luate(context);)return Double. NaN;可以看到左子树和右子树同样是Exp

9、ression,4 .)到目前为止，可以说是万事俱备，只欠东风了，这个东风就是怎么样去构建表达式树。的是,一个效就是一个由+或-分割开来的项(term )列表，而项是由x或者/分隔的因子(factor )列表。expr- expr+ term/expr- term/termprivate Expression Expr()(Token old;Expression expression = Term();while ( currentToken=Token. Add| | currentToken=Token.Sub)old = currentToken;currentToken = lexi

10、calAnalyzer. GetTokenO;Expression el = Expr();expression=new BinaryExpression(expression, el, old=Token. Add?Operator. P 1us:Operator. Minus);)return expression;term- term x factor/term/factor/factorprivate Expression TermO (Token old;Expression expression = Factor();while (_currentToken=Token. Mui

11、|currentToken二二Token, Div)(old 二 _currentToken;_currentToken = _lexicalAnalyzer. GetTokenO ；Expression el = TermO ;expression二new BinaryExpression(expression, el, old二二Token, Mul?Operator. M ul:Operator. Div);return expression;factor- digitl(expr)private Expression Factor()(Token token;Expression ex

12、pression;if (_currentToken=Token. Double)expression=new NumericConstant QlexicalAnalyzer. GetDigits();_currentToken = lexicalAnalyzer. GetTokenO;)else if (_currentToken 二二 Token. Param)expression=new Var();currentToken = lexicalAnalyzer. GetTokenO ;)else if ( currentToken=Token. OParen)currentToken

13、= lexicalAnalyzer. GetTokenO；expression = Expr();if ( currentToken!=Token. CParen)(throw new Exception(zzMissing Closing Parenthesisn，z);)currentToken = lexicalAnalyzer. GetTokenO;)else if( currentToken二二Token.AddcurrentToken二二Token.Sub)var old = currentToken;currentToken 二 _lexicalAnalyzer. GetToke

14、nO ;expression = Eactor();expression=new UnaryExpression(expression, old=Token. Add?Operator. Plus: Operator. Minus);elsethrow new Exception(，errorz，);return expression;最后生成的树结构如下所示:UnaryExpression-(10+(20+30)NumericConstantExpressionF翳一Binarv.Expression+NumericConstantExpression30NumericConstantExp

15、ression30NumericConstantExpression20zOceaiiEyes小结本文为大家介绍了怎样从编译原理的角度来实现一个解释器。在游戏领域，需要解释器来解释自定义的 公式。这个公式的语法往往是和上下文无关的，又被称为BNF范式。解释器的核心就是怎样构建一棵抽象的表达式树，这需要词法分析和语法分析的相关知识。.将表达式转化成二叉树形式，二叉树的父节点是运算符，左右子节 点代表数字，通过递归遍历树，将左右节点的数字运算之后放入父 节点，直至到达根节点很显然第一种方式简单直白，但很繁重，代码的易读性也不佳，第二种是目前 最好的解决方式，将表达式转化为二叉树。所以难点在于怎样将

16、表达式转化为 一棵二叉树？这需要了解数据结构相关知识，表达式-4+便+协4-9又被称为中序排序，中序排序不能生成一棵二叉 树，你需要将中序排序转化为前序排序或者后序排序，然后根据中序排序和前序排序生成二叉树，相关算 法自行搜索，不做累赘。我在阅读了编译原理第1 , 2章之后，还有另外一种方式将表达式生成二 叉树形式，这也是编译的基本原理。一个编译器的前端模型我们以最简单的算术表达式举例，编译器在分析阶段把一个字符序列分为各个 组成局部，最终生成一棵抽象语法树(abstract syntax tree),如下所示：解释器模型9-5+2词法分析器词法单元9 厂5+,2喑法分析器9语法分析树表达式语

17、法定义 语法，顾名思义，是一种特定的描述方法。我们学习的英语语法，又或者是程序语言的语法，都有严格的格式要求。对于算术表达式而言，比方9-5+2, 3-2,语法是两个数字之间必须出现+ ,-,如果出现9+-5,那么这就是错误的语法。那我们怎么来制定语法呢？在编译原理领域，使用一个通用的表示方法来描述语法，这个方法就是上下文无关文法或BNF范式。比方上述的算术(+和-)表达式：9-5+2,我们可以推导出如下BNF范式：list- Hst+digitllist-digitldigitdigit- 0/1I2I3/4I5I6I7I8I9/克代表一个表达式序列，digit代球字,箭头。可以读作可以具有

18、如下形 式，而竖线|代表或的意思。词法分析器词法分析器读入源程序中的字符序列，将他们组织为具有词法含义的词素，生成并输出代表这些词素的词法单元(Token)。语法分析器 语法分析器根据词法单元，以语法分析树的形式构建表达式，最终形成一颗抽象的语法树(abstract syntax tree),这是一种表示了层次化的结构。语法分析树 如果非终端节点A有一个产生式/-那么在语法分析树中就可能有一个 标号为A的内部节点，该节点有三个子节点，从左向右标号为X , Y , Zo内部 节点对应于产生式的头，它的子节点对应于产生式的体：A. _ _ |x pY7Z I digitl(expr) digit-

19、 0I112/3/4I5I6I7/8I9那什么是term呢？一个（不是因子）项（term ）是一个可能被高优先级的运算符x和/分开，但不能被低优先级运算符分开 的表达式。term- term x factor/term / factor/factor那什么是做”呢?一个（不是因子也不是项）的表达式可能被任何一个运算符分开。expr- expr+ term/expr- term/term因此最终得到的BNF范式是：expr- expr+ term/expr- term/termterm- term x factor/term/factor/factorfactor- digitl（expr）使用

20、这个BNF范式时，一个表达式就是一个由+或-分割开来的项（term ）列表，而项是由x或者/分隔 的因子（factor）列表。请注意，任何由括号括起来的表达式都是一个因子。这个BNF范式的语法分析树为如下所示：Expr： 4+3*2 OceanEyes求值时，从root节点遍历二叉树，如果节点有子节点，递归的方式遍历下去, 直到是叶子节点为止，接着将左子树和右子树取得的值放入它们的根节点，最 后root节点的值就是表达式最终的值。开始实现解释器有了准备之后，接下来就是实现解释器，它可以解释游戏中的公式。1 .）创立一个数学表达式类MathExpression ,根据面向对象思想,它封装了数据和

21、行为,由于篇幅有限，只展示其骨架：public class MathExpression(private readonly string expression;public int Currentindexpublic bool IsIndexOutOfRangepublic bool IsEndOfStringpublic char CurrentCharpublic char GetSpecificCharBylndex(int index) .)创立一个词法分析器Lexical Analyzer z获取对应的词法单元Token ：switch (_mathExpression. Curr

22、entChar) case +:token = Token. Add;_mathExpression. CurrentIndex+;break;case -:token = Token.Sub;_mathExpression. CurrentIndex+;break;case *:token=Token. Mui;_mathExpression. CurrentIndex+;break;case /:token = Token. Div;_mathExpression. CurrentIndex+;break;case (:token = Token. OParen;mathExpressio

23、n. CurrentIndex+;break;case ):token = Token. CParen;mathExpression. CurrentIndex+;break;case $:if ( mathExpression. GetSpecificCharByIndex( mathExpression. Currentindex + 1) =，c，)(mathExpression. CurrentTndex += 2;token = Token. Param;)else(mathExpression. CurrentIndex+;token=Token. Illegal;)break;default:if (char. IsDigit( mathExpression. CurrentChar)(token = GetDigitsFromString ();else if (char. IsLetter( mathExpression. CurrentChar)(token = GetSineCosineFromString(); else