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

基于编译原理的计算器设计与实现一方面看一下这个计算器的功能：CALC>seta=1;b=2CALC>setc=3CALC>calc(10+pow(b,c))*sqrt(4)-135.0CALC>exit如上所示，这个计算器的功能非常简朴：用set命令设立上下文中的变量。用calc命令计算一个表达式的值。用exit命令退出计算器。我们把编译的重点放在calc命令后面的计算表达式的解析，其它的部分我们可以简朴解决（如set命令可以这样简朴解决：先按分号分隔得到多个赋值解决，再按等号分隔就可以在上下文中设立变量了，并不需要复杂的编译过程）。如上的演示例子中，我们使用编译技术解决的部分是(10+pow(b,c))*sqrt(4)-1，其它部分我们只使用简朴的文本解决。麻雀虽小，但五脏俱全，这个计算器包含编译技术中最必要的部分。虽然这次我们只是实现了一个计算器，但所使用的技术足以实现一个简朴的脚本语言的解释器了。这个计算器分为如下几个部分：词法分析：把表达式的文本，解析成词法元素列表(tokenList)。语法分析：把tokenList解析成语法树(syntaxTree)。语义分析：把语法树转成汇编语言的代码(asm)汇编器：把汇编代码翻译为机器码（字节码）。虚拟机：执行字节码。一般的编译步聚中不包含“汇编器”和“虚拟机”，而这里之所以包含这两个部分是由于：通常编译器会直接由中间代码生成机器码，而不是生成汇编代码，而这里我之所以要生成汇编代码的因素是“调试的时候汇编的可读性很好”，假如直接生成目的代码，则会非常难用肉眼来阅读。自己实现虚拟机的因素是：现有的机器（涉及物理机和虚拟机以及模拟器）的指令虽然也很丰富，但似乎都没有直接计算“乘方”或“开方”的指令，自已实现虚拟机可以任意设计计算指令，这样可以减少整个程序的复杂度。因汇编器与虚拟机并不是编译原理的部分，所以下文中并不会描述其实现细节，但由于计算器代码编译后的目的代码就是汇编代码，所以需要把汇编指令做一下说明（以下把这个汇编语言简称为ASM）。

