《编译原理及其习题解答武汉大学出版社课件chap6》由会员分享，可在线阅读，更多相关《编译原理及其习题解答武汉大学出版社课件chap6（93页珍藏版）》请在金锄头文库上搜索。
1、中南民族大学计算机科学学院中南民族大学计算机科学学院编译原理编译原理CompilerPrinciples第六章第六章 自底向上优先分析法自底向上优先分析法编译原理CompilerPrinciples第六章第六章 自底向上优先分析法自底向上优先分析法自底向上的分析方法，也称移进自底向上的分析方法，也称移进-归约分析法。它的归约分析法。它的实实现思想现思想是：是：对输入符号串自左向右进行扫描，并将输入符逐个移对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，成某个句型的句柄时，(该句
2、柄对应某产生式的右部该句柄对应某产生式的右部)，就，就用该产生式的左部非终结符代替相应右部的文法符号串，用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句的开始符号时则为分析成功，也就确认输入串是文法的句子。子。确定的自底向上的分析方法分为两大类：确定的自底向上的分析方法分为两大类：优先分析法优先分析法和和LR分析方法分析方法。本章将在介绍自底向上分析思想基础上，。本章将在介绍自底向上分析思想基础上，着重介绍算符优先分析法。着重介绍算符优先分析法
3、。 编译原理CompilerPrinciples6.1 短语、直接短语、句柄1、短语：、短语：令文法令文法G，开始符号为开始符号为S，xAy是是G的句型的句型（即（即SxAy），），如果如果SxAy且且A，则称则称是句型是句型xy相对于非终结符相对于非终结符A的的短语。短语。2、直接短语（简单短语）、直接短语（简单短语）如短语中有如短语中有A=，则称则称是句型相对于规则是句型相对于规则A的直的直接短语。接短语。3、句柄（、句柄（Handle）一个句型的最左直接短语称为该句型的句柄。一个句型的最左直接短语称为该句型的句柄。（可规约（可规约串）串）编译原理CompilerPrinciples例例6
4、.1例：文法例：文法G数数:|0|1|2|3|4|5|6|7|8|9=1所以，所以，1是一个句型。下面结论是否正确？是一个句型。下面结论是否正确？1.1是句型是句型1相对于相对于的短语。的短语。2.1是句型是句型1相对于相对于的短语。的短语。3.是句型是句型1相对于相对于的短语。的短语。编译原理CompilerPrinciples语法树与短语的关系语法树与短语的关系1.每个句型（句子）都对应有一棵语法树；每个句型（句子）都对应有一棵语法树；2.每棵语法树的叶子结点从左到右、从上到下构成一个句每棵语法树的叶子结点从左到右、从上到下构成一个句型（句子）；型（句子）；3.每棵子树的叶子结点从左到右、
5、从上到下构成一个短语；每棵子树的叶子结点从左到右、从上到下构成一个短语；4.每棵子树的直接叶子结点从左到右、从上到下构成一个每棵子树的直接叶子结点从左到右、从上到下构成一个直接短语；直接短语；5.最左简单子树的直接叶子结点从左到右、从上到下构成最左简单子树的直接叶子结点从左到右、从上到下构成一个句柄。一个句柄。编译原理CompilerPrinciples例例6.11编译原理CompilerPrinciples解题方法解题方法例例2例：文法例：文法GE:ET|E+TTF|T*FF(E)|i证明证明i+i*i是是G的一个句型，并指出这个句型的所有短语、直的一个句型，并指出这个句型的所有短语、直接短
6、语、句柄。接短语、句柄。证明：证明：EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i编译原理CompilerPrinciples接上例接上例语法树：EE+TTT*FFFi3i1i2第1层 i1+i2*i3 相对于E第2层 i1 相对于E ; i2*i3 相对于T第3层 i1 ,i2 相对于T; i3 相对于F第4层 i1 ,i2 相对于F(F i直接短语)第5层 i+i*i是G的一个句型，其中i1 , i2 , i3, i2*i3 , i1+i2*i3 都是句型i1+i2*i3 的短语，且i1 , i2 , i3 为直接短语， i1为句柄编译原理CompilerP
7、rinciples分析说明分析说明(2)作为“短语”的两个条件是不可缺少的，仅仅有A ，未必意味着就是句型的一个短语，因为还需要有S 这个条件。例如：上例中有E i1+i2，但i1+i2并不是该句型的一个短语，因为不存在从E（开始符号）到E* i3的推导。(1)短语、直接短语、句柄是针对某一句型（S ）而言的;编译原理CompilerPrinciples解题方法解题方法 先证明前提（如证明i+i*i是G的一个句型） 给出语法树（注意文法是否是二义性的） 如题文法GE: E E+E|E*E|(E) | i 所以：证明i+i*i是G的一个句型，并指出这个句型的所有短语、直接短语、句柄。 根据每颗语
8、法树得出短语、直接短语、句柄例课本P143例6.3编译原理CompilerPrinciples练习练习1题目题目文法GT: T F | T*F F F P | P P (T) | i 证明T*P (T*F)是文法G的一个句型，并指出这个句型的所有短语、直接短语、句柄。编译原理CompilerPrinciples练习解答练习解答证明：T T*F T*FP T*F(T) T*F(T*F) T*P(T*F)语法树：TT*FFPPT()T*F第1层 T*P(T*F) 相对于T第2层 P(T*F) 相对于F; 第3层 P 相对于F; (T*F) 相对于P第4层 T*F 相对于T第5层 T*P(T*F)是
9、G的一个句型，其中T*F , P , (T*F), P(T*F), T*P(T*F) 都是该句型的短语，且T*F , P 为直接短语， P为句柄编译原理CompilerPrinciples练习2题目设有文法设有文法GS:SV1V1V2|V1iV2V2V3|V2+V3V3)V1*|(1)给出给出(+(i(的最右推导，并画出相应的语法树；的最右推导，并画出相应的语法树；(2)证明证明V2+V3i(是文法的一个句型，并指出这个句型的短语、直接是文法的一个句型，并指出这个句型的短语、直接短语、句柄。短语、句柄。编译原理CompilerPrinciples练习解答（）练习解答（）(1)解：解：SV1V1
10、iV2V1iV3V1i(V2i(V2+V3i(V2+(i(V3+(i(+(i(语法树：语法树：V1V1iV2(SV2V2+V3V3V3(编译原理CompilerPrinciples练习解答（）练习解答（）(2)证明：证明：SV1V1iV2V1iV3V1i(V2i(V2+V3i(V2+V3i(是文法的一个句型是文法的一个句型短语：短语：V2+V3,(,V2+V3i(直接短语：直接短语：V2+V3,(句柄：句柄：V2+V3编译原理CompilerPrinciples算法应考虑的问题算法应考虑的问题n算法是否能够终止？n算法是否快速？n算法是否能够处理所有的情况？n在每一步中如何选择子串进行归约？编
11、译原理CompilerPrinciples文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进A 3） #ab bcde# 归约归约(Ab) 4） #aA bcde# 移进移进A 5） #aAb cde# 归约归约(AAb) 6） #aA cde# 移进移进 7） #aAc de# 移进移进B 8） # aAcd e# 归约归约(Bd) 9） #aAcB e# 移进移进11） #S # 接受接受S10） #aAcBe # 归约归
12、约(SaAcBe)分析符号串abbcde是否GS的句子对输入串abbcde#的移进-规约分析过程SaAcBe aAcde aAbcde abbcde编译原理CompilerPrinciples自下而上分析法存在的问题自下而上分析法存在的问题可归约串的问题可归约串的问题；（；（该分析的每一步就是从当前串中找一该分析的每一步就是从当前串中找一个子串（称个子串（称“可归约串可归约串”），将它归约到某个非终结符号），将它归约到某个非终结符号）自下而上分析法的自下而上分析法的关键关键就是找哪个子串是就是找哪个子串是“可归约串可归约串”，哪个不是哪个不是“可归约串可归约串”。例如上例中的。例如上例中的(3
13、)abbcdeA A(3)用产生式用产生式(2)而非而非(3)，否则不能归约到，否则不能归约到S因此必须精确定义因此必须精确定义“可归约串可归约串”，事实上存在着种种不同的，事实上存在着种种不同的方法刻画方法刻画“可归约串可归约串”，对这个概念的不同定义，形成了不，对这个概念的不同定义，形成了不同的自下而上的分析法。在同的自下而上的分析法。在“规范归约规范归约”的分析中，用的分析中，用“句句柄柄”来刻画来刻画“可归约串可归约串”。编译原理CompilerPrinciples课本例课本例6.4例例6.4 设文法设文法GZ: (1)Z - AB(2)A - aAb(3)A - ab(4)B - b
14、B(5)B - c对输入符号串对输入符号串aabbbc进行移进进行移进-归约分析。归约分析。分析过程在分析过程在p146.编译原理CompilerPrinciples非确定的自下而上的分析器非确定的自下而上的分析器 非确定的自下而上的分析器，是一般移进非确定的自下而上的分析器，是一般移进-归约方法归约方法的抽象模型，可识别任何上下文无关语言。给定一个上下的抽象模型，可识别任何上下文无关语言。给定一个上下文无关文法，可构造一个自下而上的分析器。文无关文法，可构造一个自下而上的分析器。 非确定的自下而上的分析器与非确定的自上而下的分非确定的自下而上的分析器与非确定的自上而下的分析器的不同之处：析器
15、的不同之处： 课本课本P147编译原理CompilerPrinciples非确定的自下而上的分析器形式定义非确定的自下而上的分析器形式定义 非确定的自下而上的分析器，是一个七元组。非确定的自下而上的分析器，是一个七元组。 课本课本P147-148编译原理CompilerPrinciples6.2 自底自底向上优先分析方法概述向上优先分析方法概述优先分析方法可分为简单优先分析法和算符优先分析法。优先分析方法可分为简单优先分析法和算符优先分析法。1、简单优先分析法的基本思想、简单优先分析法的基本思想对一个文法按一定原则求出该文法所有符号（终结符对一个文法按一定原则求出该文法所有符号（终结符和非终结
16、符）之间的优先关系，并按照这种关系来确定归约和非终结符）之间的优先关系，并按照这种关系来确定归约过程中的句柄。它的归约过程是一种规范归约。过程中的句柄。它的归约过程是一种规范归约。2、算符优先分析法的基本思想、算符优先分析法的基本思想只规定算符之间的优先关系（即只考虑终结符之间的只规定算符之间的优先关系（即只考虑终结符之间的优先关系），在规约过程中，只要找到句柄就规约，不考虑优先关系），在规约过程中，只要找到句柄就规约，不考虑归约到哪个非终结符，不是规范归约。归约到哪个非终结符，不是规范归约。编译原理CompilerPrinciples两种优先分析方法的比较两种优先分析方法的比较3、简单优先分
17、析法和算符优先分析法比较、简单优先分析法和算符优先分析法比较简单优先分析法准确、规范，但分析效率低，不实用；简单优先分析法准确、规范，但分析效率低，不实用；算符优先分析法不规范，但速度快，特别适用于表达式的分算符优先分析法不规范，但速度快，特别适用于表达式的分析。析。编译原理CompilerPrinciples6.3 简单优先分析方法简单优先分析方法按照文法符号之间的优先关系来确定句柄。按照文法符号之间的优先关系来确定句柄。1、优先关系的表示、优先关系的表示（1）X=Y表示表示X和和Y的优先关系相等的优先关系相等（2）XY表示表示X的优先性比的优先性比Y的优先性大的优先性大编译原理Compil
18、erPrinciples6.3 简单优先分析方法简单优先分析方法按照文法符号之间的优先关系来确定句柄。按照文法符号之间的优先关系来确定句柄。2、优先关系的确定、优先关系的确定（1）X=Y文法文法G中存在产生式中存在产生式A.XY.（2）XY文法文法G中存在产生式中存在产生式A.BD.，且且B.X和和DY.编译原理CompilerPrinciples简单优先关系的确定简单优先关系的确定 例子例子文法文法GS：(1) S bAb (2) A (B|a (3) B Aa)确定优先关系：确定优先关系：（1）求）求=关系关系因为：因为：SbAb和和A(B|a和和Aa)所以：所以：b=A,A=b,(=B,
19、A=a,a=)（2）求求关系关系因为：因为：SbAb,且且A(B，Aa所以：所以：b(,ba因为：因为：A(B,且且B(B，Ba,BA所以所以:(,(a,(关系关系因为：因为：SbAb,且且A)，AB，Aa所以所以:)b,Bb,ab因为：因为：BAa),且且A)，AB，Aa所以所以:)a,Ba,aa编译原理CompilerPrinciples3. 简单优先关系矩阵简单优先关系矩阵 及及 例子例子优先关系矩阵：把文法符号之间的优先关系用矩阵来表示。优先关系矩阵：把文法符号之间的优先关系用矩阵来表示。注意注意：1.矩阵中的元素要么只有一种优先关系，要么为空；2. #用来表示语句括号，#优先级 #。
20、相当于存在：#S#文法文法GS：(1) S bAb(2) A (B|a(3) B Aa)编译原理CompilerPrinciples4. 简单优先文法的定义简单优先文法的定义若一个文法是简单优先文法，必须满足以下条件：若一个文法是简单优先文法，必须满足以下条件：（1）在文法符号集）在文法符号集V中，任意两个符号序偶最多只有一种优中，任意两个符号序偶最多只有一种优先关系存在；先关系存在；（2）在文法）在文法 中，任意两个产生式没有相同的右部。（若不中，任意两个产生式没有相同的右部。（若不满足会出现归约不唯一）满足会出现归约不唯一）句柄：句柄：在句型在句型a1a2an中，中，ai-1 aj+1则则
21、ai ai+1 aj 是是句柄。句柄。编译原理CompilerPrinciples5. 简单优先分析法简单优先分析法首先首先构造优先关系矩阵；构造优先关系矩阵；其次其次将文法的产生式保存，设置符号栈等；将文法的产生式保存，设置符号栈等；然后然后，按照以下算法进行归约：，按照以下算法进行归约：（1）将输入符号串）将输入符号串a1a2an#依次逐个移入符号栈中，直依次逐个移入符号栈中，直到遇到栈顶符号到遇到栈顶符号ai的优先性的优先性 下一个待输入符号下一个待输入符号aj为止；为止；（2）当前栈顶符号）当前栈顶符号ai为为句柄尾，由此向左在栈中找句柄的头句柄尾，由此向左在栈中找句柄的头符号符号ak
22、，即找到即找到ak-1 ak为止；为止；（3）由句柄）由句柄akai在在文法的产生式中查找对应的产生式，文法的产生式中查找对应的产生式，若找到则进行归约，若找到则进行归约， akai全部出栈，将产生式右部的非全部出栈，将产生式右部的非终结符进栈；否则出错；终结符进栈；否则出错；（4）重复以上步骤，直到归约完输入符号串，栈中只剩下）重复以上步骤，直到归约完输入符号串，栈中只剩下文法的开始符号。文法的开始符号。编译原理CompilerPrinciples文法文法GS：(1) S bAb(2) A (B|a(3) B Aa)步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # b(aa)b#
23、#b,移进移进 2） #b (aa)b# b(,移进移进 3） #b( aa)b# (a,归约归约Aa 5） #b(A a)b# A=a,移进移进 6） #b(Aa )b# a=),移进移进 7） #b(Aa) b# )b,归约归约BAa) 8） #b(B b# Bb,归约归约A(B 9） #bA b# A=b,移进移进10） #bAb # b#,归约归约SbAb11） #S # 接受接受对输入串b(aa)#的简单优先分析过程简单优先关系矩阵编译原理CompilerPrinciples简单优先分析方法的算法流程图及例子简单优先分析方法的算法流程图及例子1. 流程图：流程图：P166 图图6.6
24、2. 例题：例题：P167 例例6.133. 优先关系矩阵的表示优先关系矩阵的表示 P1684. 文法存放的数据结构文法存放的数据结构 P168编译原理CompilerPrinciples6. 有关文法的一些关系有关文法的一些关系 课本课本P1511. 一个一个n元关系元关系R可定义为一个有序的可定义为一个有序的n元组集合。元组集合。2. 基本性质：自反、对称、可传递基本性质：自反、对称、可传递3. 与文法相关的一些关系：关系和、关系积、传递闭包和与文法相关的一些关系：关系和、关系积、传递闭包和自反传递闭包。自反传递闭包。4. 布尔矩阵和关系布尔矩阵和关系5. Warshall算法算法 一个求
25、关系的传递闭包的算法。一个求关系的传递闭包的算法。P1546. 设设R是集合是集合A上的关系，若上的关系，若#A=n，则，则R+= R1 + R2+ Rn 2元关系元关系R的传递闭包的传递闭包R+的关系矩阵为：的关系矩阵为：M(R+)=M(R1)+M(R2)+M(Rk) =M(R)1+M(R)2+M(R)k其中，其中，kB其中，其中，AVN，B(VNVT)，(VNVT)*(2).ALASTB，当且仅当文法有如下产生式：当且仅当文法有如下产生式：A-B其中，其中，AVN，B(VNVT)，(VNVT)*2.FIRST关系的传递闭包关系的传递闭包FIRST+定义为：定义为：AFIRST+B，当且仅当
26、文法有如下产生式序列：当且仅当文法有如下产生式序列：A-B1,B1-B2,Bn-B3.FIRST关系的自反传递闭包关系的自反传递闭包FIRST*定义为：定义为：AFIRST*B，当且仅当当且仅当AFIRST0B或或AFIRST+B4.同理可定义同理可定义LAST的传递闭包和自反传递闭包。的传递闭包和自反传递闭包。编译原理CompilerPrinciples关系关系FIRST与与LAST的的 例子课本例子课本P156例例6.9设文法设文法G44S：S-(A)|a|bA-BB-S|ScBSABabc()S00011010A00100000B10000000a00000000b00000000c00
27、000000(00000000)00000000FIRST=编译原理CompilerPrinciples关系关系FIRST与与LAST 例子例子 续续1例例6.9：S-(A)|a|bA-BB-S|ScBSABabc()S00011001A00100000B10100000a00000000b00000000c00000000(00000000)00000000LAST=编译原理CompilerPrinciples关系关系FIRST与与LAST 例子例子 续续2FIRST+=FIRST1+FIRST2+FIRST8=FIRST1+FIRST2+FIRST4LAST+=LAST1+LAST2+LA
28、ST8=LAST1+LAST2+LAST4两个重要结论：两个重要结论：1.A=+B，当且仅当当且仅当AFIRST+B，其中其中AVN，B(VNVT)，(VNVT)*2.A=+B，当且仅当当且仅当ALAST+B，其中其中AVN，B(VNVT)，(VNVT)*编译原理CompilerPrinciples8. 简单优先关系的形式化构造方法简单优先关系的形式化构造方法 P160可以利用布尔矩阵及其运算，计算出文法中的可以利用布尔矩阵及其运算，计算出文法中的关系。关系。1.两个公式：两个公式：(1).(=)(FIRST+)公式公式(6.1)(2).(LAST+)T(=)(FIRST*)公式公式(6.2)
29、2.根据公式根据公式(6.1)，构造关系的，构造关系的的算法。的算法。4.将简单优先关系将简单优先关系=、的关系矩阵中为的关系矩阵中为1的元素置换成的元素置换成相应的相应的=、并合并，即可得到文法的简单优先关并合并，即可得到文法的简单优先关系矩阵。系矩阵。编译原理CompilerPrinciples9. 简单优先分析方法的局限性简单优先分析方法的局限性课本课本P169编译原理CompilerPrinciples10. 简单优先分析方法简单优先分析方法 练习练习1练习题：练习题：设文法设文法GE为：为：E-E+EE-E*EE-i求简单优先关系矩阵。（考虑对输入串求简单优先关系矩阵。（考虑对输入串
30、i1+i2*i3的归约过程。）的归约过程。）E+*i#E=, =,+=,*=,#=,+=,*=,#E+EE-E*EE-i编译原理CompilerPrinciples10. 简单优先分析方法简单优先分析方法 练习练习2考虑文法考虑文法GE：EE+T|TTT*F|FF(E)|i求简单优先关系矩阵求简单优先关系矩阵.ETF+*()i#E=T=F+=*=(=)i#T=F+=,*=(=)i#编译原理CompilerPrinciples10. 简单优先分析方法简单优先分析方法 练习练习3求简单优先关系矩阵求简单优先关系矩阵.文法文法GE为：为：ETEE+TE|TFTT*FT|F(E)|I复杂。所以，根据文
31、法的特点，考虑其它的分析方法。复杂。所以，根据文法的特点，考虑其它的分析方法。编译原理CompilerPrinciples6.4 算符优先分析方法算符优先分析方法1.求优先关系矩阵求优先关系矩阵.文法文法GE为：为：EE+E|E-E|E*E|E/E|EE|(E)|i算术表达式求值中，运算的次序与运算符有关，算术表达式求值中，运算的次序与运算符有关，而与运算对象无关。若能人为地给出算符的优先顺序，则而与运算对象无关。若能人为地给出算符的优先顺序，则可以解决简单优先文法中的冲突问题。可以解决简单优先文法中的冲突问题。约定：约定：编译原理CompilerPrinciples算符优先分析方法算符优先分
32、析方法1.求优先关系矩阵求优先关系矩阵.文法文法GE为：为：EE+E|E-E|E*E|E/E|EE|(E)|i(1)的优先级最高，右结合，有的优先级最高，右结合，有*,*/,/,/*;(3)+,-优先级最低，左结合，有优先级最低，左结合，有+,+-,-,-+;(4)对对(和和),规定括号的优先性规定括号的优先性括号外的运算符，括号外的运算符，外括号。外括号。(5)i的优先级最高。的优先级最高。编译原理CompilerPrinciples1. 算符优先分析法算符优先分析法表达式文法优先矩阵表达式文法优先矩阵优先关系矩阵为：优先关系矩阵为：+-*/()i#+-*/(=i#=编译原理Compiler
33、Principles文法文法GE：EE+E|E-E|E*E|E/E|E E|(E)|i步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # i+i*i# #i,移进移进 2） #i +i*i# #+,规约规约 3） #E +i*i# #+,移进移进 4） #E+ i*i# +i,移进移进 5） #E+i *i# +*,规约规约 6） #E+E *i# +*,移进移进 7） #E+E* i# *i,移进移进 8） #E+E*i # *#,规约规约 9） #E+E*E # +#,规约规约10） #E+E # #,规约规约11） #E # 接受接受对输入串i+i*i的算符优先分析过程算符优先关
34、系表AnIntroductiontoDatabaseSystem2. 算符文法算符文法(OG) 定义和性质定义和性质(1)算符文法的定义算符文法的定义 如果不含空产生式的上下文无关文法如果不含空产生式的上下文无关文法G中没有形如中没有形如UVW的产生式，其中的产生式，其中V,WVN则称则称G为算符文法为算符文法（OperaterGrammar,OG）。）。即任即任一个产生式的右部，都不包含两个相邻的非终结符。一个产生式的右部，都不包含两个相邻的非终结符。(2)两个重要性质两个重要性质n性质性质1：在算符文法中任何句型都不包含两个相邻的非终结：在算符文法中任何句型都不包含两个相邻的非终结符符.(
35、数学归纳法数学归纳法)n性质性质2：如：如Ax或或xA出现在算符文法的出现在算符文法的句型句型 中，其中中，其中AVN,xVT,则则 中任何中任何含含x的短语必含有的短语必含有A.（反证法）反证法）编译原理CompilerPrinciples2. 算符文法算符文法(OG) 优先关系的定义优先关系的定义(3)算符优先关系的定义算符优先关系的定义在在OG中中 定义定义 （算符优先关系）（算符优先关系）n x = y G中有形如中有形如Uxy或或U xVy. 的产生式。的产生式。 n x y G中有形如中有形如U Wy的产生式的产生式,而而 W x或或W xVn规定规定 若若 S x或或 S Vx
36、则则 # #编译原理CompilerPrinciples3. 算符优先文法算符优先文法(OPG) 定义定义(1)算符优先文法的定义算符优先文法的定义 在OG文法G中，若任意两个终结符间至多有一至多有一种种算符优先关系存在，则称G为算符优先文法(OperaterOperater Precedence Grammar , Precedence Grammar , OPGOPG)。n注意：允许注意：允许bc,cb;bc,cb;不允许不允许bc,bc,bc,b=cn结论：算符优先文法是无二义的。结论：算符优先文法是无二义的。编译原理CompilerPrinciples3. 算符优先文法算符优先文法(O
37、PG) 优先关系的构造优先关系的构造(2)算符优先文法的构造算符优先文法的构造n由定义直接构造由定义直接构造n由关系图法构造算符优先关系表由关系图法构造算符优先关系表以下介绍由定义直接构造优先关系的方法。以下介绍由定义直接构造优先关系的方法。编译原理CompilerPrinciplesn首先引入两个概念首先引入两个概念nFIRSTVT(B)=b|B b或或B Cb.对于非终结符对于非终结符B，其往下推导所可能出现的首个算符其往下推导所可能出现的首个算符(终结符终结符)nLASTVT(B)=a|B a或或B . aC对于非终结符对于非终结符B，其往下推导所可能出现的最后一个其往下推导所可能出现的
38、最后一个算符算符(终结符终结符)1) 由定义构造由定义构造 OPG的优先关系的优先关系编译原理CompilerPrinciples如何计算算符优先关系如何计算算符优先关系1) =关系关系n直接看产生式的右部，若出现了直接看产生式的右部，若出现了A ab或或A aBb,则则a=b2)关系关系n求出每个非终结符求出每个非终结符B的的FIRSTVT(B)n若若AaB,则则 b FIRSTVT(B),a关系关系n求出每个非终结符求出每个非终结符B的的LASTVT(B)n若若ABb,则则 a LASTVT(B),ab编译原理CompilerPrinciples文法文法GE：(0) E#E#(1) EE+
39、T(2) ET(3) TT*F(4) TF(5) FP F|P(6) P(E)(7) PiFIRSTVT(E)=#FIRSTVT(E)=+,*, ,(,iFIRSTVT(T)=*, ,(,iFIRSTVT(F)= ,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*, ,),iLASTVT(T)=*, ,),iLASTVT(F)= ,),iLASTVT(P)=),i1)=关系关系由产生式由产生式(0)和和(6),得得#=#，（，（=）2）关系关系找形如找形如AaB的产生式的产生式#E：则则#FIRSTVT(E)+T: 则则+FIRSTVT(T) *F: 则则*F
40、IRSTVT(F) F:则则 FIRSTVT(F)(E: 则则 (关系关系找形如：找形如：ABb的产生式的产生式E# ,则则 LASTVT(E)#E+ ,则则 LASTVT(E)+ T* ,则则 LASTVT(T)* P ,则则 LASTVT(P) E) ,则则 LASTVT(E)编译原理CompilerPrinciples(3)(3)算符优先分析算法算符优先分析算法n归约过程中，归约过程中，只考虑终结符只考虑终结符之间的优先关系来之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用非终结符的归约，所以用算符优先分析法的规算符优
41、先分析法的规约过程与规范归约是不同的约过程与规范归约是不同的，P172.例子在下例子在下一页。一页。n为为解决在算符优先分析过程中如何寻找句柄的解决在算符优先分析过程中如何寻找句柄的问题问题，引入引入最左素短语最左素短语的概念的概念3. 算符优先文法算符优先文法(OPG) 之之 优先分析算法优先分析算法编译原理CompilerPrinciplesn算符文法的任一句型有如下形式：算符文法的任一句型有如下形式：#N#N1 1a a1 1N N2 2a a2 2.N.Nn na an nN Nn+1n+1# #, ,若若N Ni ia ai i.N.Nj ja aj jN Nj+1j+1为句为句柄，
42、则有柄，则有a ai-1i-1 a ai+1i+1n对于算符优先文法，如果对于算符优先文法，如果aNbaNb( (或或abab) )出现在句型出现在句型r r中中n若若ababab，则在则在r r中必含有中必含有a a而不含而不含b b的短语存在的短语存在n若若a=ba=b，则在则在r r中含有中含有a a的短语必含有的短语必含有b b，反，反之亦之亦然然 1） 算符优先分析句型的性质算符优先分析句型的性质编译原理CompilerPrinciples对输入串i+i#的规范归约的过程步骤步骤符号栈符号栈输入符号串输入符号串句柄句柄 1） # i+i# 2） #i +i# i 3） #F +i#
43、F 4） #T +i# T 5） #E +i# 6） #E+ i# 7） #E+i i# i 8） #E+F # F 9） #E+T # E+T10） #E #对输入串i+i的规范归约过程文法文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FP F|P(6) P(E)(7) Pi编译原理CompilerPrinciples对输入串i+i*i的算符优先分析过程算符优先关系表对输入串i+i#的算符优先归约过程步骤步骤符号栈符号栈输入符号串输入符号串移进或归约移进或归约 1） # i+i#移进移进 2） #i +i# 归约归约 3） #F +i# 移进移进
44、4） #F+ i#移进移进 5） #F+i #归约归约 6） #F+F #归约归约 7） #F # 接受接受文法文法GE：EE+E|E-E|E*E|E/E|E E|(E)|i编译原理CompilerPrinciplesn定义定义 cfgcfg G G 的句型的素短语是一个短的句型的素短语是一个短语，它语，它至少包含一个终结符至少包含一个终结符，且除自身外，且除自身外不再包含其他素短语不再包含其他素短语。处于句型最左边的。处于句型最左边的素短语为素短语为最左素短语最左素短语 2） 最左素短语最左素短语编译原理CompilerPrinciples文法文法GE：(1) EE+T(2) ET(3) T
45、T*F(4) TF(5) FP F|P(6) P(E)(7) Pi句型句型#T+T*F+i#其短语有：其短语有：T+T*F+iT+T*FTT*FiEET+ETF* FTTi最左素短语为：最左素短语为：T*F句型#N+N*N+i#的归约过程NN+NNi* NNN又如P173的图6.9 以及表6.4编译原理CompilerPrinciples句柄和素短语的区别：句柄和素短语的区别：GE:EE+T TEE+E E*E (E) idTT*F FF(E) idEE+T*FTFididTFidEE+E*EEididid编译原理CompilerPrinciplesn算法描述P174n流程图P175n例子：P
46、176及表6.5 算符优先分析算法描述算符优先分析算法描述编译原理CompilerPrinciples优先函数优先函数n优先函数比优先矩阵节省空间优先函数比优先矩阵节省空间n文法中有文法中有n个文法符号时，优先矩阵中有个文法符号时，优先矩阵中有(n+1)2个元素。个元素。如：假设某文法中有如：假设某文法中有99个终结符，其算符优先关系矩个终结符，其算符优先关系矩阵则有阵则有10000个元素，每个元素至少用个元素，每个元素至少用2个二进制位个二进制位来表示，也需要来表示，也需要20000位，即位，即2500个字节。个字节。n在实际应用中，往往用优先函数来代替优先矩阵来表在实际应用中，往往用优先函
47、数来代替优先矩阵来表示优先关系。具有示优先关系。具有n个终结符的算符文法（或具有个终结符的算符文法（或具有n个个文法符号的简单优先文法），只需文法符号的简单优先文法），只需2(n+1)个单元存放个单元存放优先函数。优先函数。n优先函数的构造优先函数的构造n用关系图构造优先函数用关系图构造优先函数n用迭代法构造用迭代法构造编译原理CompilerPrinciples优先函数的定义优先函数的定义 为了节约存储空间和便于执行比较运算为了节约存储空间和便于执行比较运算 ，定义两个定义两个优先函数优先函数f f和和g g，它们是从终结符号映射到整数的函数。对它们是从终结符号映射到整数的函数。对于文法符号
48、于文法符号R R和和S S，定义择定义择f f和和g,g,使之满足：使之满足：1 1当当RRSS时时,f(R),f(R)SS时时,f(R),f(R)g(S)g(S)。于是，于是，R R和和S S之间的优先关系，可以由比较之间的优先关系，可以由比较f(R)f(R)与与g(S)g(S)的大小来决定。的大小来决定。f:入栈优先函数；入栈优先函数；g:比较优先函数。比较优先函数。损失损失:错误检测能力降低，例如：错误检测能力降低，例如：id id不存在不存在,f(id)g(id)可比较。可比较。编译原理CompilerPrinciples优先函数优先函数 例子例子 简单表达式文法的算简单表达式文法的算
49、符优先关系矩阵：符优先关系矩阵：线性化后，优先函数为：线性化后，优先函数为： 在进行语法分析时，每当需要查询符号对在进行语法分析时，每当需要查询符号对( (S Si i,S,Sj j) )之间的之间的优先关系，比较优先关系，比较f(Sf(Si i) )和和g(Sg(Sj j）的大小即可。的大小即可。编译原理CompilerPrinciples关于优先函数的关于优先函数的3个重要事实个重要事实(1)(1)不是所有的优先矩阵都能线性化不是所有的优先矩阵都能线性化。aba=.b=f(a)=g(a)f(a)g(b)f(b)=g(a)f(b)=g(b)于是有：于是有：f(a)=g(b)编译原理Compi
50、lerPrinciples关于优先函数的关于优先函数的3 3个重要事实个重要事实(2)(2)对于给定的优先矩阵，若优先函数存在，则优对于给定的优先矩阵，若优先函数存在，则优先函数不唯一，即存在无穷多个先函数不唯一，即存在无穷多个f和和g满足条件。满足条件。+-*/()id$f335551771g224466161等价于等价于编译原理CompilerPrinciples关于优先函数的关于优先函数的3 3个重要事实个重要事实(3)(3)优先矩阵线性化后，每一对符号之间，都能优先矩阵线性化后，每一对符号之间，都能够进行比较。对于够进行比较。对于原先不存在优先关系的符原先不存在优先关系的符号对号对，因
51、为也能比较，所以，在分析过程中，因为也能比较，所以，在分析过程中，当输入串当输入串存在语法错误时，可能被掩盖（至存在语法错误时，可能被掩盖（至少是推迟发现）少是推迟发现）。编译原理CompilerPrinciples优先函数构造的优先函数构造的两种方法两种方法 BellBell法法1.有向图法有向图法(Bell法法)若优先文法中的所有符号（包括若优先文法中的所有符号（包括#)为为n个，个，A1,A2,An，则：则：作一个具有作一个具有2n个结点的有向图。通常的，分个结点的有向图。通常的，分为上下两排，各为上下两排，各n个结点，上面一排结点的个结点，上面一排结点的标记为标记为fAi，上排结点标记
52、为上排结点标记为gAi 。若若Ai . Aj ,则从则从fAi到到gAi画画一条箭弧。一条箭弧。若若Ai b=编译原理CompilerPrinciples优先函数构造优先函数构造BellBell法法 举例举例3 3课本例课本例6.19p179图图6.11当一个优先文法的优先关系矩阵的阶数比较高时，当一个优先文法的优先关系矩阵的阶数比较高时，bell法线性化过程很难手工实现。可以考虑用布尔矩阵法线性化过程很难手工实现。可以考虑用布尔矩阵来构造优先函数。下面介绍一个容易在计算机上实来构造优先函数。下面介绍一个容易在计算机上实现的算法。现的算法。编译原理CompilerPrinciplesBellB
53、ell法法 布尔矩阵实现优先函数的构造布尔矩阵实现优先函数的构造算法步骤：算法步骤：(1)作关系作关系.和和=的布尔矩阵的布尔矩阵FE(2)作关系作关系.和和=的布尔矩阵的转置矩阵的布尔矩阵的转置矩阵LET(3)根据上述含有根据上述含有2n个结点的有向图的作法可知，所构造的个结点的有向图的作法可知，所构造的有向图，可用如下的有向图，可用如下的2n阶矩阵来表示：阶矩阵来表示：其中，其中，I为为n阶单位矩阵。阶单位矩阵。(4)求求B的正闭包的正闭包B+。(5)f(Si)=B+中，第中，第i行中值为行中值为1的元素的个数的元素的个数g(Sj)=B+中，第中，第n+j行中值为行中值为1的元素的个数的元
54、素的个数B=IFELETI编译原理CompilerPrinciples用布尔矩阵构造优先函数用布尔矩阵构造优先函数 举例举例(1)(1)假设优先文法的优先矩阵为：假设优先文法的优先矩阵为：(1)FE矩阵为：矩阵为：=id+*$id0111+0101*0111$0001(2)LET矩阵为：矩阵为：id+*$id0111+0001*0101$0001编译原理CompilerPrinciples用布尔矩阵构造优先函数用布尔矩阵构造优先函数 举例举例(2)(2)(3)B矩阵为：矩阵为：10000111010001010010011100010001011110000001010001010010000
55、10001编译原理CompilerPrinciples用布尔矩阵构造优先函数用布尔矩阵构造优先函数 举例举例(3)(3)(3)B2矩阵为：矩阵为：1101011101010101011101110001000101111111000101010101011100010001B3=B2，所以，所以，B+=B1+B2=B2编译原理CompilerPrinciples用布尔矩阵构造优先函数用布尔矩阵构造优先函数 举例举例(4)(4)(4)优先函数为：优先函数为：1101011101010101011101110001000101111111000101010101011100010001id+*$f
56、6462g7352(5)对照优先矩阵检验对照优先矩阵检验编译原理CompilerPrinciples优先函数构造的优先函数构造的两种方法两种方法 FloydFloyd法法又称为逐次加又称为逐次加1法。法。假设假设x、y为优先文法的符号为优先文法的符号(算符文法为终结符算符文法为终结符)，有，有:(1)对于每一个对于每一个x，令，令f(x)=g(x)=1(2)对于对于x=g(y)，则令，则令g(y)=f(x)+1(3)对于对于x.y，若，若f(x)2n，则不会收敛，优先函则不会收敛，优先函数不存在。数不存在。编译原理CompilerPrinciples优先函数构造优先函数构造 FloydFloy
57、d法法 举例举例1(1)1(1)优先矩阵为：优先矩阵为：=(1) 设置初值：设置初值：id +*$f1111g1111(2) 根据（根据（2）：id +*$f1111g2221编译原理CompilerPrinciples优先函数构造优先函数构造 FloydFloyd法法 举例举例1(2)1(2)=(3) 根据（根据（3）：(4) 根据（根据（2）：id +*$f1111g2221id +*$f3331g2221id +*$f3331g4241编译原理CompilerPrinciples优先函数构造优先函数构造 FloydFloyd法法 举例举例1(3)1(3)=(5) 根据（根据（3）：(6)
58、 根据（根据（2）：id +*$f5351g4241id +*$f3331g4241id +*$f5351g6241编译原理CompilerPrinciples优先函数构造优先函数构造 FloydFloyd法法 举例举例1(4)1(4)(7) 过程已经收敛过程已经收敛与根据与根据Bell法求出的优先函法求出的优先函数比较：数比较：id +*$f5351g6241id+*$f6462g7352(8) 对照优先矩阵检验对照优先矩阵检验编译原理CompilerPrinciples优先函数构造优先函数构造 FloydFloyd法法 举例举例2 2 及比较及比较课本例课本例6.20 p180Bell和和
59、Floyd两种方法的比较两种方法的比较编译原理CompilerPrinciples利用优先函数进行语法分析利用优先函数进行语法分析 举例举例1 1分析符号串分析符号串 i + i * i 。对输入串i+i*i的算符优先分析过程优先函数步骤步骤符号栈符号栈输入符号串输入符号串移进或归约移进或归约 1） # i+i*i#移进移进 2） #i +i*i# 归约归约 3） #F +i*i# 移进移进 4） #F+ i*i#移进移进 5） #F+i *i#归约归约 6） #F+F *i#归约归约i+ * #f5 3 5 1g 6 2 4 1 7） #F+F* i# 移进移进 8） #F+F*i # 归约
60、归约 9） #F+F*F # 归约归约 10） #F+F # 归约归约 11） #F # 归约归约编译原理CompilerPrinciples利用优先函数进行语法分析利用优先函数进行语法分析 举例举例2 2分析符号串分析符号串 i + i i* i 。对输入串i+i*i的算符优先分析过程步骤步骤符号栈符号栈输入符号串输入符号串移进或归约移进或归约 1） # i+ii*i#移进移进 2） #i +ii*i# 归约归约 3） #F +ii*i# 移进移进 4） #F+ ii*i#移进移进 5） #F+i i*i#移进移进 6） #F+ii *i#归约归约 7） #F+iF *i# 归约归约i+ *
61、 #f5 3 5 1g 6 2 4 1 8） #F+FF *i# 移进移进 9） #F+FF*i i# 归约归约 10） #F+FF*F # 归约归约 11） #F+F # 归约归约 12） #F # 接受接受=编译原理CompilerPrinciples利用优先函数进行语法分析利用优先函数进行语法分析 练习练习1 1设有文法设有文法GS:GS:S - S;D | DS - S;D | DD - D(T)| HD - D(T)| HH - a |(S)H - a |(S)T - T+S | ST - T+S | S求算符优先关系矩阵和优先函数，并分析串求算符优先关系矩阵和优先函数，并分析串 (
62、a+a)#(a+a)#。编译原理CompilerPrinciples算符优先分析方法的局限性算符优先分析方法的局限性设有文法设有文法GS:GS:编译原理CompilerPrinciples简单优先分析法和算符优先分析法的比较简单优先分析法和算符优先分析法的比较课本课本 P183 P183 表表6.156.15编译原理CompilerPrinciples实验二：语法分析器的实现实验二：语法分析器的实现设有文法设有文法GEGE:(0) E(0) E#E#E#(1) EE+T(1) EE+T(2) ET(2) ET(3) TT*F(3) TT*F(4) TF(4) TF(5) FP(5) FP F|PF|P(6) P(6) P(E)(E)(7) Pi(7) Pi求算符优先关系矩阵和优先函数，并分析串以求算符优先关系矩阵和优先函数，并分析串以# #结尾的结尾的符号串。符号串。编译原理CompilerPrinciples算符优先分析法的局限性算符优先分析法的局限性n一般语言的方法很难满足算符优先文法的条件n很难避免把错误的句子得到正确的归约编译原理CompilerPrinciples 下课了。下课了。休息一会儿。休息一会儿。编译原理CompilerPrinciples
