自底向上优先分析法ppt课件

1、编译原理编译原理第第6 6章章 自底向上优先分析法自底向上优先分析法 自底向上优先分析概述 简单优先分析 算符优先分析编译原理编译原理自底向上分析方法自底向上分析方法 自底向上分析方法，也称移进-归约分析法。 实现思想： 对输入符号串自左向右进展扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串构成某个句型的句柄时，该句型对应某产生式的右部，就用该产生式的左部非终结符替代相应右部的文法符号串，这称为归约。 反复这一过程直到归约到栈中只剩文法的开场符号时那么为分析胜利，也就确认输入串是文法的句子。S10 #aAcBe # 归约归约(SaAcBe)文法文法GS：1 S aAcB

2、e2 A b3 A Ab4 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 # 接受接受分析符号串分析符号串abbcdeabbcde能否为能否为GSGS的句子？的句子？对输入串abbcde#的移进-规约分析过程SaAcBe aAc

3、de aAbcde abbcde编译原理编译原理算法应思索的问题算法应思索的问题 算法能否可以终止？算法能否可以终止？ 算法能否快速？算法能否快速？ 算法能否可以处置一切的情况？算法能否可以处置一切的情况？ 在每一步中如何选择子串进展归约？在每一步中如何选择子串进展归约？编译原理编译原理自下而上语法分析的战略：移进自下而上语法分析的战略：移进- -规约分析。规约分析。移进就是将一个终结符推进栈。移进就是将一个终结符推进栈。归约就是将归约就是将0 0个或多个符号从栈中弹出，根个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈。据产生式将一个非终结符压入栈。移进移进- -归约过程是自顶向下最右

4、推导的逆过归约过程是自顶向下最右推导的逆过程规范归约。程规范归约。编译原理编译原理 简单优先分析法 对一个文法按一定原那么求出该文法一切符号终结符和非终结符之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约实践上是一种规范归约。 算符优先分析法 只规定算符终结符之间的优先关系。找到句柄就归约，不是规范归约。优先分析法优先分析法编译原理编译原理简单优先分析法简单优先分析法 按照文法符号包括终结符和非终结符 的优先关系确定句柄。编译原理编译原理文法文法GSGS：1 1 S bAb S bAb2 2 A A B|aB|a3 3 B Aa B AaSbA(Ba)#Sb=A=(=a=)#步骤步骤

5、符号栈符号栈输入符号串输入符号串动作动作 1 # baab# #b,移进移进 2 #b aab# b,移进移进 3 #b aab# a,归约归约Aa 5 #bA ab# A=a,移进移进 6 #bAa b# a=,移进移进 7 #bAa b# b,归约归约BAa 8 #bB b# Bb,归约归约AB 9 #bA b# A=b,移进移进10 #bAb # b#,归约归约SbAb11 #S # 接受接受对输入串baa#的简单优先分析过程简单优先关系矩阵编译原理编译原理优先关系优先关系优先关系优先关系X=Y 文法文法G中存在产生式中存在产生式A.XY.XY 文法文法G中存在产生式中存在产生式A.BD

6、.，且且B .X,D Y.如何确定两个文法符号之间的优先关系？如何确定两个文法符号之间的优先关系？*编译原理编译原理简单优先文法的定义简单优先文法的定义 满足以下条件的文法是简单优先文法1在文法符号集V中，恣意两个符号之间最多只需一种优先关系成立。2在文法中恣意两个产生式没有一样的右部。3不含空产生式。编译原理编译原理简单优先分析法简单优先分析法根据优先文法构造相应优先关系矩阵，并将文法的产生式保管，设置符号栈S，算法步骤如下：将输入符号串a1a2a3.an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止。栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号a

7、k，即找到ak-1ak为止。由句柄ak.ai在文法的产生式中查找右部为ak.ai的产生式，假设找到那么用相应左部替代句柄，假设找不到那么为出错，这时可断定输入串不是该文法的句子。反复上述三步，直到归约完输入符号串，栈中只剩文法的开场符号为止。编译原理编译原理如何确定优先关系？如何确定优先关系？文法文法GS：1 S bAb2 A B|a3 B Aa1.求求=关系：关系：由由1：b=A A=b由由2：=B由由3：A=a a=2.求求关系：关系：由由12：b ba由由23：A 关系：关系：由由1：Bb ab b由由3：Ba aa a4.#SbA(Ba)#Sb=A=(=a=)#编译原理编译原理算符优先

8、分析法算符优先分析法 某些文法具有“算符特性 表达式运算符优先级、结合性 人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性 只思索算符之间的优先关系来确定句柄编译原理编译原理文法文法GE：EE+E|E-E|E*E|E/E|EE|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、9 #E+E*E # +#,规约规约10 #E+E # #,规约规约11 #E # 接受接受对输入串对输入串i+ii+i* *i i的算符优先分析过程的算符优先分析过程+ - * / ()i #+ -* / (= i# -*/ (=i# =算符优先关系表算符优先关系表编译原理编译原理算符文法的定义算符文法的定义 定义定义 假设不含空产生式的上下文无关文法假设不含空产生式的上下文无关文法 G G 中没有形如中没有形如 U UVWVW的产生式，其中的产生式，其中V,WVNV,WVN那么称那么称G G 为算符文法为算符文法OGOG。 性质性质1 1：在算符文法中任何句型都不包含两个：在算符文法中任何

