第六章自底向上优先分析.

1盛威网：专业的计算机学习网站指导教师:杨建国二零零七年十一月2盛威网：专业的计算机学习网站第6章自底向上优先分析语法分析推导自上而下的语法分析过程预测分析程序，递归下降分析法（最左推导）注：要求文法是LL(1)文法归约自下而上的语法分析过程简单优先分析法，算符优先分析法，LR分析法3盛威网：专业的计算机学习网站1.自底向上优先分析概述2.简单优先分析（优先关系的理解）3.算符优先分析确定句型的短语、直接短语、句柄、素短语、最左素短语算符优先关系矩阵的构造及输入串的过程分析学习目标4盛威网：专业的计算机学习网站第一节自底向上优先分析概述第二节简单优先分析法第三节算符优先分析法第四节典型例题及解答教学内容5盛威网：专业的计算机学习网站知识结构6盛威网：专业的计算机学习网站从输入串开始，逐步进行“归约”，直至归约到文法开始符号；或者说，从语法树的末端开始，步步向上“归约”，直到根结点。7盛威网：专业的计算机学习网站引言1.基本思想自下而上的语法分析过程是一个最左归约的过程，从输入串开始，朝着文法的开始符号进行归约，直到到达文法的开始符号为止的过程。从语法树角度看，是以输入符号串作为语法树的末端结点符号串，自底向上地构造语法树，使文法开始符号正好是该语法树的根。如果最终根结点是开始符号，则输入符号串是语言的一个句子，否则不是。自底向上分析过程实际上是一个不断进行直接归约的过程。注意：输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列。8盛威网：专业的计算机学习网站分析过程是重复以下步骤：1、找出当前句型的句柄x（或句柄的变形）2、找出以x为右部的规则X→x3、把x规约为X，产生语法树的一枝关键：找出当前句型的句柄x(或其变形），这不是很容易。9盛威网：专业的计算机学习网站2.实现方式-“移进－归约”方式语法分析程序语法表a+b……#输出带#自左至右把输入串的符号逐个移进栈【注】初态时栈内仅有栈底符“＃”，读头指在最左边的单词符号上。若栈顶形成某个句型的句柄，就将此句柄用相应的产生式左部替换（归约），若再形成句柄，就继续替换，直到栈顶不再形成句柄为止。重复上面的过程直到栈顶只剩下#和文法的开始符号，同时输入串读完为止，这样就认为识别了一个句子。10盛威网：专业的计算机学习网站3.语法分析程序执行的动作移进读入下一个输入符号并压入栈内，读头后移；归约检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式；接受移进－归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符；报错当识别程序察觉一个错误，因此输入符号串不是句子而无法继续识别工作时，调用一个出错处理子程序进行处理或停止。11盛威网：专业的计算机学习网站例1：文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabbcde步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcde#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8）#aAcde#归约(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约(S→aAcBe)符号串abbcde是否是G[S]的句子对输入串abbcde#的移进-归约分析过程SaAcBeaAcdeaAbcdeabbcde12盛威网：专业的计算机学习网站顺序扫描输入符号并依次移进栈栈顶部的符号串是否构成一句柄？YN进行一次归约输入串扫描完否？noY栈中仅有开始符号？noerror输入串合法，报告分析报告出口移进-归约过程Y13盛威网：专业的计算机学习网站（1）例子的分析过程是一步步地归约当前句型的句柄该句子的唯一语法树为:aAcBeAbbdS注意两点：（a）栈内符号串+未处理输入符号串=当前句型（b）句柄都在栈顶实际上，以上分析过程并未真正解决句柄的识别问题说明:14盛威网：专业的计算机学习网站（2）未真正解决句柄的识别*上述分析过程是怎样识别句柄的，主要看栈顶符号串是否形成规则的右部。这种做法形式上是正确的，但在实际上不一定正确。举例的分析过程可以说是一种巧合。因为不能认为:对句型xuy而言，若有U→u，即Uu就断定u是简单短语，u就是句柄，而是要同时满足ZxUy15盛威网：专业的计算机学习网站一.优先分析法的类别§6.1自底向上优先分析概述1.优先分析器（PrecedenceParser）•简单优先分析法•算符优先分析法2.LR分析器16盛威网：专业的计算机学习网站二.简单优先分析法基本思想：按一定原则定义文法中所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄并实行归约。是一种规范归约。简单优先分析法准确、规范，但效率低，不实用，不流行。17盛威网：专业的计算机学习网站三.算符优先分析法基本思想：只定义文法中终结符之间的优先关系（不考虑非终结符），并由这种关系指导分析过程不是规范归约算符优先分析法分析速度快，特别适用于表达式的分析。缺点是不规范，常常要采用适当措施克服其缺点。18盛威网：专业的计算机学习网站§6.2简单优先分析法一.优先关系的符号表示6.2.1优先关系＝...XY表示X和Y的优先关系相等XY表示X的优先性比Y的优先性大XY表示X的优先性比Y的优先性小19盛威网：专业的计算机学习网站二.优先级别定义（4）对任何X，若文法开始符号SX…,则＃X;若有S…X，则X＃。＝...+*.+.++（1）XY当且仅当G中存在产生式规则A…XY…（2）XY当且仅当G中存在产生式规则A…XB…，且BY…（3）XY当且仅当G中存在产生式规则A…BD…,且B…X和DY…20盛威网：专业的计算机学习网站三.从语法树判别优先性•设G是已化简的文法,s,tV,若G中存在规范句型=…st…,则s,t与的句柄之间的关系必有下述情况之一:1.s在句柄中,而t不在句柄中2.s与t均在句柄中3.s不在句柄中,而t在句柄中对于上述情况,我们规定：情况1:st;情况2:s=t;情况3:stA……st...A……st…...A……st…...21盛威网：专业的计算机学习网站另外,还有一种情况,就是s和t均不在句柄中,那么一定存在某句型使得它们进入上述三种情况之一。若s和t在任何句型中都不可能相邻出现,则我们规定二者无关系。注意,这种优先关系是不对称的!22盛威网：专业的计算机学习网站在句型中，句柄内各相邻符号之间具有相同的优先级。结论由于句柄要先归约，所以规定句柄两端符号的优先级要比位于句柄之外的相邻符号的优先级高。句型中Ni……Nj是句柄，则N1…Ni-1Ni……NjNj+1…Nn.＝.＝..【注】优先分析法基本思想也可以表述为：若句型中Ni……Nj是句柄，语法分析程序可以通过寻找Ni-1Ni和NjNj+1这两个关系来确定句柄的头尾，从而确定句柄进行归约。..23盛威网：专业的计算机学习网站我们可以通过两个相邻符号SiSi+1之间的关系来找到句柄：–SiSi+1在句柄内：必然有规则U→…SiSi+1…–Si在句柄内部，但是Si+1在句柄之后，必然有规则U→…Si，且存在规范句型…USi+1…。–如果Si+1在句柄内，而Si在句柄外，那么必然存在规范句型…SiU…，且有U→Si+1…。24盛威网：专业的计算机学习网站如何确定优先关系？例2文法G[S]：(1)S→bAb(2)A→(B|a(3)B→Aa)1.求=关系：由(1)：b=AA=b由(2)：(=B由(3)：A=aa=)注意：行列与左右，空SbA(Ba)#Sb=A==(=Ba=)#4.#所有相邻符号，所有相邻符号#3.求关系：由(1)：Bbab)b由(3)：Baaa)a2.求关系：由(1)(2)：bba由(2)(3)：(A(((a简单优先关系矩阵25盛威网：专业的计算机学习网站上述关系用语法树的结构如下图：26盛威网：专业的计算机学习网站若一个文法是简单优先文法必须满足以下条件：（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立（2）在文法中任意两个产生式没有相同的右部（3）不含空产生式6.2.2简单优先文法的定义第一点保证可以识别出句柄。第二点保证可以确定归约到哪个非终结符号。27盛威网：专业的计算机学习网站6.2.3简单优先分析法的操作步骤由ai向左在栈中找，倘若某两个相邻的符号满足ak-1ak，则终止寻找，ak就是我们要找的句柄的头。第一步：找句柄尾将输入符号串a1a2…an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止，栈顶当前符号ai为句柄尾.第二步：找句柄头.28盛威网：专业的计算机学习网站由句柄ak…ai在文法的产生式中查找右部为ak…ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，此时可断定输入串不是该文法的句子第三步：找产生式最后，重复第一、二和三步直到归约完输入符号串，栈中只剩文法的开始符号为止29盛威网：专业的计算机学习网站简单优先分析技术流程图开始S[1]#，i,j1M[S[i],tr[j]]=errorS[i]tr[j]kiS[k-1]S[k]kk-1=S[k]S[k+1]S[i]是句柄，用它查产生式表与一产生式右部相同S[i]=#且tr[j]=#结束ik，S[i]UU是该产生式左部符号errorii+1S[i]tr[j]jj+1YNNYYNYYNerrorN30盛威网：专业的计算机学习网站文法G[S]：(1)S→bAb(2)A→(B|a(3)B→Aa)SbA(Ba)#Sb=A==(=Ba=)#步骤符号栈输入符号串动作1）#b(aa)b#2）#b(aa)b#3）#b(aa)b#4）#b(aa)b#5）#b(Aa)b#6）#b(Aa)b#7）#b(Aa)b#8）#b(Bb#9）#bAb#10）#bAb#11）#S#对输入串b(aa)b#的简单优先分析过程简单优先关系矩阵注意：何时移进，何时归约？归约中如何确定句柄？#b(a#b,移进b(,移进(a,移进aa,用A→a归约A=a,移进a=),移进#b(Aa))b,用B→Aa)归约#b(BBb,用A→(B归约A=b,移进#bAbb#,用S→bAb归约接受31盛威网：专业的计算机学习网站6.2.4简单优先分析法的优缺点优点：技术简单缺点：适用范围小，分析表尺寸太大。32盛威网：专业的计算机学习网站6.2.5简单优先分析法的局限性※简单优先分析法是有局限性的，它只适应于简单优先文法，但是程序设计语言的文法一般都不是简单优先文法，即使是关于表达式的文法也不是简单优先文法。如果要使用简单优先文法，就必须修改相应语言的文法，使之成为简单优先文法。例3设文法G：EE+T|TTT*F|FE（E）|i33盛威网：专业的计算机学习网站【解】因为有EE+T，所以有+=T，但由于TT*F，所以有+T，从上面的分析我们可以看出在+和T之间存在两种简单优先关系，所以关于简单算术表达式的文法不是一个简单优先文法，因而不能使用简单优先分析法，当然,此文法也可能修改成简单优先文法。上述文法就可以改为：G’：EEEE+T|TTTTT*F|FE（E）|i34盛威网：专业的计算机学习网站§6.3算符优先分析法问题的提出例4若有文法G为：（1）EE+E（2）EE*E（3）Ei35盛威网：专业的计算机学习网站步骤栈S当前输入符输入串剩余部分动作对输入串i1+i2*i3的归约过程：（1）＃i1+i2*i3#移进（2）＃i1+i2*i3#归约(3)（3）＃E+i2*i3#移进（4）＃E+i2*i3#移进（5）＃E+i2*i3#归约(3)（6）＃E+E*i3#移进（7）＃E+E*i3#移进（8）＃E+