基于编译原理的计算器设计与实现样本.doc

资料内容仅供您学习参考，如有不当之处，请联系改正或者删除。基于编译原理的计算器设计与实现 首先看一下这个计算器的功能: CALC> set a = 1; b = 2CALC> set c = 3CALC> calc (10 + pow(b, c) * sqrt(4) - 135.0CALC> exit如上所示, 这个计算器的功能非常简单: 1. 用set命令设置上下文中的变量。 2. 用calc命令计算一个表示式的值。 3. 用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, 则我们写出的汇编代码如下( 行号是为下文解释代码方便而放上去的, 不是代码的一部分) : 点击(此处)折叠或打开 store 3store 2mulstore 1sub print 对这段代码的说明如下: 前两行向栈顶添加两个数字, 先压入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, 则我们写出的汇编代码如下( 行号是为下文解释代码方便而放上去的, 不是代码的一部分) : 点击(此处)折叠或打开 store 1store 4sqrtstore 3store 2powstore 10addmulsubprint 对这段代码的说明如下: 这段代码稍有点复杂, 但有前一段代码的经验, 我们能够看到, 所有的操作数的先后顺序是从右向左store的, 因此store指令的顺序是固定下来的, 剩下的关键是操作指令应该放在哪里。 操作指令也是有一个规律的, 即: 当前栈顶的数据刚刚好满足某运算时, 则操作指令就放在哪里, 如: store 1的时候没有任何操作的操作数都在栈中。 store 4的时候, 刚刚好sqrt的操作数都在栈中, 则此时加入sqrt指令。 store 3 store 2时, 刚刚好能够计算pow。 store 10之后, 就能够计算加法了, 因此此时加入add指令。 add计算完成之后, 再加上之前已计算完的sqrt指令, 则此时乘法的所有操作数都在栈中了, 则此时加入mul指令。 最后减操作也能够计算了, 则加上sub指令。 所有计算完成之后打印出结果。 在这个例子中, 我所说的”规律”其实就是”后缀表示式”。我们平常写的算术表示式是”中缀”的, 即符号在操作数中间, 如1 + 2, 的 + 在1和2中间, 转为后缀形式即为1 2 +这里因为我对于参数顺序的设计是与”正常”顺序相反的, 因此1 + 2对于这个汇编器来说, 其后缀形式就应该为2 1 +大家是能够按照这个规律, 相对简单的实现这个计算器只要做好词法分析就能够按照后缀表示式的规律直接由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的思路: 思路一: 直接静态代码来描述, 类似这样的方式把状态机的每个路径都描述出来: IF S = START AND c = 1 THEN S = INT . ELSIF ., 这样就能够输入运行了。 思路二: 表格驱动式的, 例如列出下面的表格即可知道哪个状态经过哪个输入之后到达哪个新的状态了下表的左标题是当前的状态, 上标题是在当前状态上的输入, 表格中的内容是经过路径到达的状态。 思路三: 结合前两个思路先写一个代码生成工具, 工具读取”思路二”中表格中的内容, 并生成”思路一”中的静态代码。0-9 . _a-zA-Z + - * / ( ) , START INT POINT ID ADD SUB MUL DIV LBT RBT COMMA INT INT NUMBER POINT NUMBER NUMBER NUMBER ID ID ID ADD SUB MUL DIV LBT RBT COMMA 下面举一下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     -> NODE2 NODE3NODE2     -> NODE4这个表示的意思是: NODE1为根节点, NODE1有两个子节点NODE2和NODE3, NODE2又有一个子节点NODE4。这样即可用文本的形式表示树形结构了。这种表示形式叫”巴科斯范式”, 英文简称为BNF下文中有需要表示这个名称的地方, 我就直接用BNF三个字母来代替了。下面我们看一下这个计算器的BNF( 对于复杂语言的BNF描述要写几十页, 但我们的计算器就只有这么几行) : 点击(此处)折叠或打开 exp     -> term exp     -> term + exp exp     -> term - exp term    -> factor term    -> factor * term term    -> factor / term factor  -> varName factor  -> number factor  -> - number factor  -> funCall factor  -> ( exp ) funCall -> funName ( params ) params  -> exp params  -> 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 的例子来讲语义分析, 这个表示式的语法树还是这个: 语法分析是构造语法树, 语义分析是读语法树, 因此语义分析的代码与语法分析的代码是相通的, 读这个语法树我们也是需要parseExp、 parseTerm、 parseFactor三个函数的, 只是这三个函数的参数不再是tokenList, 而是TreeNode, 返回值不再是 TreeNode, 而要返回ASM代码( 直接返回字符串文本即可不过直接返回一个字符串列表可能更好一些, 这样海汇编器直接收到的就是一个个的汇编表 示了) 。下面分别描述一下parseExp、 parseTerm、 parseFactor三个函数的逻辑: parseExp: 检查一下exp节点的子节点有几个, 如果只有一个, 则这一个一定是一个term结构, 则把这个节点传给parseTerm得到结果并返回即可; 如果有三个, 则对第三个参数调用parseExp得到一个asmCode, 把第一个参数传给parseTerm得到一串汇编指令, 并加到asmCode后面做为新的asmCode, 最后, 判断第二个参数是add还是sub, 直接向asmCode后面加上一个add指令或sub指令作为新的asmCode, 最后返回asmCode即可。 这里要说明一个在解析三个子节点的情况下为什么要从第三个开始, 然后第一个, 最后第二个呢? 是因为: 我们现在的汇编器的设计中, 指令要从本中取操作数, 因此要先把所有的操作数搞定才能搞写指令, 因此第二个操作数的处理要放到最后。 我们现在的汇编器的设计中, 操作数出栈的顺序是按我们正常表示式的从左到右的顺序, 因此入线的顺序就要从右到左, 因此第三个操作数先处理, 然后才是第一个。 parseTerm: 与parseExp也几乎是一样的, 也不赘述了。 parseFactor: 在语法解析中我们只将了这三个产生式: "factor -> number"和"factor -> - number"和"factor -> ( exp )", 因此在这里我们还是继续以此为例。 如果factor的第一个子节点是一个number类型, 则直接返回"store " + number指令即可。 如果factor的第一个子节点是一个sub类型, 则直接返回"store -" + number指令即可。 如果factor的第一个子节点是lbt类型, 则对第二个参数调用parseExp函数得到asmCode, 并返回asmCode即可因此时第三个操作数一定是rbt, 因此此时不论它也能够, 其实在语法分析时本就能够直接不构造lbt和rbt这两个节点的。 就这样, 我们就能够得到ASM代码了为了在控制台看到计算结构, 我们还要在ASM代码的结尾加一个print指令。最后我们要做的事情是调用已经存在的汇编器和虚拟机来运行了。 到现在所涉及到的技术对于处理复杂语言是远远不够, 但也足能够用这些知识来设计语法简单, 但功能强劲的语言解释器, 对于一般的领域特定语言的语法处理都是足够的了。以后有机会可能会再写其它的关于编译技术的文章。