样题与课件编译原理第6章

1、1第六章自底向上的优先分析法2它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，(该句柄对应某产生式的右部)，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，6.1 自底向上分析概述 自底向上分析法(或自下而上分析)，也称移进-归约分析法。由于自底向上分析的移进-归约过程是自顶向下最右推导的逆过程，而最右推导为规范推导，自左向右的归约过程也称规范归约。3例(P102)SaAcBe aAcde aAbcde abbcde由此我们可以构造它

2、的逆过程即归约过程。先设一个先进后出的符号栈，并把句子左括号“#”号放入 栈底，其分析过程如下页：设文法GS为：(1) SaAcBe(2) Ab(3) AAb(4) Bd对输入串abbcde#进行分析，检查该符号串是否是GS的句子。容易看出对输入串abbcde的最右推导是：4文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dabbcde步骤符号栈输入符号串动作 1） # abbcde# 移进 2） #a bbcde# 移进A 3） #ab bcde# 归约(Ab) 4） #aA bcde# 移进A 5） #aAb cde# 归约(AAb) 6） #aA cde# 移进

3、 7） #aAc de# 移进B 8） # aAcd e# 归约(Bd) 9） #aAcB e# 移进11） #S # 接受S10） #aAcBe # 归约SaAcBeaAcdeaAbcdeabbcde5在上述移进-归约或自底向上构造语法树的过程中，我们怎么知道何时移进，何时归约，不能只简单地看成栈顶出现某一产生式的右部就可用相应产生式归约，例如在上表分析到第5)步时栈中的符号串是#aAb，栈顶符号串b和Ab分别是产生式(2)，(3)的右部，这时到底用(2)归约还是用(3)归约是自底向上分析要解决的关键问题。由此可见自底向上分析的关键问题是在分析过程中如何确定句柄，也就是说如何知道何时在栈顶符

4、号串中已形成某句型的句柄，那么就可以确定何时可以进行归约。66.2简单优先分析法6.2.1 优先关系 首先定义优先关系的表示: X Y表示X的优先性等于Y。 X Y表示X的优先性低于Y X Y表示X的优先性高于Y。优先关系是有序的， X Y不一定Y X；X Y不一定Y X；X Y不一定Y X；简单优先分析法是按照文法符号(终结符和非终结符)的优先关系确定句柄的.因此,首先要介绍两个文法符号的优先关系如何确定.7(1)X Y 当且仅当G中存在产生式AXY(2)X Y 当且仅当G中存在产生式AXB,且B Y(3)X Y 当且仅当G中存在产生式ABD, 且B X和D Y见P104-105页的例题6.

5、2简单优先文法的定义(P105)简单优先分析法 (P105)86.3 算符优先分析法 算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。9如何确定算符优先关系？人为确定：（1）i的优先级最高（1） 优先级次于i，右结合（2）*和/优先级次之，左结合（3）+和-优先级最低，左结合（4）括号(,)的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号（5）#的优先性低于与其相邻的算符算符优先关系表10例如:若有文法G为：(1) EE+E(2) EE*E(3) Ei对输入串i+i*i的归约过程可表示为表

6、6.3。步骤 栈当前输入字符剩余输入串动作1i+i*i#+ 归约3E+i*i#+移进4#E+i*i#+* 归约6#E+E*i#+*移进7#E+E*i#*#归约9#E+E*E#*#归约10#E+E#+#归约11#E#接受11 算符优先文法的定义定义：如果不含空产生式的上下文无关文法 G 中没有形如 ABC的产生式，其中B，CVN 则称G 为算符文法（OG）。例6.1 GE：EE+E|E*E|i 是OG文法性质1：在算符文法中任何句型都不包含两个相邻的非终结符.（证明P108，用归纳法证明）性质2：如 Ab 或 bA 出现在算符文法的 句型 中，其中 AVN，bVT， 则 中任何 含 b 的短语必

7、含有A。（注意：含A的短语不一定含b)用反证法P10812证明：性质1用归纳法设是句型，即S S=0 1 . n-1 n=推导长度为n，归纳起点n=1时，S=0 1=，即S ，必存在产生式S，而由算符文法的定义，文法的产生式中无相邻的非终结符，显然满足性质1。假设n1, n-1满足性质1。若n-1=A，A为非终结符。由假设的尾符号和的首符号都不可能是非终结符，否则与假设矛盾。又若A是文法的产生式，则有n-1 n=而A是文法的原产生式，不含两个相邻的非终结符，所以也不含两个相邻的非终结符。满足性质1。证毕。 13 证明：性质2用反证法。因为由算符文法的性质1知可有：S =bA若存在B b，这时b