10、句型都不包含两个相邻的非终结符相邻的非终结符. .数学归纳法数学归纳法 性质性质2 2：如：如 Vx Vx 或或 xV xV 出如今算符文法的句型出如今算符文法的句型 中，其中中，其中VVN,xVT, VVN,xVT, 那么那么 中任何含中任何含 x x 的短语必含有的短语必含有V.V.反证法反证法编译原理编译原理算符优先关系的定义算符优先关系的定义在在OGOG中中 定义定义 算符优先关系算符优先关系x = y Gx = y G中有形如中有形如.U.Uxyxy或或U U xVy. xVy.的产的产生式。生式。x y Gx y Gxy G中有形如中有形如.U .U Wy Wy的产生式的产生式,

11、,而而 W xW x或或W xVW xV规定规定 假设假设 S x S x或或S Vx S Vx 那么那么 # x # # x #编译原理编译原理算符优先文法的定义算符优先文法的定义 在 OG文法 G 中，假设恣意两个终结符间至多有一种算符优先关系存在，那么称G 为算符优先文法OPG。 留意：允许bc,cb;不允许bc,bc,b=c 结论： 算符优先文法是无二义的。编译原理编译原理算符优先关系表的构造算符优先关系表的构造由定义直接构造由定义直接构造由关系图法构造算符优先关系表由关系图法构造算符优先关系表编译原理编译原理 首先引入两个概念首先引入两个概念 FIRSTVTFIRSTVTB B=b|

12、B b=b|B b或或B Cb.B Cb.对于非终结符对于非终结符B B，其往下推导所能够呈现的首，其往下推导所能够呈现的首个算符。个算符。 LASTVTLASTVTB B=a|B a=a|B a或或B . aCB . aC对于非终结符对于非终结符B B，其往下推导所能够呈现的最，其往下推导所能够呈现的最后一个算符。后一个算符。编译原理编译原理如何计算算符优先关系如何计算算符优先关系1 =关系关系直接看产生式的右部，假设呈现了直接看产生式的右部，假设呈现了A ab或或A aBb,那么那么a=b。2关系关系求出每个非终结符求出每个非终结符B的的FIRSTVTB， 假设假设AaB,那么那么bFIR

13、STVTB,那么那么a关系关系求出每个非终结符求出每个非终结符B的的LASTVTB， 假设假设ABb,那么那么aLASTVTB,那么那么ab。编译原理编译原理文法文法GE：0 E#E#1 EE+T2 ET3 TT*F4 TF5 FPF|P6 PE7 PiFIRSTVTE=#FIRSTVTE=+,*,iFIRSTVTT=*,iFIRSTVTF=,iFIRSTVTP=,iLASTVTE=#LASTVTE=+,*,iLASTVTT=*,iLASTVTF=,iLASTVTP=,i+-*/ ()i#+-*/ (=i#=1=关系关系由产生式由产生式0和和6,得得#=#，=2关系关系找形如：找形如：AaB的

14、产生式的产生式#E：那么：那么#FIRSTVTE+T: 那么那么+FIRSTVTT *F: 那么那么*FIRSTVTFF:那么那么 FIRSTVTFE: 那么那么 关系关系找形如：找形如：ABb的产生式的产生式E# ,那么那么 LASTVTE#E+ ,那么那么 LASTVTE+ T* ,那么那么 LASTVTT* P ,那么那么 LASTVTP E ,那么那么 LASTVTE编译原理编译原理算符优先分析算法算符优先分析算法 归约过程中，只思索终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的，P110. 为处置在算符优

15、先分析过程中如何寻觅句柄，引进最左素短语的概念。编译原理编译原理最左素短语最左素短语 算符文法的任一句型有如下方式：#N1a1N2a2.NnanNn+1#,假设Niai.NjajNj+1为句柄，那么有 ai-1 ai+1 对于算符优先文法，假设aNb或ab出如今句型r中 假设ab，那么在r中必含有a而不含b的短语存在。 假设a=b，那么在r中含有a的短语必含有b，反之亦然。 定义 cfg G 的句型的素短语是一个短语，它至少包含一个终结符，且除本身外不再包含其他素短语。处于句型最左边的素短语为最左素短语。编译原理编译原理文法文法GEGE：1 1 EE+T EE+T2 2 ET ET3 3 TT TT* *F F4 4 TF TF5 5 FPFPF|PF|P6 6 P PE E7 7 Pi Pi句型句型#T+T*F+i#其短语有：其短语有：T+T*F+iT+T*FTT*FiEET+ETF