编译原理复习陆筱霞.ppt

编译原理复习课,陆筱霞公共邮箱：密码：soft_zzti,第一章 引 论,一.什么是编译程序,翻译程序 把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序,一.什么是编译程序,编译程序(compiler)把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序诊断编译程序优化编译程序交叉编译程序可变目标编译程序,一.什么是编译程序,解释程序 把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身,二.编译过程,编译程序的工作一般分为五个阶段:词法分析语法分析中间代码产生优化目标代码产生,1.词法分析,任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。依循的原则：构词规则描述工具：有限自动机FOR I:=1 TO 100 DO 保留字 标识符 等符 整常数 保留字 整常数 保留字,2.语法分析,任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。依循的原则：语法规则描述工具：上下文无关文法Z:=X+0.618*Y 算术表达式，赋值语句,3.中间代码产生,任务:对各类不同语法范畴按语言的语义进行初步翻译。依循的原则：语义规则中间代码:三元式，四元式，树形结构等Z:=X+0.618*Y 翻译成四元式为(1)*0.618 Y T1(2)+X T1 T2(3):=T2 _ Z,4.优化,任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规则,5.目标代码产生,任务:把中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式:绝对指令代码:可直接运行 可重新定位指令代码:需要连接装配汇编指令代码:需要进行汇编,三.编译程序结构,编译程序总框,词法分析器,语法分析器,语义分析与中间代码生成器,优化段,表格管理,出错处理,目标代码生成器,2.表格和表格管理,常见的表格:符号名表，常数表，标号表，入口名表，过程引用表。格式:,名字,信息,3.出错处理,出错处理程序：发现源程序中的错误，把有关错误信息报告给用户语法错误语义错误,4.遍(pass),所谓遍，就是对源程序或源程序的中间表示从头到尾扫描一次。阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。,5.编译前端与后端,编译前端：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化编译后端：与目标机有关，与目标机有关的优化，目标代码产生优点：减少对内存容量的要求，程序逻辑结构清晰;优化更充分，有利于移植。不足:编译程序运行的效率低,前端,后端,第二章 高级语言及其语法描述,一.语法,程序本质上是一定字符集（称为字母表）上的字符串（有限序列）。语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序。规则的一部分称为词法规则，另一部分称为语法规则（或产生式规则）。,语 法,词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：有限自动机语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;描述工具：上下文无关文法,语义,语义：一组规则，用它可以定义一个程序的意义。描述方法：自然语言描述：隐藏错误、二义性和不完整性形式描述：操作语义(PL/1)指称语义(ADA)代数语义(PASCAL),2.3 程序语言的语法描述,几个概念:考虑一个有穷 字母表 字符集其中每一个元素称为一个字符上的字(也叫字符串)是指由中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为用*表示上的所有字的全体,包含空字例如:设=a，b，则*=,a,b,aa,ab,ba,bb,aaa,.即 是空集，表示一个不含任何元素的集合。,*的子集U和V的连接（积）定义为UV|U&V 设：U a,aa V b,bb 那么：UV=ab,abb,aab,aabb,V自身的 n次积记为Vn=VVV规定V0=，令 V*=V0V1V2V3 称V*是V的闭包;记 VVV*，称V+是V的正规闭包。闭包V*中每个符号串都是由V中的符号串经有限次连接而成的。,2.3.1 上下文无关文法,文法：描述语言的语法结构的形式规则,上下文无关文法的定义：一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VT VN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VT VN)*开始符S至少必须在某个产生式的左部出现一次。,定义：称A直接推出，即A 仅当A 是一个产生式，且，(VT VN)*。如果1 2 n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。对文法G(E)：E i|E+E|E*E|(E)E(E)(E+E)(i+E)(i+i),通常，用 表示：从1出发，经过一步或若干步，可以推出n。,用 表示：从1出发，经过0步或若干步，可以推出n。,从一个句型到另一个句型的推导往往不唯一。E+Ei+Ei+i E+EE+ii+i最左推导：任何一步 都是对中的最左非终结符进行替换。最右推导：任何一步 都是对中的最右非终结符进行替换。规范推导、规范规约,定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。G(E)：E i|E+E|E*E|(E)是二义文法。语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。可能存在G和G，一个为二义的，一个为无二义的。但L(G)=L(G)二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。可以找到一组无二义文法的充分条件。,2.3.3 形式语言鸟瞰,Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。,0型(短语文法，图灵机)：产生式形如：其中：(VT VN)*且至少含有一个非终结符；(VT VN)*1型(上下文有关文法，线性界限自动机)：产生式形如：其中：|，仅 S 例外。,2型(上下文无关文法，非确定下推自动机)：产生式形如：A 其中：A VN；(VT VN)*。3型(正规文法，有限自动机)：产生式形如：A B 或 A 其中：VT*；A，BVN 产生式形如：A B 或 A 其中：VT*；A，BVN,右线性文法,左线性文法,第三章 词法分析,词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。词法分析器(Lexical Analyzer)又称扫描器(Scanner)：执行词法分析的程序,3.1 对于词法分析器的要求,一、词法分析器的功能和输出形式功能:输入源程序、输出单词符号单词符号的种类：基本字(保留字)：如 begin，repeat，标识符表示各种名字：如变量名、数组名和过程名常数：各种类型的常数运算符：+，-，*，/，界符：逗号、分号、括号和空白,输出的单词符号的表示形式:(单词种别，单词自身的值)单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值(单词符号的属性信息)。标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。常数按类型分种；常数的值则表示成标准的二进制形式。,三、状态转换图,1 概念状态转换图是一张有限方向图。,结点代表状态，用圆圈表示。,状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。,一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。,识别标识符的状态转换图,1,2,3,字母,其他,字母或数字,*,识别整常数的状态转换图,一个状态转换图可用于识别(或接受)一定的字符串。,单词的描述工具,程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。,正规表达式是典型的词法规则描述工具。,3.3.1 正规式和正规集,正规集可以用正规表达式（简称正规式）表示。正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。,正规式也称正则表达式（regular expression），是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。,正规式和正规集的递归定义：对给定的字母表1)和都是上的正规式，它们所表示的正规集为和;2)任何a，a是上的正规式，它所表示的正规集为a;,3)假定e1和e2都是上的正规式，它们所表示的正规集为L(e1)和L(e2)，则i)(e1|e2)为正规式，它所表示的正规集为L(e1)L(e2)，ii)(e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)，iii)(e1)*为正规式，它所表示的正规集为(L(e1)*，仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式表示的字集才是上的正规集。,所有词法结构一般都可以用正规式描述。若两个正规式所表示的正规集相同，则称这两个正规式等价。如b(ab)*=(ba)*b(a*b*)*=(a|b)*,L(ba)*b)=L(ba)*)L(b)=(L(ba)*L(b)=(L(b)L(a)*L(b)=ba*b=,ba,baba,bababa,b=b,bab,babab,bababab,L(b(ab)*)=L(b)L(ab)*)=L(b)(L(ab)*=L(b)(L(a)L(b)*=b ab*=b,ab,abab,ababab,=b,bab,babab,bababab,L(b(ab)*)=L(ba)*b)b(ab)*=(ba)*b,3.3.2 确定有限自动机(DFA),对状态图进行形式化，则可以下定义：自动机M是一个五元式M=(S,f,S0,F),其中：1.S:有穷状态集，2.：输入字母表(有穷)，3.f:状态转换函数，为SS的单值部分映射，f(s，a)=s表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s。我们把s称为s的一个后继状态。4.S0S是唯一的一个初态；5 FS：终态集(可空)。,DFA可以表示为状态转换图。假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧射出，且每条箭弧用上的不同的输入字符来作标记。,对于*中的任何字，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于，则称为DFA M所识别(接收)DFA M所识别的字的全体记为L(M)。可以证明：上的字集V*是正规集，当且仅当存在上的DFA M，使得VL(M)。,3.3.3 非确定有限自动机(NFA),定义：一个非确定有限自动机(NFA)M是一个五元式M=(S,f,S0,F)，其中：1 S:有穷状态集；2：输入字母表(有穷)；3 f:状态转换函数，为S*2S的部分映射(非单值)；4 S0S是非空的初态集；5 F S：终态集(可空)。,从状态图中看NFA 和DFA的区别：1 弧上的标记可以是*中的一个字，而不一定是单个字符；2 同一个字可能出现在同状态射出的多条弧上。DFA是NFA的特例。,1.假定NFA M=，我们对M的状态转换图进行以下改造：1)引进新的初态结点X和终态结点Y，X,YS，从X到S0中任意状态结点连一条箭弧，从F中任意状态结点连一条箭弧到Y。2)对M的状态转换图进一步施行替换，其中k是新引入的状态。,证明:,加入新初态和新终态的目的是让转换图中初态和终态唯一。任意表示状态集合中的所有节点都应该与新加入节点间有弧相连。,代之为,代之为,代之为,按下面的三条规则对V进行分裂:,逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFA M，显然L(M)=L(M),2.把上述NFA确定化采用子集法.,设I是的状态集的一个子集，定义I的-闭包-closure(I)为:i)若sI，则s-closure(I)；ii)若sI，则从s出发经过任意条弧而能到达的任何状态s都属于-closure(I)即-closure(I)=Is|从某个sI出发经过任意条弧能到达s,设a是中的一个字符，定义Ia=-closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。,确定化的过程:不失一般性，设字母表只包含两个a和b，我们构造一张表:,首先，置第1行第1列为-closure(X)求出这一列的Ia，Ib；然后，检查这两个Ia，Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合.重复上述过程，知道所有第2，3列子集全部出现在第一列为止。,现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。这张表唯一刻划了一个确定的有限自动机M，它的初态是-closure(X)，它的终态是含有原终态Y的子集。不难看出，这个DFA M与M等价。,3.3.4 正规文法与有限自动机的等价性,定理：1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA)M，使得L(M)L(G)。2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。,了解转换过程：1.对每一个右线性正规文法G或左线性正规文法G，都构造一个有限自动机（FA）M，使得L(M)L(G)。(1)设右线性正规文法G=。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，fVN。令M=，其中状态转换函数由以下规则定义：,(a)若对某个AVN及aVT，P中有产生式Aa，则令(A,a)=f(b)对任意的AVN及aVT，设P中左端为A，右端第一符号为a的所有产生式为：AaA1|aAk（不包括Aa），则令(A,a)=A1,Ak。显然，上述M是一个NFA。,对于右线性正规文法G，在S w的最左推导过程中:利用AaB一次就相当于在M中从状态A经过标记为a的箭弧到达状态B（包括a=的情形）;在推导的最后，利用Aa一次则相当于在M中从状态A经过标记为a的箭弧到达终结状态f（包括a=的情形）。综上，在正规文法G中，S w的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于w，这就是说，wL(G)当且仅当wL(M)，故L(G)L(M)。,(2)设左线性正规文法G=。将VN中的每一符号视为状态符号，并增加一个初始状态符号q0，q0VN。令M=，其中状态转换函数由以下规则定义：(a)若对某个AVN及aVT，若P中有产生式Aa，则令(q0,a)=A(b)对任意的AVN及aVT，若P中所有右端第一符号为A，第二个符号为a的产生式为：A1Aa,AkAa，则令(A,a)=A1,Ak。与(1)类似，可以证明L(G)L(M)。,3.3.5 正规式与有限自动机的等价性,定理：1.对任何FA M，都存在一个正规式r，使得L(r)=L(M)。2.对任何正规式r，都存在一个FA M，使得L(M)=L(r)。对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号),证明：1 对上任一NFA M，构造一个上的正规式r，使得L(r)=L(M)。首先，在M的转换图上加进两个状态X和Y，从X用弧连接到M的所有初态结点，从M的所有终态结点用弧连接到Y，从而形成一个新的NFA，记为M，它只有一个初态X和一个终态Y，显然L(M)=L(M)。然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下X和Y为止；,代之为,代之为,代之为,对一个DFA M最少化的基本思想:把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。,具体做法:对M的状态集进行划分首先，把S划分为终态和非终态两个子集，形成基本划分。假定到某个时候，已含m个子集，记为=I(1)，I(2)，I(m)，检查中的每个子集看是否能进一步划分:对某个I(i)，令I(i)=s1,s2,sk，若存在一个输入字符a使得Ia(i)不会包含在现行的某个子集I(j)中，则至少应把I(i)分为两个部分。,自上而下分析,第四章 语法分析,4.1 语法分析器的功能,语法分析的任务是分析一个文法的句子结构。语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。,4.2 自上而下分析面临的问题,自上而下就是从文法的开始符号出发，向下推导，推出句子。带“回溯”的不带回溯的递归子程序(递归下降)分析方法。自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。,当某个非终结符有多个产生式候选时，可能带来如下问题:1.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P,含有左递归的文法将使自上而下的分析陷入无限循环。,结论左递归和回溯问题的产生直接与描述语言的文法有关。因此，要对文法进行确定的自顶向下分析应该改造文法，使其不含左递归和回溯。,4.3.1 左递归的消除,直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为PP|其中不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式：PPPP|,左递归变右递归,一般而言，假定P关于的全部产生式是PP1|P2|Pm|1|2|n其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成：P1P|2P|nPP1P|2P|mP|,左递归变右递归,消除左递归的算法:1.把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|2|k;(其中Pj1|2|k是关于Pj的所有规则)消除关于Pi规则的直接左递归性 END3.化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。,4.3.2 消除回溯、提左因子,为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。A 1|2|n,令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：,特别是，若，则规定FIRST()。,如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 jFIRST(i)FIRST(j)当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。,提取公共左因子:假定关于A的规则是 A 1|2|n|1|2|m(其中，每个 不以开头)那么，可以把这些规则改写成AA|1|2|mA 1|2|n经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。,当A面临输入符a时,若aFIRST(A)且FIRST(A),则考虑自动匹配问题。对于上述算术表达式文法,若输入串为i/i,即使让T自动匹配,“/”仍不能与后面符号匹配,此时没必要让T自动匹配。,结论:只有在当前输入符能与A后的第一个终结符匹配成功时,才让A自动得到匹配。这就要求分析前先求出紧跟在A后的终结符,即FOLLOW(A)。,假定S是文法G的开始符号，对于G的任何非终结符A，我们定义,特别是，若，则规定 FOLLOW(A),4.3.3 LL(1)分析条件,即FOLLOW(A)是所有句型中紧跟在A之后的终结符 或#。,自动匹配条件 当A面临输入符a时,若aFIRST(A)且FIRST(A),则只有当aFOLLOW(A)时,才使A自动得到匹配。缺少任一条件,均不自动匹配。,若输入符aFIRST(A)且aFOLLOW(A),则当FIRST(A)时仍可能需进行试探(回溯)。因此,对于存在-生成式的非终结符A,若要进行不带回溯的自上而下分析,则FIRST(A)与FOLLOW(A)应互不相交。,构造不带回溯的自上而下分析的文法条件1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A 1|2|n 则 FIRST(i)FIRST(j)(ij)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(i)FOLLOW(A)=i=1,2,.,n如果一个文法G满足以上条件，则称该文法G为LL(1)文法。,对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A 1|2|n1.若aFIRST(i)，则指派 i执行匹配任务；2.若a不属于任何一个候选首符集，则：(1)若属于某个FIRST(i)且 aFOLLOW(A)，则让A与自动匹配。(2)否则，a的出现是一种语法错误。,对每一文法符号XVTVN构造FIRST(X)连续使用下面的规则，直至每个集合FIRST不再增大为止：1.若XVT，则FIRST(X)X。2.若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若X也是一条产生式，则把也加到FIRST(X)中。,3.若XY是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有(即Y1Yi-1)，则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j1，2，k，则把加到FIRST(X)中。,对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止：1.对于文法的开始符号S，置于FOLLOW(S)中；2.若AB是一个产生式，则把FIRST()加至FOLLOW(B)中；,3.若AB是一个产生式，或AB是一个产生式而(即FIRST()，则把FOLLOW(A)加至FOLLOW(B)中。,4.4 递归下降分析程序构造,递归下降分析法也称递归子程序法，是一种直观易于构造的自顶向下分析方法。分析过程则通过自上而下一级一级地调用子程序来实现，所以称为递归下降分析法。思想:对文法中的每个非终结符编写一个处理子程序，处理子程序的代码结构由相应的非终结符的规则右部来决定：规则右部的终结符号与输入符号相匹配，非终结符与相应的子程序调用相对应，非终结符对应的各个候选式与分支结构相对应。,构造不带回溯的自上而下分析器分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的)几个全局过程和变量：ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号SYM，IP当前所指的输入符号ERROR，出错处理子程序,每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。,4.5 预测分析程序,预测分析程序或LL(1)分析法：总控程序分析表 MA，a矩阵，A VN，a VT 是终结符或，分析栈 STACK 用于存放文法符号,二、分析表MA，a的构造,构造FIRST()和FOLLOW(A)构造分析表MA，a,在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表MA，a。1.对文法G的每个产生式A执行第2步和第3步；2.对每个终结符a FIRST()，把A加至MA，a中；3.若FIRST()，则对任何bFOLLOW(A)把A加至MA，b中。4.把所有无定义的MA，a标上“出错标志”。,第五章 语法分析,自下而上分析,语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约,5.1.2 规范归约,定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且,则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。,把上例倒过来写，则得到：S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。规范归约是一个最右推导的逆过程最左归约 规范推导由规范推导推出的句型称为规范句型。,首先必须定义任何两个可能相继出现的终结符a与b(可能中间有VN),的优先关系 三种关系ab a的优先级高于b注意：与数学上的,=不同a a,算符优先分析法,5.2.1 算符优先文法及优先表构造,一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：QR 则我们称该文法为算符文法。约定：a、b代表任意终结符；P、Q、R代表任意非终结符；代表由终结符和非终结符组成的任意序列，包括空字。,假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：1.a b当且仅当文法G中含有形如Pab或PaQb的产生式；,3.a b 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。,2.a b当且仅当G中含有形如PaR的产生式，而R b或R Qb；,如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：a b 则称G是一个算符优先文法。,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足a b的终结符对。确定满足关系 的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系 的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系 的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,比较,比较,有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系的所有终结符对。假定有个产生式的一个候选形为aP 那么，对任何bFIRSTVT(P)，有 a b。,数据结构：布尔数组FP，a，使得FP，a为真的条件是，当且仅当aFIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素FP，a赋初值。栈STACK，把所有初值为真的数组元素FP，a的符号对(P，a)全都放在STACK之中。,运算：如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如PQ 的产生式，若FP，a为假，则变其值为真且将(P，a)推进STACK栈。上述过程必须一直重复，直至栈STACK拆空为止。,如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)：PROCEDURE INSERT(P，a)；IF NOT FP，a THENBEGIN FP，a:=TRUE；把(P，a)下推进STACK栈 END；,主程序：BEGIN FOR 每个非终结符P和终结符a DO FP，a:=FALSE；FOR 每个形如Pa或PQa的产生式 DO INSERT(P，a)；WHILE STACK 非空 DOBEGIN 把STACK的顶项，记为(Q，a)，上托出去；FOR 每条形如PQ的产生式 DOINSERT(P，a)；END OF WHILE；END,这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。FIRSTVT(P)a|FP，a=TRUE同理，可构造计算LASTVT的算法。,构造集合LASTVT(P)的算法。按其定义，可用下面两条规则来构造集合LASTVT(P)：1.若有产生式P a或P aQ，则a LASTVT(P)；2.若a LASTVT(Q)，且有产生式P Q，则a LASTVT(P)。,使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：,FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和Xi+1均为终结符 THEN 置Xi Xi+1 IF in-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置Xi Xi+2；IF Xi为终结符而Xi+1为非终结符 THENFOR FIRSTVT(Xi+1)中的每个a DO 置 XiXi+1 END,5.2.2 算符优先分析算法,可归约串，句型，短语，直接短语，句柄，规范归约。一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。最左素短语是指处于句型最左边的那个素短语。,第六章 属性文法和语法制导翻译,语义分析的任务,编译中的语义处理包括两个功能：（1）审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。也称为静态语义分析或静态审查；（2）如果静态语义正确，则执行真正的翻译，即生成中间代码或生成实际的目标代码。以上工作普遍基于属性文法和语法制导翻译方法。,属性综合属性：“自下而上”传递信息继承属性：“自上而下”传递信息在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为：b:=f(c1,c2,ck)这里，f是一个函数，而且或者1.b是A的一个综合属性并且c1,c2,ck是产生式右边文法符号的属性，或者2.b是产生式右边某个文法符号的一个继承属性并且c1,c2,ck 是A或产生式右边任何文法符号的属性。属性b依赖于属性c1,c2,ck。,一遍扫描实现布尔表达式的翻译,采用四元式形式把四元式存入一个数组中，数组下标就代表四元式的标号约定 四元式(jnz,a,-,p)表示 if a goto p 四元式(jrop,x,y,p)表示 if x rop y goto p四元式(j,-,-,p)表示 goto p,有时,四元式转移地址无法立即知道,我们只好把这个未完成的四元式地址作为E的语义值保存,待机回填。,为非终结符E赋予两个综合属性E.truelist和E.falselist。它们分别记录布尔表达式E所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表 例如:假定E的四元式中需要回填真出口的p，q，r三个四元式，则E.truelist为下列链:(p)(x，x，x，0)(q)(x，x，x，p)(r)(x，x，x，q),链尾,E.truelist=r,为了处理E.truelist和E.falselist，引入下列语义变量和过程:变量nextquad，它指向下一条将要产生但尚未形成的四元式的地址(标号)。nextquad的初值为1，每当执行一次emit之后，nextquad将自动增1。函数makelist(i)，它将创建一个仅含i的新链表，其中i是四元式数组的一个下标(标号)；函数返回指向这个链的指针。函数merge(p1,p2)，把以p1和p2为链首的两条链合并为一，作为函数值，回送合并后的链首。过程backpatch(p,t)，其功能是完成“回填”，把p所链接的每个四元式的第四区段都填为t。,