ASM指令介绍指令助记符操作数指命说明storenumber把number放入栈顶add从栈顶取出两个数相加，并把结果压回栈中sub从栈顶取出一个数做为被减数，再取一个做为减数，相减之后的结果入栈mul从栈顶取出两个数相乘，并把结果入栈div从栈顶取出一个数做为除法的分子，再取出一个做为除法的分母，相除的结果入栈pow从栈顶取出一个数做为底，再取出一个做为幂，计算结果入栈sqrt从栈顶取出一个数，把这个数开平方后的结果入栈print在控制台打印栈顶的数字这个虚拟机是基于栈来设计的，所有的计算指令的操作数都从栈中取，store命令向栈顶添加数据。print指令用于打印当前栈顶的数据，在我们编译的汇编代码要做到：对的计算出结果，且计算完毕之后的结果要刚好在栈顶，这样最后调用一个print指令即可以控制台看到计算结果。ASM举例：例1，假如我们要计算1-2*3，则我们写出的汇编代码如下（行号是为下文解释代码方便而放上去的，不是代码的一部分）：点击(此处)折叠或打开store3store2mulstore1subprint对这段代码的说明如下：前两行向栈顶添加两个数字，先压入3再压入2，这样栈顶的数字是2，第二个数字是3。第三行mul会从栈顶弹出两个数字（2和3）计算乘法，并把结果（6）再压入栈中，此时栈中只有一个数字6。第四行向栈顶压入一个数字1，此时栈顶为1，第二个数字是6。第五行sub指令从栈顶取出两个数字，第一个数字1做为被减数，第二个数字6做为减数，即计算1-6，并把结果压入栈中，此时栈中只有一个数字-5。最后一行print指令不对栈做写操作，只读取栈顶的数字，并打印出来。在这里，我们用到两个运算，mul和sub，这两个运算都是二元运算，因我在设计指令的时候，先取出来的数字是第一个操作数，所以先压入的应当是第二个操作数，这也是为什么代码中先压入的是3，之后是2，最后才是1。例2，假如我们要计算(10+pow(2,3))*sqrt(4)-1，则我们写出的汇编代码如下（行号是为下文解释代码方便而放上去的，不是代码的一部分）：点击(此处)折叠或打开store1store4sqrtstore3store2powstore10addmulsubprint对这段代码的说明如下：这段代码稍有点复杂，但有前一段代码的经验，我们可以看到，所有的操作数的先后顺序是从右向左store的，所以store指令的顺序是固定下来的，剩下的关键是操作指令应当放在哪里。操作指令也是有一个规律的，即：当前栈顶的数据刚刚好满足某运算时，则操作指令就放在哪里，如：store1的时候没有任何操作的操作数都在栈中。store4的时候，刚刚好sqrt的操作数都在栈中，则此时加入sqrt指令。store3store2时，刚刚好可以计算pow。store10之后，就可以计算加法了，所以此时加入add指令。add计算完毕之后，再加上之前已计算完的sqrt指令，则此时乘法的所有操作数都在栈中了，则此时加入mul指令。最后减操作也可以计算了，则加上sub指令。所有计算完毕之后打印出结果。在这个例子中，我所说的“规律”其实就是“后缀表达式”。我们平常写的算术表达式是“中缀”的，即符号在操作数中间，如1+2，的+在1和2中间，转为后缀形式即为12+这里由于我对于参数顺序的设计是与“正常”顺序相反的，所以1+2对于这个汇编器来说，其后缀形式就应当为21+大家是可以按照这个规律，相对简朴的实现这个计算器——只要做好词法分析就可以按照后缀表达式的规律直接由tokenList生成汇编代码了——但我们的目的是用这个计算器的例子来讲编译，所以还是按步就班来讲。词法分析词法分析的目的是把一段文本分解成词法元素列表，例如(10+pow(2,3))*sqrt(4)-1，做词法分析之后会分解成如下几个词法元素：（10+pow(2,3))*sqrt(4)-1这里只是做了一次文本解决——在解决之前，我们手里有的东西就是一串字符组成的字符串，在解决之后，我们按照一定的“规则”分解为多个单词。算法是多种多样的，有发明力的程序员会想出各种办法来解决这个单词分解的问题。在编译原理中，普遍的方式是用如下一个状态转换图来实现的在图中，“椭圆形”的是状态，状态与状态之间有一条有方向的线，这个线代表从一个状态到另一个状态的途径，在这条线上面有一个花括号代表从前一个状态到达后一个状态的输入（为方便表达，0-9表达从0到9十个数字，a-z表达从a到z二十六个字母等），如从START状态开始，输入一个数字1，就会到达INT状态。图中蓝色的状态是终结状态，假如从START状态通过若干输入后到达终结状态，则这些输入的字符可合并为词法的合法单词——这里需要额外说明一点：在对输入进行匹配状态时采用贪婪方式，即：尽量输入更多的字符。在辨认到一个合法的词法单元之后，状态回到START继续辨认下一个元素，直到没有新的元素为止。这个状态转换图在编译原理中有一个专有名词称呼它“拟定有限状态自动机”，英文简称DFA。这里“拟定”的意思是每一个状态通过一个输入字符可以拟定只有一条途径到达另一个状态，“有限”的意思是，状态的个数是有限的。对于一个复杂语言的状态数量是这个状态机的几个数量级的大小。但我们现在的计算器只需要这几个状态就够了。通常的DFA会由工具读取正则方法描述而生成的，而不是直接手工构造，但对我们现在设计的计算器来说，其DFA非常小，手工构造是很方便的，所以就不用工具了。此外，假如使用工具的话，我这篇文章也不会使用现有的工具，而是自己实现一个工具。下面举个例子：我们有一个表达式12.3+abc，下面我来描述一下DFA的运营过程：定义一个变量s，来表达当前状态机所在的状态（初始时s=START）。输入第一个字符1，此时START状态可接受这个输入1，到达INT状态，则变量s赋值为INT状态，此时可看到INT状态的颜色是蓝色表达当前可辨认为一个合法的词法元素，但由于我们的规则是贪婪匹配，所以我们还要看看是否还可以匹配更多的字符。输入第二个字符2，此时INT状态也可以接受这人输入，并到达INT状态（转了一个圈又回到本来的状态），此时变量s赋值为INT状态。再输入第三个字符.，此时INT状态可接受.到达NUMBER状态，此时变量s赋值为NUMBER状态。此时我们再向前看一个字符+，此时的状态NUMBER无法接受这个字符了，同时我们可在看到NUMBER状态的颜色是蓝色的，表达当前状态可辨认一个合法的词法元素，即：从START开始到当前我们一共经历的输入为12.3，则这个单词做为第一个合法的词法元素。第一个词法元素辨认成功之后，变量s要回到START状态，并继续输入+，此时从START状态可到达ADD状态，且ADD状态并不允许接受任何输入，同时ADD状态的颜色也是蓝色的，则我们又辨认出第二个词法元素+。在辨认到第二个词法元素之后，变更s要回到START状态，并继续输入a，此时START状态可由a指向的途径到达ID状态，此时s赋值为新的状态ID。现在的情况与辨认NUMBER的情况类似，当前的状态也是终结状态，但按贪婪匹配的原则还要继续看看是否可以匹配到新的输入。后面的b和c都在ID一个状态里转圈，我就不在赘述了，这样我们就辨认到了最后一个词法元素abc了。用如上过程的方法可以辨认任何对的的算术表达式，但尚有几点需要特别说明：如何辨认错误：目前我见过的语言规范都在描述如何对的的编译一个语言，但没有一个规范有描述如何报错的，所以我们目前能做的是只要按正常的走法走不通了，那就是错了，就要报错，并尽也许提供具体的错误信息。对空白的辨认：我在DFA中并没有画辨认空白的部分，因素是对于计算器程序来说，空白完全没有用处，所以我只是在代码中直接忽略这个输入，以免状态机无法辨认空白，同时在辨认到词法元素之后，去掉单词前后的空白。对于某些语言来说，空白是故意义的，需要做为词法元素辨认出来，不能忽略掉。对于词法元素的表达：通常我们会用一个类型Token来表达一个词法元素，Token中有两个属性，一个用于表达这个Token的类型，另一个用于表达内容，只有数字与标记符才需要使用Token类型的内容属性，其它的类型由于同一类型只有一种表达的也许，所以就不需要再把内容保存下来了（如ADD的内容一定是+）。关于标记符：DFA中的ID状态用于辨认标记符，这里的标记符涉及自定义的变量，也涉及函数名。在DFA的设计过程中，我们可以选择把普通标记符与保存字做为不同的状态，也可以用使用同一个状态。我们现在的设计就使用了一个ID状态表达所有的标记符，而在辨认到一个ID之后，我们在看是否是一个保存字，这样在返回Token对象时设立不同的类型。对于INT和NUMBER：这个计算器的所有计算都使用的是double类型的数字，所在虽然我们的词法可以辨认到INT，但我们定义Token的类型时，就只定义一个NUMBER类型，INT或NUMBER状态拟定的单词都返回NUMBER这个类型的Token对象。前面的逻辑中有一个贪婪批配的原则，这个原则在某些语言的词法中会有一些特例不合用，例如在C++和JAVA中都有一个运算符“>>”，这个运算符代表右移，但在C++11标准中可以写出这样的代码std::vector<std::vector<int>>，在JDK5及以上版本也可以这样写List<List<Integer>>，这里假如按贪婪批配就错了。所以必须在词法分析中加入上下文的判断才干决定是按两个>来辨认还是按一个>>来辨认——上下文的判断是语法分析的部分了，但对于复杂的词法结构在没有一个统一的词法解析算法可以解决的情况下就得借助更高级的方法了。现在剩下的就是写代码了。假如我把代码贴在这里就太长了，不太合适。所以下面我只描述一下描述DFA的思绪：思绪一：直接静态代码来描述，类似这样的方式把状态机的每个途径都描述出来：IFS=STARTANDc=‘1’THENS=INT...ELSIF...，这样就可以输入运营了。思绪二：表格驱动式的，例如列出下面的表格即可知道哪个状态通过哪个输入之后到达哪个新的状态了——下表的左标题是当前的状态，上标题是在当前状态上的输入，表格中的内容是通过途径到达的状态。思绪三：结合前两个思绪——先写一个代码生成工具，工具读取“思绪二”中表格中的内容，并生成“思绪一”中的静态代码。[0-9].[_a-zA-Z]+-*/(),STARTINTPOINTIDADDSUBMULDIVLBTRBTCOMMAINTINTNUMBERPOINTNUMBERNUMBERNUMBERIDIDIDADDSUBMULDIVLBTRBTCOMMA下面举一下DFA返回的Token对象的类型：NUM，FUN，VAR，ADD，SUB，MUL，DIV，LBT，RBT，COMMA这里前三个与DFA的状态名不同：NUM代表INT状态和NUMBER状态两个状态辨认出的词法元素。FUN和VAR都是ID状态辨认出的元素，假如这个ID是一个函数名，则Token为FUN类型，否则即为VAR类型。其它类型与DFA的状态是一一相应的。最后说一下DFA的接口：假设DFA有一个方法叫做parse，则这个方法的参数只有一个字符串用于传入表达式即可。假如我们写的DFA是用于解析长文本的（而不仅仅是解析这个简短的算术表达式），则可以考虑参数为输入流。parse方法的返回可以考虑返回一个Token的游标，游标供语法分析程序调用；也可以考虑解析完所有的词法元素返回一个Token的列表。由于目前比较通用的语法分析算法只需要向前看一个Token对象，所以游标就足够了。由于语法分析程序有也许会把已读出来的Token放回去，下次再用，所以游标可考虑加一个putBack方法——也可以考虑不实现这个方法，而由语法分析程序自己缓存当前用不到的词法元素——假如DFA返回的是list就简朴一些，语法分析器可以前后前后移动offset即可。DFA返回list的方式实现虽然简朴一点，但对于要解析的数据非常大的情况就不合用了——特别数据是从网络上以流的方式传过来的，这样我们主线不知道什么时候这个流会结束，所以还是需要一个元素就返回一个元素的做法比较安全——对于我们现在做的计算器的程序来说，随便怎么做都可以了。语法分析语法分析是把词法分析过程返回的tokenList转换为语法树的过程。词法分析的结果是为语法分析服务的，语法分析自然也是为下一步的语义分析做准备的，在这一节中，我们只讲一下语法树是怎么构造的，下一节语义分析的部分再讲如何使用语法树。语法树是一个树形的数据结构，树的每个根节点表达一个语法结构，子节点表达构成根这个大语法结构的小语法结构。这样不断划分更小的语法结构直到无法再分的子节点，其实就是一个整体与部分的关系。因树形结构是要画图的，但我们通常的工具是文本工具，所以我们通常用类似以下文本形式来表达树形结构：NODE1

