基于编译原理的计算器设计实现分析

1、-. z.基于编译原理的计算器设计与实现首先看一下这个计算器的功能：CALC set a = 1; b = 2CALC set c = 3CALC calc (10 + pow(b, c) * sqrt(4) - 135.0CALC e*it如上所示，这个计算器的功能非常简单：用set命令设置上下文中的变量。 用calc命令计算一个表达式的值。 用e*it命令退出计算器。 我们把编译的重点放在calc命令后面的计算表达式的解析，其它的局部我们可以简单处理如set命令可以这样简单处理：先按分号分隔得到多个赋值处理，再按等号分隔就可以在上下文中设置变量了，并不需要复杂的编译过程。如上的演例如子中，

2、我们使用编译技术处理的局部是(10 + pow(b, c) * sqrt(4) - 1，其它局部我们只使用简单的文本处理。麻雀虽小，但五脏俱全，这个计算器包含编译技术中最必要的局部。虽然这次我们只是实现了一个计算器，但所使用的技术足以实现一个简单的脚本语言的解释器了。这个计算器分为如下几个局部：词法分析：把表达式的文本，解析成词法元素列表(tokenList)。 语法分析：把tokenList解析成语法树(synta*Tree)。 语义分析：把语法树转成汇编语言的代码(asm) 汇编器：把汇编代码翻译为机器码字节码。 虚拟机：执行字节码。 一般的编译步聚中不包含汇编器和虚拟机，而这里之所以包含

3、这两个局部是因为：通常编译器会直接由中间代码生成机器码，而不是生成汇编代码，而这里我之所以要生成汇编代码的原因是调试的时候汇编的可读性很好，如果直接生成目标代码，则会非常难用肉眼来阅读。 自己实现虚拟机的原因是：现有的机器包括物理机和虚拟机以及模拟器的指令虽然也很丰富，但似乎都没有直接计算乘方或开方的指令，自已实现虚拟机可以任意设计计算指令，这样可以降低整个程序的复杂度。 因汇编器与虚拟机并不是编译原理的局部，所以下文中并不会描述其实现细节，但因为计算器代码编译后的目标代码就是汇编代码，所以需要把汇编指令做一下说明以下把这个汇编语言简称为ASM。ASM指令介绍指令助记符 操作数 指命说明 st

4、orenumber把number放入栈顶add从栈顶取出两个数相加，并把结果压回栈中sub从栈顶取出一个数做为被减数，再取一个做为减数，相减之后的结果入栈mul从栈顶取出两个数相乘，并把结果入栈div从栈顶取出一个数做为除法的分子，再取出一个做为除法的分母，相除的结果入栈pow从栈顶取出一个数做为底，再取出一个做为幂，计算结果入栈sqrt从栈顶取出一个数，把这个数开平方后的结果入栈print在控制台打印栈顶的数字这个虚拟机是基于栈来设计的，所有的计算指令的操作数都从栈中取，store命令向栈顶添加数据。print指令用于打印当前栈顶的数据，在我们编译的汇编代码要做到：正确计算出结果，且计算完成

5、之后的结果要刚好在栈顶，这样最后调用一个print指令即可以控制台看到计算结果。ASM举例：例1，如果我们要计算1-2*3，则我们写出的汇编代码如下行号是为下文解释代码方便而放上去的，不是代码的一局部：点击(此处)折叠或翻开 store 3store 2mulstore 1sub print 对这段代码的说明如下：前两行向栈顶添加两个数字，先压入3再压入2，这样栈顶的数字是2，第二个数字是3。 第三行mul会从栈顶弹出两个数字2和3计算乘法，并把结果6再压入栈中，此时栈中只有一个数字6。 第四行向栈顶压入一个数字1，此时栈顶为1，第二个数字是6。 第五行sub指令从栈顶取出两个数字，第一个数字

6、1做为被减数，第二个数字6做为减数，即计算1-6，并把结果压入栈中，此时栈中只有一个数字-5。 最后一行print指令不对栈做写操作，只读取栈顶的数字，并打印出来。 在这里，我们用到两个运算，mul和sub，这两个运算都是二元运算，因我在设计指令的时候，先取出来的数字是第一个操作数，所以先压入的应该是第二个操作数，这也是为什么代码中先压入的是3，之后是2，最后才是1。 例2，如果我们要计算(10 + pow(2, 3) * sqrt(4) - 1，则我们写出的汇编代码如下行号是为下文解释代码方便而放上去的，不是代码的一局部：点击(此处)折叠或翻开 store 1store 4sqrtstore

7、 3store 2powstore 10addmulsubprint 对这段代码的说明如下：这段代码稍有点复杂，但有前一段代码的经历，我们可以看到，所有的操作数的先后顺序是从右向左store的，所以store指令的顺序是固定下来的，剩下的关键是操作指令应该放在哪里。 操作指令也是有一个规律的，即：当前栈顶的数据刚刚好满足*运算时，则操作指令就放在哪里，如： store 1的时候没有任何操作的操作数都在栈中。 store 4的时候，刚刚好sqrt的操作数都在栈中，则此时参加sqrt指令。 store 3 store 2时，刚刚好可以计算pow。 store 10之后，就可以计算加法了，所以此时参

8、加add指令。 add计算完成之后，再加上之前已计算完的sqrt指令，则此时乘法的所有操作数都在栈中了，则此时参加mul指令。 最后减操作也可以计算了，则加上sub指令。 所有计算完成之后打印出结果。 在这个例子中，我所说的规律其实就是后缀表达式。我们平常写的算术表达式是中缀的，即符号在操作数中间，如1 + 2，的 + 在1和2中间，转为后缀形式即为1 2 +这里因为我对于参数顺序的设计是与正常顺序相反的，所以1 + 2对于这个汇编器来说，其后缀形式就应该为2 1 +大家是可以按照这个规律，相对简单的实现这个计算器只要做好词法分析就可以按照后缀表达式的规律直接由tokenList生成汇编代码了

9、但我们的目的是用这个计算器的例子来讲编译，所以还是按步就班来讲。词法分析词法分析的目的是把一段文本分解成词法元素列表，例如(10 + pow(2, 3) * sqrt(4) - 1，做词法分析之后会分解成如下几个词法元素： 10+pow(2,3)*sqrt(4)-1这里只是做了一次文本处理在处理之前，我们手里有的东西就是一串字符组成的字符串，在处理之后，我们按照一定的规则分解为多个单词。算法是多种多样的，有创造力的程序员会想出各种方法来处理这个单词分解的问题。在编译原理中，普遍的方式是用如下一个状态转换图来实现的在图中，椭圆形的是状态，状态与状态之间有一条有方向的线，这个线代表从一个状态到另一

10、个状态的路径，在这条线上面有一个花括号代表从前一个状态到达 后一个状态的输入为方便表示，0-9表示从0到9十个数字，a-z表示从a到z二十六个字母等，如从START状态开场，输入一个数字1，就会到达 INT状态。图中蓝色的状态是终结状态，如果从START状态经过假设干输入后到达终结状态，则这些输入的字符可合并为词法的合法单词这里需要额外说明一点：在对输入进展匹配状态时采用贪婪方式，即：尽量输入更多的字符。在识别到一个合法的词法单元之后，状态回到START继续识别下一个元素，直到没有新的元素为止。这个状态转换图在编译原理中有一个专有名词称呼它确定有限状态自动机，英文简称DFA。这里确定的意思是每

11、一个状态经过一个输入字符可以确定只有 一条路径到达另一个状态，有限的意思是，状态的个数是有限的。对于一个复杂语言的状态数量是这个状态机的几个数量级的大小。但我们现在的计算器只需要 这几个状态就够了。通常的DFA会由工具读取正则方法描述而生成的，而不是直接手工构造，但对我们现在设计的计算器来说，其DFA非常小，手工构造是很方便的，所以就不用工具了。另外，如果使用工具的话，我这篇文章也不会使用现有的工具，而是自己实现一个工具。下面举个例子：我们有一个表达式12.3 + abc，下面我来描述一下DFA的运行过程：定义一个变量s，来表示当前状态机所在的状态初始时s = START。 输入第一个字符1，

12、此时START状态可承受这个输入1，到达INT状态，则变量s赋值为INT状态，此时可看到INT状态的颜色是蓝色表示当前可识别为一个合法的词法元素，但因为我们的规则是贪婪匹配，所以我们还要看看是否还能够匹配更多的字符。 输入第二个字符2，此时INT状态也可以承受这人输入，并到达INT状态转了一个圈又回到原来的状态，此时变量s赋值为INT状态。 再输入第三个字符 . ，此时INT状态可承受 . 到达NUMBER状态，此时变量s赋值为NUMBER状态。 此时我们再向前看一个字符 + ，此时的状态NUMBER无法承受这个字符了，同时我们可在看到NUMBER状态的颜色是蓝色的，表示当前状态可识别一个合法

13、的词法元素，即：从 START开场到当前我们一共经历的输入为12.3，则这个单词做为第一个合法的词法元素。 第一个词法元素识别成功之后，变量s要回到START状态，并继续输入 + ，此时从START状态可到达ADD状态，且ADD状态并不允许承受任何输入，同时ADD状态的颜色也是蓝色的，则我们又识别出第二个词法元素 + 。 在识别到第二个词法元素之后，变更s要回到START状态，并继续输入a，此时START状态可由a指向的路径到达ID状态，此时s赋值为新的状态ID。 现在的情况与识别NUMBER的情况类似，当前的状态也是终结状态，但按贪婪匹配的原则还要继续看看是否可以匹配到新的输入。 后面的b和

14、c都在ID一个状态里转圈，我就不在赘述了，这样我们就识别到了最后一个词法元素abc了。 用如上过程的方法可以识别任何正确的算术表达式，但还有几点需要特别说明： 如何识别错误：目前我见过的语言规都在描述如何正确的编译一个语言，但没有一个规有描述如何报错的，所以我们目前能做的是只要按正常的走法走不通了，那就是错了，就要报错，并尽可能提供详细的错误信息。 对空白的识别：我在DFA中并没有画识别空白的局部，原因是对于计算器程序来说，空白完全没有用处，所以我只是在代码中直接忽略这个输入，以免状态机无法 识别空白，同时在识别到词法元素之后，去掉单词前后的空白。对于*些语言来说，空白是有意义的，需要做为词法

15、元素识别出来，不能忽略掉。 对于词法元素的表示：通常我们会用一个类型Token来表示一个词法元素，Token中有两个属性，一个用于表示这个Token的类型，另一个用于表示 容，只有数字与标识符才需要使用Token类型的容属性，其它的类型因为同一类型只有一种表示的可能，所以就不需要再把容保存下来了如ADD的容 一定是+。 关于标识符：DFA中的ID状态用于识别标识符，这里的标识符包括自定义的变量，也包括函数名。在DFA的设计过程中，我们可以选择把普通标识符与保存字 做为不同的状态，也可以用使用同一个状态。我们现在的设计就使用了一个ID状态表示所有的标识符，而在识别到一个ID之后，我们在看是否是一

16、个保存字，这 样在返回Token对象时设置不同的类型。 对于INT和NUMBER：这个计算器的所有计算都使用的是double类型的数字，所在虽然我们的词法可以识别到INT，但我们定义Token的类型 时，就只定义一个NUMBER类型，INT或NUMBER状态确定的单词都返回NUMBER这个类型的Token对象。 前面的逻辑中有一个贪婪批配的原则，这个原则在*些语言的词法中会有一些特例不适用，例如在C+和JAVA中都有一个运算符，这个运算符代表右移，但在C+11 标准中可以写出这样的代码std:vectorstd:vector，在JDK5及以上版本也可以这样写 ListList，这里如果按贪婪批

17、配就错了。所以必须在词法分析中参加上下文的判断才能决定是按两 个来识别还是按一个来识别上下文的判断是语法分析的局部了，但对于复杂的词法构造在没有一个统一的词法解析算法可以处理的情 况下就得借助更高级的方法了。 现在剩下的就是写代码了。 如果我把代码贴在这里就太长了，不太适宜。所以下面我只描述一下描述DFA的思路： 思路一：直接静态代码来描述，类似这样的方式把状态机的每个路径都描述出来：IF S = START AND c = 1 THEN S = INT . ELSIF .，这样就可以输入运行了。 思路二：表格驱动式的，例如列出下面的表格即可知道哪个状态经过哪个输入之后到达哪个新的状态了下表的

18、左标题是当前的状态，上标题是在当前状态上的输入，表格中的容是经过路径到达的状态。 思路三：结合前两个思路先写一个代码生成工具，工具读取思路二中表格中的容，并生成思路一中的静态代码。0-9 . _a-zA-Z + - * / ( ) , START INT POINT ID ADD SUB MUL DIV LBT RBT MA INT INT NUMBER POINT NUMBER NUMBER NUMBER ID ID ID ADD SUB MUL DIV LBT RBT MA 下面举一下DFA返回的Token对象的类型：NUM，FUN，VAR，ADD，SUB，MUL，DIV，LBT，RBT，

19、MA这里前三个与DFA的状态名不同：NUM代表INT状态和NUMBER状态两个状态识别出的词法元素。 FUN和VAR都是ID状态识别出的元素，如果这个ID是一个函数名，则Token为FUN类型，否则即为VAR类型。 其它类型与DFA的状态是一一对应的。 最后说一下DFA的接口：假设DFA有一个方法叫做parse，则这个方法的参数只有一个字符串用于传入表达式即可。如果我们写的DFA是用于解析长文本的而不仅仅是解析这个简短的算术表达式，则可以考虑参数为输入流。 parse方法的返回可以考虑返回一个Token的游标，游标供语法分析程序调用；也可以考虑解析完所有的词法元素返回一个Token的列表。因为

20、目前比拟通用的语法分析算法只需要向前看一个Token对象，所以游标就足够了。 因为语法分析程序有可能会把已读出来的Token放回去，下次再用，所以游 标可考虑加一个putBack方法也可以考虑不实现这个方法，而由语法分析程序自己缓存当前用不到的词法元素如果DFA返回的是list就简单一 些，语法分析器可以前后前后移动offset即可。 DFA返回list的方式实现虽然简单一点，但对于要解析的数据非常大的情况就不适用了尤其数据是从网络上以流的方式传过来的，这样我们根本不知道什 么时候这个流会完毕，所以还是需要一个元素就返回一个元素的做法比拟平安对于我们现在做的计算器的程序来说，随便怎么做都可以了

21、。 语法分析语法分析是把词法分析过程返回的tokenList转换为语法树的过程。词法分析的结果是为语法分析效劳的，语法分析自然也是为下一步的语义分析做准备的，在这一节中，我们只讲一下语法树是怎么构造的，下一节语义分析的局部再讲如何使用语法树。语法树是一个树形的数据构造，树的每个根节点表示一个语法构造，子节点表示构成根这个大语法构造的小语法构造。这样不断划分更小的语法构造直到无法再分的子节点，其实就是一个整体与局部的关系。因树形构造是要画图的，但我们通常的工具是文本工具，所以我们通常用类似以下文本形式来表示树形构造：NODE1 -NODE2 NODE3NODE2 - NODE4这个表示的意思是：

22、NODE1为根节点，NODE1有两个子节点NODE2和NODE3，NODE2又有一个子节点NODE4。这样即可用文本的形式表示树形构造了。这种表示形式叫巴科斯式，英文简称为BNF下文中有需要表示这个名称的地方，我就直接用BNF三个字母来代替了。下面我们看一下这个计算器的BNF对于复杂语言的BNF描述要写几十页，但我们的计算器就只有这么几行：点击(此处)折叠或翻开 e*p - term e*p - term +e*p e*p - term -e*p term - factor term - factor*term term - factor /term factor - varName fact

23、or - number factor - -number factor - funCall factor - ( e*p ) funCall- funName ( params ) params - e*p params - e*p , params 下面对这个语法构造描述一下：e*p为算术表达式，即为我们要分析的表达式整体。 term是可做加法或减法的项。 我们可看到e*p有三行表示基构造，这三行是或的关系，即：e*p可能是一个term，也可能是一个term加上一个e*p，也可能是一个term减掉一个e*p。也就是说，e*p这个根节点的子节点可能只有一个节点，也可能有三个节点。 factor

24、是可做乘法或除法的项。 term继续分解的过程与e*p是完全一样的，这里就不再赘述。 这里把加减法与乘除法分开为两种语法构造的原因是，乘法与除法的优先级高于加法与减法，按照我们现在的表示，在计算加法或减法之前必须先计算term，这样因term是先计算的，所以优先级就表示出来了。 varName是变量名，number是数字，funCall是函数调用 对于factor的组成局部就可理解为：可以为一个变量，或一个数字，或一个减号连着一个数字负数，或一次函数调用，或用小括号括起来的表达式。 funName是函数名，params是函数调用的参数。 funCall的构造为：函数名后跟着一个括号，再跟着一个

25、或多个参数，再跟着一个括回。 params由两个产生式，因每个参数都可以是单独的算术表达式，所以一个e*p节点即可表示一个参数，如果有多个参数，则e*p后成要跟着一个逗号，之后再跟着其它的参数。 这种表示方法相对于树形的表示来说，有一个优点，即：相比照拟容易表示或，比方factor这个节点可能由变量名来表示，也可能由数字来表示，如可能是，这样我们如果画图的话，如何表示多种可能中只选其中一种的情况呢？上面的表示是对语法构造的抽象表示，抽象的东西还是具体化为我们的代码中的数据构造的。我们的目的是把我们的算术表达式变成符合语法树描述的样子，举个例子来说：(1 + 2) * 3转成语法语法树就是下列图

26、所示的样子：图中蓝色的局部为语法树的叶子节点，也就是不能再分解的节点。这些叶子节点正是词法分析局部的词法元素。下面我们看一下来看一下构造这个树的步骤：上 面的图中只有三种非叶子节点的类型e*p、term、factor以及几个叶子节点的类型number、*、+、(、)，所以下面我只以这几个为 例做一下描述，其它的节点类型的解析步骤是类似的因+*()这几个符号在描述中会不太好看，所以下文中我改用add、mul、lbt、rbt来表示。 节点的类型： 我们可以为每种节点类型单独创立一个类，如：e*p类型的节点即为E*p类型的对象，term类型的节点即为Term类型的对象 也可以考虑只用一个类型Tree

27、Node，而用Node中的一个属性type来表示不同的节点类型。 我选择用第二种方式来表示节点的类型，这样对于子节点的表示也相对简单的直接用一个list即可。 对于number类型的节点，还需要一个属性来表示数字的容，所以TreeNode类中除了type字段之外，还要有一个content字段varName或funName类型也是需要content字段的，用于表示变量名或函数名。 为每个非叶子节点写一个函数来解析这个语法构造，如：parseE*p、parseTerm、parseFactor，因为我们每个语法构造或子语法构造都是TreeNode类型的对象为根的树，所以这几个函数的返回值类型为Tre

28、eNode。 每个函数的构造化代码与BNF中的描述可完全对应得上，比方： e*p有三个产生式：e*p - term和e*p - term + e*p和e*p - term - e*p，则parseE*p的代码可以按下面的步骤来写： 创立一个类TreeNode的对象e*pNode，并指定其类型为e*p。 调用parseTerm函数解析出e*pNode的第一个子元素termNode。 向前看下一个词法元素如果还有下一个的话： 如果为add或sub类型的Token，则创立第二个子元素opNode这个元素的类型为add或sub，之后再递归调用parseE*p解析第三个子元素。 如果不为add或sub类

29、型的Token，则一定是出错了。 反回e*pNode。 term有三个产生式：term - factor和term - factor * term和term - factor / term，这三个产生式与e*p的三个产生式是同一个格式的，所以代码也几乎是一样的。 factor有五个产生式，但我们现在这个例子用不到变更和函数，所以只看其中的三个：factor - number和factor - - number和factor - ( e*p )，则parseFactor的代码可以这样写： 创立一个类TreeNode的对象factorNode，并指定其类型为factor。 向前看一个词法元素： 如

30、果是num类型的Token，则创立一个number类型的TreeNode对象做为factorNode的子节点这个节点的content值为当前这个Token的值。 如果是sub类型的Token，则再从tokenList中读出一个num，创立一个number类型的TreeNode做为factorNode的子节点这个节点的content值为当前这个Token的值把符号位反过来。 如果是lbt类型的，则先创立一个lbt类型的TreeNode做为factorNode的第一个子节点，再调用parseE*p函数来获得第二个子节 点，再向前看一个Token，如果是rbt类型的，则创立一个rbt类型的Token

31、做为第三个子节点如果看到的不是rbt类型的就要报语法错误了。 返回factorNode。 按上面描述的逻辑实现代码是要不了多少行代码就可以实现这个计算器的语法解析了。还有两个funCall和params，这两个类型的解析与e*p或term或factor差不多，就不再描述了。下面还要说一点额外的考前须知：我们现在写代码这种方式叫做LL(1)型，也叫递归向下型的语法分析，在这种 语法分析方式中，我们总是先创立根节点，再创立子节点，在创立子节点时，我们总是由最左边的节点开场一个一个去创立如parseE*p中，我们先创立出 来的就是e*pNode，然后再创立的是termNode，之后如果还有元素的话就

32、会创立opNode和下一个e*pNode，这种语法解析方式是最容 易用代码实现的，所以我才使用这种方式来做，但这种解析方式有一个局限性：语法的BNF描述中不能有左递归。何为左递归呢？举个例子来说：e*p的产生式 中的两个e*p - term + e*p和e*p - term - e*p，如果改为e*p - e*p +term和e*p -e*p - term，也是对的，但按照这样的产生式来写代码时，第一个要解析的就不是term，则还是一个e*p，要解析第一个TreeNode就要递归调用parseE*p函数了，这样就会形成无限的递归了。所以我们在设计LL(1)型的文法描述时要防止左递归。 LL(1

33、)的文法设计在解析复杂的语言时会有语法描述上的局限性，如：C语言 的一条语句开头如果为ABC，则这个ABC可能一个变量名，也可能是行号，此时必须再向前看一个Token才能知道应该使用哪个产生式，这就变成 LL(2)型了LL后面括号中的数字代表我们在识别语法产生式时，要向前看几个Token这样的语法解析的代码就复杂很多了。则，有没有实现简 单，且语法描述能力又强的解析方法呢？答案为：是有的。但本文只需要实现计算器的语法，就没有必要喧宾夺主来花费大量的篇幅来写其它的语法解析方式。以后 如果有时间可专门再写一个博文来讲语法解析。 语法分析有时也是要判断上下文的，比方：假设在C+代 码中有这样的一句：

34、f(c);这句代码在没有上下文的情况下是不能判断是什么，它可能是一个函数调用f是函数名，A和B是形参数，c是函数的参数，也可能是一 个逗号表达式f，A，B，c都是变量或值，这一名就表示为f小于A，B大于c其实这是C+语法上的一个考虑不周之处，这给编译器的设计者带来了很大的麻烦，JAVA对于型方法的调用就防止了C+的为难：JAVA中型参数位置不在方法名与参数之间，而在方法名之前，如： f(c)，这样就不会与其它的JAVA语法冲突了。从这也可看出，语法的设计对语法解析程序的编写影响是非常直接的。最后再讲一点稍微偏门一点的东西：上面讲的解析过程是正统的语法解析方式，用这样的方式来解析计算器的算术表达

35、式有点杀鸡用牛刀的感觉。对于算术表达式的语法树可以用以更简单的构造，例如：表达式(10 + pow(2, 3) * sqrt(4) - 1的语法树可以表示成下面的图形：这个图显然比正统的语法解析方式的结果树要小很多因为这个树中只有终结符号，e*p、term、factor等非终结符号是不存在的。对于这样的语法树的语义分析也更简单，后面讲语义分析时再讲一下如何解析这个袖珍版本的语法树。这个树的构造即：所有的叶子节点都是操作数，所有的根节点都是操作符同时大家也可以注意到括号不见了，实际上括号在语法树中也是不必要的。至于这个语法树如何构造就留个悬念，不在这里讲了。语义分析语义分析是把语法树转成中间代码

36、，再由中间代码转成目标代码。但对于简单的分析来说，我们省略中间代码的步骤，直接读语法树生成目标代码目标代码即为前面讲过的ASM代码。虽然对于复杂的语言来说语义分析这个局部是非常复杂，但对于语法与设计都很简单的语言来说语义分析这个局部简直简单到可以合并到语法分析的过程中去做了，只是我们现在的目的是用计算器的例子来讲编译过程，所以这个局部还是简单讲一讲。我之所以说这个计算器的语义分析可以合并到语法分析中是因为计算器的构造中没有上下文的判断，所以语法分析不报错的话，语义分析就一定没有问题了。我们还是以在语法分析中的 (1 + 2) * 3 的例子来讲语义分析，这个表达式的语法树还是这个：语法分析是构造语法树，语