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

解释器在游戏领域的应用

虽然解释器模式很少使用，但在在游戏开发中，还是很常见的。比如你在战斗

时，普通攻击和魔法攻击一定会产生不同的伤害，游戏设计者会为技能设计不

同的『公式』，简单如我方的攻击力-敌方的防御力，同时『公式』还可以加入

参数，如$critRate 代表一个爆发率。故游戏的技能伤害如下图所示：

游戏里的『公式』本质上是字符串，很像数学表达式，但又比它更高级，可以

加入自定义的参数，所以『公式』更像是数学表达式的超集。既然谈到了数学

表达式，那么有必要知道怎样去解析一个数学表达式。

节点，直至到达根节点

很显然第一种方式简单直白，但很繁重，代码的易读性也不佳，第二种是目前

最好的解决方式，将表达式转化为二叉树。所以难点在于怎样将表达式转化为

一棵二叉树？

这需要了解数据结构相关知识，表达式-(1+(2+3)x4-5)又被称为中序排序，中序排序不能生成一棵二叉

树，你需要将中序排序转化为前序排序或者后序排序，然后根据中序排序和前序排序生成二叉树，相关算

法自行搜索，不做累赘。

我在阅读了《编译原理》第 1，2 章之后，还有另外一种方式将表达式生成二

叉树形式，这也是编译的基本原理。

一个编译器的前端模型

2，语法是两个数字之间必须出现+，-，如果出现 9+-5,那么这就是错误的语

那我们怎么来制定语法呢？在编译原理领域，使用一个通用的表示方法来描述

语法，这个方法就是上下文无关文法或 BNF 范式。

digit->0|1|2|3|4|5|6|7|8|9

list 代表一个表达式序列，digit 代表数字，箭头->可以读作“可以具有如下形

式”，而竖线|代表或的意思。

词法分析器

词法分析器读入源程序中的字符序列，将他们组织为具有词法含义的词素，生

成并输出代表这些词素的词法单元(Token)。

语法分析器

语法分析器根据词法单元，以语法分析树的形式构建表达式，最终形成一颗抽

象的语法树(abstract syntax tree)，这是一种表示了层次化的结构。

语法分析树