->

NODE2NODE3NODE2

->NODE4这个表达的意思是：NODE1为根节点，NODE1有两个子节点NODE2和NODE3，NODE2又有一个子节点NODE4。这样即可用文本的形式表达树形结构了。这种表达形式叫“巴科斯范式”，英文简称为BNF——下文中有需要表达这个名称的地方，我就直接用BNF三个字母来代替了。下面我们看一下这个计算器的BNF（对于复杂语言的BNF描述要写几十页，但我们的计算器就只有这么几行）：点击(此处)折叠或打开exp

->termexp

->term+

expexp

->term-

expterm

->factorterm

->factor

*

termterm

->factor/

termfactor

->varNamefactor

->numberfactor

->-

numberfactor

->funCallfactor

->(exp)funCall

->funName(params)params

->expparams

->exp,params下面对这个语法结构描述一下：exp为算术表达式，即为我们要分析的表达式整体。term是可做加法或减法的项。我们可看到exp有三行表达基结构，这三行是或的关系，即：exp也许是一个term，也也许是一个term加上一个exp，也也许是一个term减掉一个exp。也就是说，exp这个根节点的子节点也许只有一个节点，也也许有三个节点。factor是可做乘法或除法的项。term继续分解的过程与exp是完全同样的，这里就不再赘述。这里把加减法与乘除法分开为两种语法结构的因素是，乘法与除法的优先级高于加法与减法，按照我们现在的表达，在计算加法或减法之前必须先计算term，这样因term是先计算的，所以优先级就表达出来了。varName是变量名，number是数字，funCall是函数调用对于factor的组成部分就可理解为：可认为一个变量，或一个数字，或一个减号连着一个数字（负数），或一次函数调用，或用小括号括起来的表达式。funName是函数名，params是函数调用的参数。funCall的结构为：函数名后跟着一个括号，再跟着一个或多个参数，再跟着一个括回。params由两个产生式，因每个参数都可以是单独的算术表达式，所以一个exp节点即可表达一个参数，假如有多个参数，则exp后成要跟着一个逗号，之后再跟着其它的参数。这种表达方法相对于树形的表达来说，有一个优点，即：相对比较容易表达“或”，比如factor这个节点也许由变量名来表达，也也许由数字来表达，如也许是……，这样我们假如画图的话，如何表达多种也许中只选其中一种的情况呢？上面的表达是对语法结构的抽象表达，抽象的东西还是具体化为我们的代码中的数据结构的。我们的目的是把我们的算术表达式变成符合语法树描述的样子，举个例子来说：(1+2)*3转成语法语法树就是下图所示的样子：图中蓝色的部分为语法树的叶子节点，也就是不能再分解的节点。这些叶子节点正是词法分析部分的词法元素。下面我们看一下来看一下构造这个树的环节：上面的图中只有三种非叶子节点的类型（exp、term、factor）以及几个叶子节点的类型[number、*、+、(、)]，所以下面我只以这几个为例做一下描述，其它的节点类型的解析环节是类似的——因+*()这几个符号在描述中会不太好看，所以下文中我改用add、mul、lbt、rbt来表达。节点的类型：我们可认为每种节点类型单独创建一个类，如：exp类型的节点即为Exp类型的对象，term类型的节点即为Term类型的对象……也可以考虑只用一个类型TreeNode，而用Node中的一个属性type来表达不同的节点类型。我选择用第二种方式来表达节点的类型，这样对于子节点的表达也相对简朴的直接用一个list即可。对于number类型的节点，还需要一个属性来表达数字的内容，所以TreeNode类中除了type字段之外，还要有一个content字段——varName或funName类型也是需要content字段的，用于表达变量名或函数名。为每个非叶子节点写一个函数来解析这个语法结构，如：parseExp、parseTerm、parseFactor，由于我们每个语法结构（或子语法结构）都是TreeNode类型的对象为根的树，所以这几个函数的返回值类型为TreeNode。每个函数内的结构化代码与BNF中的描述可完全相应得上，比如：exp有三个产生式："exp->term"和"exp->term+exp"和"exp->term-exp"，则parseExp的代码可以按下面的环节来写：创建一个类TreeNode的对象expNode，并指定其类型为exp。调用parseTerm函数解析出expNode的第一个子元素termNode。向前看下一个词法元素（假如尚有下一个的话）：假如为add或sub类型的Token，则创建第二个子元素opNode（这个元素的类型为add或sub），之后再递归调用parseExp解析第三个子元素。假如不为add或sub类型的Token，则一定是犯错了。反回expNode。term有三个产生式："term->factor"和"term->factor*term"和"term->factor/term"，这三个产生式与exp的三个产生式是同一个格式的，所以代码也几乎是同样的。factor有五个产生式，但我们现在这个例子用不到变更和函数，所以只看其中的三个："factor->number"和"factor->-number"和"factor->(exp)"，则parseFactor的代码可以这样写：创建一个类TreeNode的对象factorNode，并指定其类型为factor。向前看一个词法元素：假如是num类型的Token，则创建一个number类型的TreeNode对象做为factorNode的子节点（这个节点的content值为当前这个Token的值）。假如是sub类型的Token，则再从tokenList中读出一个num，创建一个number类型的TreeNode做为factorNode的子节点（这个节点的content值为当前这个Token的值把符号位反过来）。假如是lbt类型的，则先创建一个lbt类型的TreeNode做为factorNode的第一个子节点，再调用parseExp函数来获得第二个子节点，再向前看一个Token，假如是rbt类型的，则创建一个rbt类型的Token做为第三个子节点（假如看到的不是rbt类型的就要报语法错误了）。返回factorNode。按上面描述的逻辑实现代码是要不了多少行代码就可以实现这个计算器的语法解析了。尚有两个funCall和params，这两个类型的解析与exp或term或factor差不多，就不再描述了。下面还要说一点额外的注意事项：我们现在写代码这种方式叫做LL(1)型，也叫递归向下型的语法分析，在这种语法分析方式中，我们总是先创建根节点，再创建子节点，在创建子节点时，我们总是由最左边的节点开始一个一个去创建（如parseExp中，我们先创建出来的就是expNode，然后再创建的是termNode，之后假如尚有元素的话就会创建opNode和下一个expNode），这种语法解析方式是最容易用代码实现的，所以我才使用这种方式来做，但这种解析方式有一个局限性：语法的BNF描述中不能有左递归。何为左递归呢？举个例子来说：exp的产生式中的两个"exp->term+exp"和"exp->term-exp"，假如改为"exp->exp+

