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

解释器在游戏领域的应用虽然解释器模式很少使用，但在在游戏开发中，还是很常见的。比方你在战斗 时，普通攻击和魔法攻击一定会产生不同的伤害，游戏设计者会为技能设计不 同的公式，简单如我方的攻击力敌方的防御力，同时公式还可以加入 参数，代表一个爆发率。故游戏的技能伤害如下列图所示：$atk*l -2*$critRate-Sdef魔法攻击State w (Satk+Smatk)* 1.2-(SdefH-Smdef)* 1. : «wvw, cnblogs OceanEyes游戏里的公式本质上是字符串，很像数学表达式，但又比它更高级，可以 加入自定义的参数，所以公式更像是数学表达式的超集。既然谈到了数学 表达式，那么有必要知道怎样去解析一个数学表达式。千万不要小看这个任务，实际上要做一个计算器是非常复杂的。假设输入一个字符串：-a+便+效注意这是一个字符串。解决方案有两种： while遍历字符串，将括号、运算符、数字等取出来，根据运算符左结合以及优先级计算throw new Exception(Illegal Token");)break;.）值得一提的事情，怎样从字符串中获取数字，数字有两种形式：整数和小数点形式，通过有穷自动机在不同的状态间跳转并记录下数字的索引下标，直到遇到非数字退出,有穷自动机如下所示：有穷自动机输入 : cnblogs. com/OceanEy es一个有穷自动机的状态判断代码如下：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;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: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 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, 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 _leftExpression. 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;可以看到左子树和右子树同样是Expression,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 = lexicalAnalyzer. 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 |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 expression;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 = 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. GetTokenO ;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+NumericConstantExpression30NumericConstantExpression30NumericConstantExpression20zOceaiiEyes小结本文为大家介绍了怎样从编译原理的角度来实现一个解释器。在游戏领域，需要解释器来解释自定义的 公式。这个公式的语法往往是和上下文无关的，又被称为BNF范式。解释器的核心就是怎样构建一棵抽象的表达式树，这需要词法分析和语法分析的相关知识。.将表达式转化成二叉树形式，二叉树的父节点是运算符，左右子节 点代表数字，通过递归遍历树，将左右节点的数字运算之后放入父 节点，直至到达根节点很显然第一种方式简单直白，但很繁重，代码的易读性也不佳，第二种是目前 最好的解决方式，将表达式转化为二叉树。所以难点在于怎样将表达式转化为 一棵二叉树？这需要了解数据结构相关知识，表达式-4+便+协4-9又被称为中序排序，中序排序不能生成一棵二叉 树，你需要将中序排序转化为前序排序或者后序排序，然后根据中序排序和前序排序生成二叉树，相关算 法自行搜索，不做累赘。我在阅读了编译原理第1 , 2章之后，还有另外一种方式将表达式生成二 叉树形式，这也是编译的基本原理。一个编译器的前端模型我们以最简单的算术表达式举例，编译器在分析阶段把一个字符序列分为各个 组成局部，最终生成一棵抽象语法树(abstract syntax tree),如下所示：解释器模型9-5+2词法分析器词法单元9 厂5+,2喑法分析器9语法分析树表达式语法定义 语法，顾名思义，是一种特定的描述方法。我们学习的英语语法，又或者是程序语言的语法，都有严格的格式要求。对于算术表达式而言，比方9-5+2, 3-2,语法是两个数字之间必须出现+ ,-,如果出现9+-5,那么这就是错误的语法。那我们怎么来制定语法呢？在编译原理领域，使用一个通用的表示方法来描述语法，这个方法就是上下文无关文法或BNF范式。比方上述的算术(+和-)表达式：9-5+2,我们可以推导出如下BNF范式：list- > Hst+digitllist-digitldigitdigit- > 0/1I2I3/4I5I6I7I8I9/克代表一个表达式序列，digit代球字,箭头。可以读作"可以具有如下形 式，而竖线|代表或的意思。词法分析器词法分析器读入源程序中的字符序列，将他们组织为具有词法含义的词素，生成并输出代表这些词素的词法单元(Token)。语法分析器 语法分析器根据词法单元，以语法分析树的形式构建表达式，最终形成一颗抽象的语法树(abstract syntax tree),这是一种表示了层次化的结构。语法分析树 如果非终端节点A有一个产生式/-那么在语法分析树中就可能有一个 标号为A的内部节点，该节点有三个子节点，从左向右标号为X , Y , Zo内部 节点对应于产生式的头，它的子节点对应于产生式的体：A. _ _ |x pY7Z I<B 一. I 、 jv, j jv ? jBNF范式构建数学表达式的特点运用编译原理的知识，编写一个自定义的解释器，我们需要如下三个步骤： BNF范式来描述游戏公式词法分析器获得词法单元Token ,对应的类是LexicalAnalyzer 语法分析器根据Token构建抽象树，对应的类是Parser我在一开始就提到过，游戏里的公式很像数学表达式，那么数学表达式有什么广泛和通用的特点？首先数学表达式由数字和运算符构成，并且运算符有左结合性和优先性： 结合性：依照惯例，9+5+2等价于(9+5)+2 , 9-5-2等价于(9-5)- 2。当一个运算分量，比方上述的5左右两侧都有运算符时，我们 需要一些规那么来决定哪个运算符被应用于该运算分量。我们说运算 符是左结合的，因为当一个运算分量左右两侧都有号 时，它属于其左边运算符。力，减，乘，除四种算术运算符都是左 4土A 一口 口 O.优先性：在算术中，乘法和除法比加法和减法具有更高的优先级。 因此在表达式9+5x2和9x5+2中，都是运算分量5首先参与x 塔算。算术表达式的BNF构建通过对数学表达式的了解，我们知道一个数学表达式有数字、运算符等组成， 并且运算符是左结合和有优先性，那怎样去构建它的BNF范式呢？我们创立两个非终结符号效"俵达成和term(项),分别对应这两个优先级 层次,并使用另一个非终结符号后或。磔另来生成表达式的基本单元。那什么是后ctor呢?我们可以将因子(factor)理解成不能被任何运算符分开的表达式。不能分开的意思是说当我们在任意 因子的任意一边放置一个运算符，都不会导致这个因子的任何局部别离出来，成为这个运算符的运算分 量。当然，因子本身作为一个整体可以成为该运算符的一个运算分量。如果这个因子是由一个括号括起来 的表达式，那么这个括号将起到保护其不被分开的作用。factor- > digitl(expr) digit- > 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）使用这个BNF范式时，一个表达式就是一个由+或-分割开来的项（term ）列表，而项是由x或者/分隔 的因子（factor）列表。请注意，任何由括号括起来的表达式都是一个因子。这个BNF范式的语法分析树为如下所示：Expr： 4+3*2 OceanEyes求值时，从root节点遍历二叉树，如果节点有子节点，递归的方式遍历下去, 直到是叶子节点为止，接着将左子树和右子树取得的值放入它们的根节点，最 后root节点的值就是表达式最终的值。开始实现解释器有了准备之后，接下来就是实现解释器，它可以解释游戏中的公式。1 .）创立一个数学表达式类MathExpression ,根据面向对象思想,它封装了数据和行为,由于篇幅有限，只展示其骨架：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. CurrentChar) 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;mathExpression. 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