8、和A不同时归约，则必有S BA, 这样在句型BA中存在相邻的非终结符B和A，所以与性质1矛 盾，证毕。注意：含b的短语必含A，含A的短语不一定含b。14算符优先关系的定义：在OG中 定义 （算符优先关系） a = b G中有形如：Aab 或A aBb.的产生式。 a b G中有形如: A Bb的产生 式,而 B a 或 B aC规定 若 S a或 S Ca 则 # #15在 OG文法 G 中，若任意两个终结符间至多有一种算符优先关系存在，则称G 为算符优先文法(OPG)。注意：不允许 bc, b+*+16算符优先关系表的构造首先定义如下两个集合：FIRSTVT(B)=bB b 或 B CbLA

9、STVT(B)=aB a 或 B aC按如下算法计算出给定文法中任何两个终结符对(a,b)之间的优先关系： 1) =关系直接看产生式的右部，若出现了A ab或 A aBb,则a=b 2)关系求出每个非终结符B的FIRSTVT(B)若AaB,则bFIRSTVT(B),则ab 即a关系求出每个非终结符B的LASTVT(B)若ABb,则aLASTVT(B),则ab 即 LASTVT(B)b17如何求FIRSTVT集:若有产生式A a 或A Ba 则aFIRSTVT(A)若a FIRSTVT(B)且有产生式A B 则a FIRSTVT(A)如何求LASTVT集:若有产生式A a或A aB 则aLAST

10、VT(A)若a LASTVT(B)且有产生式A B则a LASTVT(A)18计算算符优先关系例文法GE： (0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|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)=),i先计算每个非终结符的FirstVt集和LastVt集19(0)E#E# (1) EE

11、+T (2) ET (3) TT*F (4) TF(5) FPF|P (6) P(E) (7) Pi3)关系找形如：ABb的产生式E#: 则 LASTVT(E)#E+: 则 LASTVT(E)+ T*: 则 LASTVT(T)* P: 则 LASTVT(P) E): 则 LASTVT(E)2）关系找形如AaB的产生式#E：则 #FIRSTVT(E)+T: 则 +FIRSTVT(T) *F: 则 *FIRSTVT(F)F: 则 FIRSTVT(F)(E: 则 (FIRSTVT(E)1)=关系由产生式(0)和(6),得#=#， ( = )20表达式文法GE的算符优先关表21算符优先分析算符优先分析

12、的可归约 串是句型的最左素短语定义 G 的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。即素短语必须满足下列两个条件:1、至少包含一个终结符号。2、该短语不再包含满足第一个条件的更小的短语。处于句型最左边的素短语为最左素短语 22文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi句型T+T*F+i其短语有：T+T*F+iT+T*FTT*FiEET+ETF*FTTi句型T+T*F+i的最左素短语为：T*FE+TFE句型T+T*F+i的素短语为：T*F， iETTi句型T+T+i的素短语是: T+T 和 i

13、,其中最左素短语:T+T23课堂练习：分别求句型Ei、E+F的短语、简单短语、句柄、素短语、最左素短语 E T F + i E短语：E+i, i简单短语： i句柄：i素短语：i最左素短语：i短语：E+F, F简单短语：F句柄：F素短语： E+F最左素短语： E+F E T F + E例: 文法GE EE+T|T TT*F|F F(E)|i24算符优先分析算法前面介绍了如何对已给定的文法按其产生式构造算符优先关系表，有了算符优先关系表并满足算符优先文法时，我们就可以对任意给定的符号串进行归约分析，进而判定输入串是否为该文法的句子。然而用算符优先分析法的归约过程与规范归约是不同的。例：表达式文法：

14、(0)E#E# (1) EE+T (2) ET (3) TT*F (4) TF(5) FPF|P (6) P(E) (7) Pi对i+i#的规范规约和算符优先规约见P115表6.7和表6.8注意在算符优先分析过程中，因去掉了单非终结符之间的归约，非终结符的名字没有任何意义。所以在归约过程中所有的非终结符都用同一个名字。 25 算符优先文法句型的性质算符文法的任何一个句型应为如下形式：N1a1N2a2 . Nnan Nn+1其中N k(1kn+1)为非终结符或空，ak(1kn)为终结符算符优先文法句型的最左素短语NiaiNi+1ai+1 . Njaj Nj+1满足：ai-1 aiai =ai+1

15、 = =aj-1 =ajaj aj+1即：ai-1 aj+1 算符优先分析过程归约时，只能把 和 之间的符号串作为可归约串进行归约。26 算符优先分析句型有如下性质：如果aNb(或ab)出现在句型r中，则a和b之间有且只有一种 优先关系,即：若a b则在r中必含有b而不含a的短语存在。若a b则在r中必含有a而不含b的短语存在。若a b则在r中含有a的短语必含有b，反之亦然。27由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。例如，下述文法是一个算符优先文法，其产生式为：SS;D|DDD(T)|HHa|(S)TT+S|S其中VNS，D，T，H，VT；,(,),a,+，S为