term"和"exp->

exp-term"，也是对的，但按照这样的产生式来写代码时，第一个要解析的就不是term，则还是一个exp，要解析第一个TreeNode就要递归调用parseExp函数了，这样就会形成无限的递归了。所以我们在设计LL(1)型的文法描述时要避免左递归。LL(1)的文法设计在解析复杂的语言时会有语法描述上的局限性，如：C语言的一条语句开头假如为ABC，则这个ABC也许一个变量名，也也许是行号，此时必须再向前看一个Token才干知道应当使用哪个产生式，这就变成LL(2)型了——LL后面括号中的数字代表我们在辨认语法产生式时，要向前看几个Token——这样的语法解析的代码就复杂很多了。那么，有没有实现简单，且语法描述能力又强的解析方法呢？答案为：是有的。但本文只需要实现计算器的语法，就没有必要喧宾夺主来花费大量的篇幅来写其它的语法解析方式。以后假如有时间可专门再写一个博文来讲语法解析。语法分析有时也是要判断上下文的，比如：假设在C++代码中有这样的一句：f<A,B>(c);这句代码在没有上下文的情况下是不能判断是什么，它也许是一个函数调用（f是函数名，A和B是范形参数，c是函数的参数），也也许是一个逗号表达式（f，A，B，c都是变量或值，这一名就表达为f小于A，B大于c）——其实这是C++语法上的一个考虑不周之处，这给编译器的设计者带来了很大的麻烦，JAVA对于范型方法的调用就避免了C++的尴尬：JAVA中范型参数位置不在方法名与参数之间，而在方法名之前，如：<A,B>f(c)，这样就不会与其它的JAVA语法冲突了。从这也可看出，语法的设计对语法解析程序的编写影响是非常直接的。最后再讲一点稍微偏门一点的东西：上面讲的解析过程是正统的语法解析方式，用这样的方式来解析计算器的算术表达式有点杀鸡用牛刀的感觉。对于算术表达式的语法树可以用以更简朴的结构，例如：表达式(10+pow(2,3))*sqrt(4)-1的语法树可以表达成下面的图形：这个图显然比正统的语法解析方式的结果树要小很多——由于这个树中只有终结符号，exp、term、factor等非终结符号是不存在的。对于这样的语法树的语义分析也更简朴，后面讲语义分析时再讲一下如何解析这个袖珍版本的语法树。这个树的构造即：所有的叶子节点都是操作数，所有的根节点都是操作符——同时大家也可以注意到括号不见了，事实上括号在语法树中也是不必要的。至于这个语法树如何构造就留个悬念，不在这里讲了。语义分析语义分析是把语法树转成中间代码，再由中间代码转成目的代码。但对于简朴的分析来说，我们省略中间代码的环节，直接读语法树生成目的代码（目的代码即为前面讲过的ASM代码）。虽然对于复杂的语言来说语义分析这个部分是非常复杂，但对于语法与设计都很简朴的语言来说语义分析这个部分简直简朴到可以合并到语法分析的过程中去做了，只是我们现在的目的是用计算器的例子来讲编译过程，所以这个部分还是简朴讲一讲。我之所以说这个计算器的语义分析可以合并到语法分析中是由于计算器的结构中没有上下文的判断，所以语法分析不报错的话，语义分析就一定没有问题了。我们还是以在语法分析中的(1+2)*3的例子来讲语义分析，这个表达式的语法树还是这个：