编译原理实用教程(Tsu版电子教案)doc.doc

第36页 共36页第1章 编译系统概述(Tsu版电子教案)第1章 编译系统概述翻译系统（编译系统）、操作系统、数据库管理系统是计算机的三大系统软件。1.1程序设计语言的发展机器语言汇编语言程序设计语言（高级语言）例计算表达式3*16+2的值，实现该计算的机器语言程序、汇编语言程序和高级语言（C语言）程序如下所示，该计算机的系统结构和汇编语言的使用方法详见本书第7章。2203 /16进制8210260261011000f000Load R0,3Mul R0,10 /10表示16Load R1,2Add R0,R1Write R0Haltvoid main(void) /C语言cout3*16+2;机器语言程序 汇编语言程序 高级语言程序1.2基本术语解释源语言和源程序文本文件目标语言和目标程序二进制文件翻译程序将源程序译成逻辑上等价的目标程序的程序，有二种翻译方式：编译和解释。解释方式以源程序作为输入，输入一句，解释执行一句，不产生完整的目标程序，相应的翻译程序称为解释程序，工作方式如下图所示： 解释、执行源 解释程序 结程 interpreter 果序输入数据编译方式将源程序全部译为目标程序，该目标程序可在操作系统环境下直接执行，相应的翻译程序称为编译程序，工作方式如下图所示：源程序ASCII码 二进制(整体未定位)二进制(整体定位)结果装入运行Run连接程序Link编译程序Compile编辑程序Edit 输入数据1.3编译过程概述编译程序工作过程相当复杂，从数据加工的角度来看，可将其分成4个逻辑阶段，它们是：l 词法分析l 语法分析l 语义分析（中间代码产生）l 目标代码生成图示如下：源程序 词法 语法 中间代码 目标代码 目标程序 分析 分析 产生 生成编译程序的结构基本上是按照这个流程来设计的。下面以算术表达式3+abc*128为例，来说明编译程序工作过程。词法分析执行词法分析任务的程序称为词法分析器。任务：字符串形式的单词 编码形式的单词内部码（二元式）依据：语言的构词规则二元式（单词种别，单词值）l 单词种别：用整数码表示（为直观起见用字符表示），语法分析时用。l 单词值：在本书中用字符串表示，语义分析时用。当一个单词种别中可能有多个单词时，单词的值才有意义。为了便于输入处理，无意义的单词值用NUL表示。二元式编码单词单词种别（字符形式）单词值（字符串形式）+NUL-NUL*NUL/NUL（NUL）NUL标识符i字符串形符号名整常数x字符串形式数字实常数y字符串形式数字经词分析，算术表达式3+abc*128的单词内部码（二元式）为：(x,3) (+,NUL) (i,abc) (*, NUL) (x,128)语法分析执行语法分析任务的程序称为语法分析器。任务：检查源程序的语法结构是否正确依据：语言的语法规则在语法分析时，算术表达式3+abc*128的语法结构应表示为x+i*x，语法分析器最终应识别出这是一个算术表达式，识别过程相当于建立一棵语法树。+ * x（整常数）x（整常数） i（标识符）语义分析执行语义分析任务的程序称为语义分析器或中间代码产生器。任务：建立符号表和常数表，记录源程序中标识符属性和常数值，根据语言的语义规定生成中间代码。依据：语言的语义内涵语义分析（中间代码产生）主要工作为：语义正确性检查和语义翻译。语义正确性检查例：beginreal a;integer a; end语法正确，语义错误，除非语言允许变量性质可动态修改。语义翻译1）说明语句的翻译 将标识符及其属性填入符号表。2）执行语句的翻译根据不同语句的语义，生成逻辑上等价的中间代码。l 中间代码结构简单、意义明确的记号系统，非常接近机器指令，但又独立于具体机器。常用的中间代码有三元式和四元式。表达式3+abc*128可译成如下四元式：(*,&abc,&128,&T1)(+,&3,&T1,&T2)其中，&abc表示标识符abc在符号表中入口；T1和T2是在翻译过程中由编译程序引入的临时变量；而&128表示常数128在常数表中的地址。l 符号表符号表用于记录源程序中出现的标识符，一个标识符往往具有一系列的语义值，它包括标识符的名称、标识符的种属、标识符的类型、标识符值的存放地址等等。每个标识符在符号表中有一项记录，用于记录标识符的各种语义值，而在四元式中填写的是标识符在符号表中的记录地址，通常称为符号表入口。符号表的结构示意如下：内存地址符号名种属类型未分配abc简单变量整型未分配T1简单变量整型未分配T2简单变量整型l 常数表常数表用于记录在源程序中出现的常数。假定，每个整常数在常数表中占2个字节，每个实常数在常数表中占4个字节。常数表的结构示意如下：常数的二进制值00000000-00000011（3）00000000-01000000（128）目标代码生成执行目标代码生成的程序称为目标代码生成器。任务：中间代码 目标代码（机器指令或汇编语言）依据：目标机器的系统结构上述算术表达式最终形成的汇编语言程序示意如下：Load R0,abcMul R0,128Store R0,T1Load R0,3Add R0,T1Store R0,T21.4出错处理编译程序在工作过程中可发现源程序中各种错误，错误类型及对策简述如下：错误类型l 词法错误l 语法错误l 语义错误出错处理l 一旦发现错误，暂停编译程序工作，指出错误的地点和类型。l 在发现错误后，不中断编译程序工作。采取某些措施（例错误局部化），使得源程序的编译工作可继续下去，尽可能发现源程序中比较多的错误。1.5编译程序的前端和后段编译程序前端组成：词法分析器、语法分析器和中间代码产生器特点：依赖于被编译的源语言，输出结果用中间代码描述，和目标机器无关。编译程序后端组成：目标代码生成器特点：和源语言无关，以中间代码形式的源程序为输入进行处理，输出结果依赖于目标机器。1.6编译程序的实现方式用机器指令或汇编语言手工编写用高级语言手工编写自编译方式自动构造词法分析器的自动构造输入词法规则，编译结果为词法分析器，例LEX系统。语法分析器的自动构造输入语法规则，编译结果为语法分析器，例YACC系统。第2章 词法分析词法分析任务2.1 词法分析器的设计考虑及手工构造2.1.1 单词类型及二元式编码单词类型基本字、标识符、常数、运算符、界符单词的性质l 个数确定和不确定l 单字符或多字符构成单词二元式编码经词法分析后，单词用二元式 (code,val) 表示。l code表示单词的种别，用整数码表示，在语法分析时使用。l val表示单词的值，在本书中用字符串表示，在语义分析时使用。编码原则通常将标识符归为一种，常数按类型分种，基本字、运算符及界符采用一符一种。实例设有某一程序设计语言，其部分单词二元式编码如下所示：单词单词种别（字符形式）单词值（字符串形式）integeraNULrealcNULbeginNULendNUL标识符i字符串形式符号名无符号整常数x字符串形式数字无符号实常数y字符串形式数字=NUL*NUL+NUL(NUL)NUL,NUL;NUL用该程序设计语言编制的计算园柱体表面积的源程序（输入输出略）如下所示：Begin/*S=2*3.14* R* R +2*3.14* R*H */Real r,h,s;s=2*3.14*r*(r+h)End根据单词二元式编码，上述程序的单词二元式序列应为：(,NUL)(c,NUL)(i,r)(,NUL) (i,h) (,NUL)(i, s)(;,NUL)(i, s)(=,NUL)(x, 2)(*,NUL)(y, 3.14)(*,NUL) (i, r)(*,NUL) (,NUL)(i, r)(+,NUL)(i, h)(),NUL)(,NUL)2.1.2 源程序的输入及预处理源程序的输入l 分段读入处理（早期）l 全部读入后处理设源程序如下所示，其中为续行符。源程序读入后，输入缓冲区的内容如下所示：Begin/*S=2*3.14*R*R+2*3.14*R*H*/ntRealr,h,s;nts=2*3.n14*r*(r+h)nEndn000预处理词法分析器通常由二个部分构成：预处理程序扫描器（单词识别程序）分成二部分的理由预处理主要工作上述源程序经预处理后，扫描缓冲区中的内容如下所示：beginrealr,h,s;s=2*3.14*r*(r+h)end0.0预处理程序例2.1.3 基本字的识别和超前搜索程序设计语言单词以基本字识别最为困难，原因如下：有些语言对基本字不加保护，用户可用作普通标识符。基本字、用户定义的标识符和常数之间没有分隔符。解决办法：所有基本字均为保留字(Reserved word)，用户不得使用它们作为标识符。将空格、TAB和换行符视为界符。在基本字、用户定义的标识符和常数之间，若没有运算符或界符，则至少用一个空格（或TAB、换行符）加以分隔。2.1.4 遍遍的基本概念遍引入的历史背景遍和编译程序的结构2.1.5 状态转换图和词法分析器的手工构造引入状态转换图的必要性状态转换图基本概念及应用例1，识别标识符的状态转换图如下所示： 字母数字 空格 字母非字母数字 *例2，识别实常数和整常数的状态转换图如下所示： 空格 数字 数字 数字 小数点 非数字* 非数字非小数点小数点* 数字 数字 非数字* 非数字（出错）例3，识别#、+和+的状态转换图。空格 +# 非+*利用状态转换图识别单词状态转换图每次只能识别一个单词，若源程序中有N个单词，则需使用状态转换图N次。设源程序为x+y#（#是预处理程序添加的），单词识别程序（扫描器）共使用状态转换图5次。1) 从初态0出发，读入x进入状态1，在状态1读入+，进入终态2，识别出标识符x，退回+；2) 从初态0出发，读入+进入状态10，在状态10读入+，进入终态11，识别出运算符+；3) 从初态0出发，读入+进入状态10，在状态10读入y，进入终态12，识别出运算符+，退回y；4) 从初态0出发，读入y进入状态1，在状态1读入#，进入终态2，识别出标识符y，退回#；5) 从初态0出发，读入#进入状态13，识别出单词#，识别出单词#意味着整个源程序中字符处理完毕。根据状态转换图编制程序2.2正规式、自动机及词法分析器的自动生成2.2.1 基本概念有穷字母表符号有限集，它的每个元素称为字符。字（字符串）上字符所构成的有限序列。空字*（集合的）积运算（集合的）闭包（集合的）正则闭包2.2.2 正规式与正规集正规式和正规集的定义：l 和是上的正规式，相应的正规集为、。l 若a，则a是正规式，相应正规集为a。l 若、为正规式，相应正规集分别记为L()和L()，则|是正规式，其相应正规集记为L(|) ，且令L(|)=L()L()。l 若、为正规式，相应正规集分别记为L()和L()，则(或)是正规式，其相应正规集记为L()，且令L()=L()L()。正规式自身的n次积是正规式，记为n，其相应正规集记为L(n)，显然L(n)= L() n。l 若为正规式，相应正规集记为L()，则*= 0|1|2|n是正规式，规定0 =，其相应正规集记为L(*)，且令L(*) =L() *。l *，可用园括号改变运算顺序。正规式相等原理二个正规式是相等的，当且仅当二个正规式所表示的正规集是相等的。正规式满足下列关系交换律：| = |结合律：|(|) = (|)|，() = () 分配律：(|) = |，(|) = | = = 2.2.3 确定有限自动机（DFA）DFA定义一个确定有限自动机M是一个五元式M = ( S，f，s0，Z )l S是一个有限集，它的每一个元素称为状态。l 是一个有穷字母表，它的每个元素称为一个输入字符。l f是一个从S至S的映照，即，f：SS（单值函数）例f (si,a) = sj，表示当现行状态为si，若输入字符为a，则转移到下一状态sj，sj称为si的后继状态。l s0S，是唯一的一个初态。l ZS，是一个终态集。状态转换矩阵DFA M可用一个（确定的）状态转换图表示字可为DFA M识别2.2.4 非确定有限自动机（NFA）定义一个非确定的有限自动机M是一个五元式M=（S，f，S0，Z）l S是一个有限集，它的每一个元素称为状态。l 是一个有穷字母表，它的每个元素称为一个输入字符。l f是一个从S*到S的子集映照，即，f：S*2S（多值函数）2S表示幂集，若S=0，1，则2S =，0，1，0，1。l S0S，是一个非空初态集，即NFA的初态不一定唯一。l ZS，是一个终态集。NFA M可用一个（非确定的）状态转换图表示字可为NFA M识别DFA是NFA的特例2.2.5正规式与确定有限自动机的等价性对于上的每个正规式V，存在一个上的确定有限自动机M，便得L(V)=L(M)。VNFA将V表示成拓广NFA根据三条规则对V进行分裂，直至每条弧上的标记为上的一个字符或。NFADFAI的闭包IaNFA确定化算法2.3词法分析器的自动生成输入正规式（构词规则），经自动生成器加工，其结果为DFA。 词法分析器 输入 的 输出 (正规式) 自动生成器 (DFA)自动生成过程概述构造描述每个单词的正规式Pi(1iN)。根据正规式Pi构造NFA Mi(1iN)，假定初态均为0。在构造NFA Mi的同时，逐步并且最终形成识别全部单词的NFA M。NFA M确定化重新标记，构造DFA M。实例扫描器控制程序工作原理第3章 程序设计语言的语法描述文法：对语言结构的定义和描述。3.1 文法的引入先讨论自然语言的文法。例：the big elephent ate a banana语法树根据英语的语法，上述句子的语法结构可用图（语法树）表示如下： the big elephant ate a banana非叶结点称为语法单位，在形式语言中称为非终结符。处于根结点位置的结点又称为开始符号。叶结点称为单词符号，在形式语言中称为终结符。规则可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。上述英文句子可用下述规则来描述：1. 2. 3. the| a 4. big5. elephant| banana6. 7. 8. ate由规则推导句子可用规则来推导出句子。从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。 the the big the big elephant the big elephant the big elephant ate the big elephant ate the big elephant ate a the big elephant ate a banana上述推导可简单表示为：the big elephant ate a banana。值得注意的是用上述规则可推导出多个句子，因存在推导the big banana ate an elephant故the big banana ate an elephant也是文法的一个合法的句子。但意义是荒谬的，也就是说句子的语义是错误的。 一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。递归规则和递归文法递归定义递归规则（直接递归）间接递归递归文法利用递归文法我们可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。例：定义无符号整数。不采用递归规则，描述无符号整数全体就要使用无穷多条的规则。 |0|1|2|3|4|5|6|7|8|9|0采用递归规则，描述无符号整数全体仅需12条规则。 |NND|D 0|1|2|3|4|5|6|7|8|9|0D0|1|2|3|4|5|6|7|8|9|0例1：无符号整数1 ND1例2：无符号整数23 NNDDD2D23例3：无符号整数456 NNDNDDDDD4DD45D4563.2上下文无关文法形式语言的奠基人乔姆斯基将文法分为4种类型，它们是：l 短语文法（0型文法）l 上下文有关文法（1型文法）l 上下文无关文法（2型文法）l 正规文法（3型文法）这四种文法在形式语言中都有严格的定义。但对于程序设计语言来说，上下文无关文法已经够用了，上下文无关文法有足够的能力描述大多数现今使用的程序设计语言的语法结构。以后，“文法”一词若无特别说明，则指“上下文无关文法”。文法和语言一个文法G是一个四元式(VT,VN,S,VP)，其中l VT是一个终结符的非空有限集，终结符通常用小写字母表示。l VN是一个非终结符的非空有限集，非终结符通常用大写字母表示。l S是一个特殊的非终结符（SVN），称为开始符号。 l VP是一个产生式（规则）的有限集合，每个产生式的形式是A ，其中AVN，(VTVN)*。例：G=（VT，VN，S，VP） VT=+，*，(，)，i VN=E S=E VP=EE+E，EE*E，E(E)，Ei 可简记为： G：EE+E|E*E| (E)|i 根据上述文法，可推导出任何仅包含加乘的算术表达式。基本术语直接推出和直接归约推导和归约句型句子语言等价文法最左推导和最右推导文法的二义性语法树我们可以用一个有向图表示一个句型的推导，这种表示称为语法树。在一般情况下，某一句型不论其推导过程如何，其最终形成的语法树是相同的，故语法树是不同推导过程的共性抽象。若仅进行最左（右）推导，则语法树和最左（右）推导等价。二义文法某些文法的句型的推导可能对应一棵以上的语法树，或存在一个以上的最左（右）推导。例：已知文法G：EE+E|E*E|(E)|i和句子i+i*i，该句子存在二个最左（右）推导，即二棵语法树。语法树1（先形成+后形成*）EE+EE*Eiii语法树2（先形成*后形成+）EE*EiE+Eii句子i+i*i的二个最左推导序列：EE+Ei+Ei+E*Ei+i*Ei+i*i EE*EE+E*Ei+E*Ei+i*Ei+i*i句子i+i*i的二个最右推导序列： EE+EE+E*EE+E*iE+i*ii+i*i EE*EE*iE+E*iE+i*ii+i*i二义文法：若一个文法所产生的语言中，只要存在一个句子，它有二个最左推导，或有二个最右推导，或句子的推导对应两棵语法树，则称该文法为二义文法。二义文法的利用和处理l 根据条件修改文法，语言不变。l 根据条件修改编译程序的某一部分，文法保持不变（详见第四、五章）。第4章 自上而下的语法分析从文法的开始符号出发进行推导，最终推出确定的输入串（由单词种别构成的源程序）。4.1 带回溯的自上而下分析法概述从根结点出发，试图用一切可能的办法，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。分析过程概述例已知文法G：SxAyA*|* 和输入串=x*y。初始时，指示器P指向的第一个符号x。Sx * y从S推导，因最左子结和输入串第一个符号相匹配，故指示器P指向下一符号*。 Sx * yx A y因第二个子结是非终结符A，从A采用第一个候选进行推导。从A推导出的左子结和指示器P所指的符号一致，故P指向下一个符号y。Sx *yx A y* *因A的第二个子结*和指示器P所指的符号不一致，这意味着A的第一个候选不适用于构造的语法树，应该回溯。将A的子树注销，P恢复进入A时的值。 Sx * yx A y用A的第二个候选进行推导，因子树A的子结和指示器P所指的符号*一致，则P指向下一个符号y。Sx * yx A y *因S的第三个子结和指示器P所指的符号一致，故是一个句子。显然上述分析过程本质上是一个试探过程，是反复使用不同产生式谋求匹配输入串的过程。问题和困难对于左递归文法定义的语言，不能采用自上而下的语法分析法。例已知左递归文法G：SSba和输入串=ab，其分析过程如下所示： S ab S b . b试图用非终结去推导匹配输入串，而推导所得到的子树第一个子结是该非终结符本身，这样就陷入了死循环。存在虚假匹配，回溯不可避免。编译程序的语法分析和语义分析通常是同时进行的。由于回溯，编译程序所做的一大堆语义分析工作必须推倒重来。当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。这种分析法最终只能告知输入串不是文法的一个句子，而无法告知输入串错在何处。带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，因此效率很低，这种分析法几乎没有实用价值。4.2 直接左递归的消除实例引入例：已知左递归文法G：SSa|b，构造文法G的等价文法G，G不含左递归。解：文法G如下所示SbSSaS|SSaSaaban 或 SbL(G)= bann0SbSbaSban 或 Sb SbL(G)= bann0L(G)= L(G)文法G和G等价，而文法G不含左递归。直接左递归消除方法假定关于非终结符P的规则为PP|其中，不以P开头。可以把关于P的规则变换为如下形式：PPPP|由于二者推导出的句型均为n（n0），故上述变换是等价的。例文法GEE+T|TTT*F|FF(E)|i|x|y经消除直接左递归后变成ETE E+TE|TFTT*FT|F(E)|i|x|y直接左递归消除一般规则及等价性证明4.3 不带回溯的自上而下分析法的基本原理设文法G有产生式A1|2|n带回溯的自上而下的分析法采用试探法，对于1、2直至n逐一试探。不带回溯的自上而下的分析法在推导时，根据面临的输入符号去找出A的那个唯一正确的候选式。引入候选式的first集定义根据定义，求出每个候选式i的first集。根据当前输入符号，选择候选式进行推导。进一步考虑（A）引入非终结符follow集定义修改分析算法4.4 提取左因子实例引入例定义无符号整数的文法NDN|D D0|1|2|3|4|5|6|7|8|9|0就是这样一种情形，first(DN)first(D)=D。解决方法提取左因子，引进产生式，将文法改造为G。NDNNN| D0|1|2|3|4|5|6|7|8|9|0提取左因子一般规则4.5 first集和follow集4.5.1 first集的定义及构造算法first集定义是文法G的任一符号串（包括候选式），(VTVN)* first()=aa，aVT若，则规定first()。文法符号first集构造算法终结符的first集为终结符本身。观察每个产生式，若有Xa，其中aVT，则afirst(X)；若X，则first(X)。观察每个产生式，若有XY，其中YVN，则将first(Y)中的非元素（记为first(Y)/）加到first(X)中。考虑更一般情况，XY1Y2YiYn，其中Y1、Y2、Yi-1VN。l 若first(Y1)中含有，则将first(Y2)/加到first(X)中，否则终止计算。l 若first(Y1)和first(Y2)中含有，则将first(Y3)/加到first(X)中，否则终止计算。l 若first(Y1)、first(Y2)、first(Yi-1)均含有，即Y1Y2Yi-1，则把first(Yi)/加到first(X)中，否则终止计算。l 若所有first(Yj) 均含有(1jn)，即Y1Y2Yn，则first(X)。反复使用规则，直至每个非终结符的first集不再增长为止。例，文法G如下所示, 求文法符号的first集。ETE E+TE| TFT T*FT|F(E) | i | x | y解：非终结符的first集计算过程如下first集规则规则1规则2规则3E(,i,x,y(,i,x,yE+,+,+,+,T(,i,x,y(,i,x,y(,i,x,yT*,*,*,*,F(,i,x,y(,i,x,y(,i,x,y(,i,x,y候选式first集构造算法设A，=X1X2Xn，计算规则如下所示： 置first()=first(X1)/。若first(X1)，则把first(X2)/加至first()中；若first(X1)且first(X2)，则把first(X3)/加至first()；依次类推。若所有的first(Xi)均含有,其中1in，则first()。特别当=,则first()=。接上例，求文法G候选式的first集：ETEfirst(TE)=first(T) /=(,i,x,yE+TE|first(+TE)=+,first()=TFTfirst(FT)=first(F) /=(,i,x,yT*FT|first(*FT)=*,first()=F(E)|i|x|yfirst(E)=( 、first(i)=i、first(x)=x、first(y)=y任一文法符号串的first集构造算法设AX1X2Xi-1XiXi+1Xn，求XiXi+1Xn的first集。令= XiXi+1Xn，参照即可。4.5.2 follow集的定义及构造算法follow集定义设S是文法开始符号，对于文法的任何非终结符A follow(A)=aSAa，aVT 特别是，若SA，规定#follow(A)。follow集构造算法对于文法开始符号S，因为SS，故#follow(S)。观察每个产生式，若AB，其中BVN，(VTVN)*、(VTVN)+，则把first()/加至follow(B)。观察每个产生式，若AB或AB()，则把follow(A)加至follow(B)。反复使用第条规则，直至每个非终结符的follow集不再增长为止。例，文法G如下所示，求非终结符的follow集。1. ET Efirst(E) /= + 2. E+TE3. E4. TFTfirst(T) /= * 5. T*FT 6. T7. F(E)first( ) )=)8. Fi9. Fx10. Fy解： 计算过程如下follow集规则规则1规则2E#,)#,)#,)E#,)#,)T+,#,)+,#,)T+,#,)+,#,)F*,+,#,)*,+,#,)4.6 递归下降分析法递归下降分析法思想是：让每个非终结符对应一个过程（函数）。根据上述文法，构造递归下降分析程序，程序用类C语言描述。struct code_valchar code;char val20; t;/定义结构变量，存放单词二元式。ifstream cinf(lex_r.txt,ios:in);/从文件lex_r.txt输入数据void E( )/ ETET;E;void E( )/ E+TE|if (t.code=+)cinft.codet.val; /读一个单词的二元式T;E;void T( )/ TFTF;T;void T( )/ T*FT|if (t.code=*)cinft.codet.val; /读一个单词的二元式F;Tvoid F( )/ F(E) | i | x | yif (t.code=()cinft.codet.val; /读一个单词的二元式E;if (t.code=) cinft.codet.val; /读一个单词的二元式else if (t.code=i| t.code=x| t.code=y)cinft.codet.val; /读一个单词的二元式void main( ) cinft.codet.val;/读一个单词的二元式E;源程序经词法分析，改造为单词二元式序列形式，存放于文件lex_r.txt中。递归下降分析器从文件lex_r.txt读入数据进行处理。4.7 预测分析法预测分析法基本原理产生式的一般形式为：A1|2|n|设当前输入符号为a，根据下述原则 if (afirst(i) 用Ai推导（1in） else if (afollow(A)用A推导else报错构造分析表如下+*()ixx#EETEETEETEETEEE+TEEETTFTTFTTFTTFTTTT*FTTTFF(E)FiFxFx以输入串“i + i#”为例，说明工作原理如下：ETEFTEiTEiEi+TEi+FTEi+iTEi+iEi+iii i + + i i # #分析表构造规则构造所有候选式的first集，构造所有非终结符的follow集。对于文法的每个产生式A执行和。对于每个终结符afirst()，把A加至MAa。若first()，则对于每个终结符bfollow(A)，把A加至MAb。把所有未定义的MAc标上“出错标志”（cVT）。预测分析控制程序实现数据结构M：二维数组，存放预测分析表。stack：符号栈，初始时为#S（S为开始符号）。 X：表示栈顶符号 t.code：当前处理单词种别算法描述预测分析控制程序任何时刻的动作，都按照栈顶符号X和当前输入符号t.code行事，控制程序每次执行下述三种可能的动作之一（暂不考虑出错情况）。l 若X 和 t.code 均为 #，则分析成功，输入串为合法句子，终止分析过程。l 若X是终结符，并且X和t.code相等，表示期望的终结符号和输入符号相等。让X出stack栈，并输入下一个单词二元式。l 若X是非终结符，则查预测分析表。若MXt.code存放着一条关于X的一个产生式，那么，让X出stack栈，然后把产生式右部符号串按反序一一推进stack栈。若右部符号串为空字，则意味着无任何文法符号进栈。预测分析法讨论预测分析法是由分析表和控制程序构成的，控制程序与文法无关，分析表随文法而异。在预测分析表中，若某一单元持有一个以上产生式，则称该预测分析表含多重定义，多重定义使得控制程序无法工作。一个文法，若它的预测分析表不含多重定义，则称该文法是LL(1)文法、分析表为LL(1)分析表。一个文法是LL(1)的，对于文法的每一个非终结符的任何两个不同候选式（A|），下述条件成立：l first()first()=l 若，则first()follow(A)=二义文法不是LL(1)文法二义文法在预测分析法中的应用第6章 语法制导翻译和中间代码生成语法分析和语义分析的区别语义分析主要工作建立符号表和常数表。诊察和报告源程序中的语义错误。根据语言的语义产生中间代码（或机器指令），或直接解释执行。6.1 语法制导翻译概述语法制导翻译方法简介为每一个产生式配一个语义子程序。在语法分析过程中，当一个产生式获得匹配或用于归约时，此产生式相应的语义子程序进入工