编译原理第六章-自底向上优先分析法.pptx

第六章 自底向上优先分析法第一页，共七十三页。自底向上优先分析法慨述简单优先分析算符优先分析第二页，共七十三页。6.1 自底向上语法分析概述如名字如示，自底向上语法分析试图将一个字符串反向归约至开始符号。自底向上语法分析比自上而下语法分析更有效率，对语法的限制更少第三页，共七十三页。自底向上语法分析的策略：移进-规约分析；移进就是将一个终结符推进栈归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈移进-归约过程是自顶向下最右推导的逆过程（规范归约）第四页，共七十三页。例6.1设文法G[s]为: (1)S ? aAcBe (2)A? b (3)A? Ab (4)B? d对输入串abbcde进行分析，检查该符号串是否是G[s]的句子。分析：容易看出对输入串abbcde的最右推导是： S＝>aAcBe＝>aAcde＝>aAbcde＝>abbcde由此我们可以构造它的逆过程即归约过程。第五页，共七十三页。自底向上分析的关键问题: 如何确定句柄。第六页，共七十三页。自底向上优先分析法慨述简单优先分析算符优先分析第七页，共七十三页。6.2 简单优先分析法按照文法符号（包括终结符和非终结符）的优先关系确定句柄。第八页，共七十三页。6.2.1 优先关系优先关系X=Y ? 文法G中存在产生式A→...XY...X<Y? 文法G中存在产生式A→...XB...，且B Y...X>Y? 文法G中存在产生式A→...BD...，且B ...X,D Y...如何确定两个文法符号之间的优先关系？(按定义求优先关系，P96)···第九页，共七十三页。6.2.2 简单优先文法的定义满足以下条件的文法是简单优先文法（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。（2）在文法中任意两个产生式没有相同的右部第十页，共七十三页。6.2.3 简单优先分析法算法步骤如下：第十一页，共七十三页。文法G[S]：(1) S → bAb(2) A → (B|a(3) B → Aa)步骤符号栈输入符号串动作 1） # b(aa)b# #<b,移进 2） #b (aa)b# b<(,移进 3） #b( aa)b# (<a,移进 4） #b(a a)b# a>a,归约A→a 5） #b(A a)b# A=a,移进 6） #b(Aa )b# a=),移进 7） #b(Aa) b# )>b,归约B→Aa) 8） #b(B b# B>b,归约A→(B 9） #bA b# A=b,移进10） #bAb # b>#,归约S→bAb11） #S # 接受对输入串b(aa)#的简单优先分析过程简单优先关系矩阵第十二页，共七十三页。自底向上优先分析法慨述简单优先分析算符优先分析第十三页，共七十三页。6.3 算符优先分析法某些文法具有“算符”特性表达式运算符（优先级、结合性）人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性只考虑算符之间的优先关系来确定句柄第十四页，共七十三页。6.3.1 直观算符优先分析法文法G[E]：E→E+E|E-E|E*E|E/E|E?E|(E)|i（1） ?优先级最高，右结合（2）*和/优先级次之，左结合（3）+和-优先级最低，左结合（4）括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号（5）#的优先性低于与其相邻的算符算符优先关系表第十五页，共七十三页。文法G[E]：E→E+E|E-E|E*E|E/E|E?E|(E)|i步骤符号栈输入符号串动作 1） # i+i*i# #<i,移进 2） #i +i*i# #<i>+,规约 3） #E +i*i# #<+,移进 4） #E+ i*i# +<i,移进 5） #E+i *i# +<i>*,规约 6） #E+E *i# +<*,移进 7） #E+E*