编译原理自底向上的语法分析方法公开课一等奖省优质课大赛获奖课件

第6章自底向上优先分析法1主要内容6.1自底向上优先分析概述6.3算符优先分析法2课题：自底向上分析方法、算符优先文法目标要求：1.了解自底向上语法分析方法基本思想；2.掌握算符文法、算符优先文法定义和性质教学重点：

1.优先分析法基本思想和术语；2.算符文法、算符优先文法定义和性质教学难点：

算符优先关系定义教学课时：2教学方法：多媒体教学教学内容和步骤：（以下）第十二讲3自底向上分析方法，也称移进归约分析法实现思想（是推导逆过程）：对输入符号串自左向右进行扫描，并将输入符逐一移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型句柄时，就用该产生式左部非终止符代替对应右部文法符号串，称为归约。重复这一过程，直到归约到栈中只剩下文法开始符号时，则分析成功。自底向上分析方法基本思想4例1：文法:SaAcBeAbAAbBd输入串abbcde#分析最右推导：SaAcBeaAcdeaAbcdeabbcde规约分析过程以下：5步骤符号栈输入符号串动作1#abbcde#移进2#abbcde#移进3#abbcde#归约A→b4#aAbcde#移进5#aAbcde#归约A→Ab6#aAcde#移进7#aAcde#移进8#aAcde#归约B→b9#aAcBe#移进10#aAcBe#规约S→aAcBe11#S#接收6上述每一步规约能够结构一颗语法树：AbBdAAbbSAbbaceBdA7问题提出：①在结构语法树过程中，何时规约？当句柄出现在栈顶符号串中就能够规约。②怎样知道在栈顶符号串中已经形成句柄？经过自底向上分析算法来解释（优先关系）8优先分析法又可分简单优先分析法和算符优先分析法。①简单优先分析法（规范归约）－对文法按一定标准求出全部文法符号间优先关系；②算法优先分析法（不规范归约）－要求算符之间优先关系）6.1自底向上优先分析法概述96.3算符优先分析法算符优先优先分析法 只要求算符（终止符）之间优先关系。在归约过程中只要找到句柄就归约，无须考虑归约到哪个非终止符，所以不是规范归约。 特点：速度快，尤其适合于表示式分析经过算符之间优先关系来确定句柄10先看一个例题：例.已知文法G[E]：E→E+EE→E*E

E→i输入串i+i*i，归约过程以下11步骤符号栈输入符号串优先关系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*i#*<i移进8）#E+E*i#*<i>#规约9）#E+E*E#+<*>#规约10）#E+E##<+>#规约11）#E#接收动作12分析可知：若只从移进—归约角度来考虑，在第6步时栈顶已出现了句柄E+E，能够进行归约了，不过显著是错误，因为这么就不符合算术运算规律。所以对于表示式，我们能够人为地要求其算符优先次序，即给出优先级别和同一级别结合性。13算符文法定义：设有一文法G，假如G中没有形如A→…BC…产生式，其中B和C为非终止符，则称G为算符文法(或称OG文法)。即任何一个产生式中都不包含两个非终止符相邻情况，就是算符文法。14性质1：在算符文法中任何句型都不包含两个相邻非终止符。性质2：假如Ab或（bA）出现在算符文法句型中，其中AVN，bVT，则中任何含b短语必含有A。（含b短语必含A，含A短语不一定含b）15算符优先关系定义：设G是一个算符文法，a和b是任意两个终止符，A，B，C是非终止符，算符优先关系以下：(1)a=b当且仅当G中含有形如A→…ab…或A→…aBb…产生式;(2)a<b当且仅当G中含有形如A→…aB…产生式，且Bb…或BCb…；(3)a>b当且仅当G中含有形如A→…Bb…产生式，且B…a或B…aC。＋＋＋＋16算符优先文法定义：设有一不含产生式算符文法G，假如对任意两个终止符a，b之间至多只有=，<和>三种关系一个成立，则称G是一个算符优先文法(也称OPG文法)。即a

b，a

b，ab只有一个成立，但允许ab，b

a同时存在。17例：已知表示式文法G[E]：E→E+E|E*E|(E)|i证实G[E]不是OPG文法。证实以下：因为：E→E+E，EE*E则有+<*又因为：E→E*E,EE+E则有+>*所以不是算符优先文法。＋＋18自底向上分析方法，也称移进归约分析法，是推导逆过程。算法优先分析法（不规范归约）－要求算符之间优先关系）文法符号之间优先关系有三种：大于、小于和等于。算符优先文法(也称OPG文法)，它是一个算符文法，不含产生式，且对任意两个终止符a，b之间至多只有=，<和>三种关系一个成立。教学总结19教材P122练习:2(1)，3(1)作业20课题：算符优先关系表和算符优先分析法目标要求：1.掌握算符优先关系表结构方法；3.掌握算符优先分析法及其不足教学重点：

1.符优先关系表结构2.算符优先分析法实现；教学难点：

算符优先关系表结构教学课时：2教学方法：多媒体教学教学内容和步骤：（以下）第十三讲21三、算符优先关系表用表格形式来表示各终止符号优先关系，这种表称为优先关系表。结构优先关系表方法：①按照定义来结构②按关系图来结构首先引入两个概念： firstVT集合lastVT集合 first(B)={b|Bb…或BCb…} lastVT(B)={a|B…a或B…aC}++++221)=关系直接看产生式右部，若出现了

A→…ab…或A→…aBb，则a=b2)<关系求出每个非终止符BFIRSTVT(B)若A→…aB…，则b∈FIRSTVT(B)，a<b3)>关系求出每个非终止符BLASTVT(B)若A→…Bb…，则a∈LASTVT(B)，a>b三种算符优先关系计算：23例：已知文法以下，计算优先关系E’→#E#E→E+TE→TT→T*FT→FF→P↑FF→PP→（E）P→i24解:(1)先求firstVT和lastVT集first(E’)={#}first(E)={+,*,↑,(,i}first(T)={*,↑,(,i}first(F)={↑,(,i}first(P)={(,i}lastVT(E’)={#}lastVT(E)={+,*,↑,),i}lastVT(T)={*,↑,),i}lastVT(F)={),↑,i}lastVT(P)={i,)}25(2)求=关系E’→#E##=#P→(E)(=)(3)求<

关系E’→#E#则#<first(E)所以#<+,#<*,#<↑,#<(，#<i26E’→E+T则+<first(T)所以+<*,+<↑,+<(,+<iT→T*F则*<first(F)所以*<↑,*<(,*<iF→P↑F则↑<first(F)所以↑<↑,↑<(,↑<iP→（E)则（<first(E)所以(<+,(<*,(<↑,(<(,(<i27(4)求>关系E’→#E#则lastVT(E)>#所以+>#,*>#，↑>#,)>#,i>#E→E+T则lastVT(E)>+所以+>+,*>+,↑>+,)>+,i>+T→T*F则lastVT(T)>*所以*>*,↑>*,i>*,)>*F→P↑F则lastVT(P)>↑所以i>↑,)>↑P→(E)则lastVT(E)>)

所以+>),*>),↑>),i>),)>)28算符优先关系表+*↑i()#+><<<<>>*>><<<>>↑>><<<>>i>>>>>(<<<<<=

)>>>>>#<<<<<=

29算符优先分析算法：归约过程中，只考虑终止符之间优先关系来确定句柄，而与非终止符无关。这么去掉了单非终止符归约，所以用算符优先分析法规约过程与规范归约是不一样.为处理在算符优先分析过程中怎样寻找句柄，引进最左素短语概念30算符文法任一句型有以下形式：

#N1a1N2a2......NnanNn+1#,若Niai......NjajNj+1为句柄，则有

ai-1<ai=ai=...=aj-1=aj>ai+1对于算符优先文法，若句型r中含有aNb(或ab)若a<b，则在r中必有含b而不含a短语存在若a>b，则在r中必有含a而不含b短语存在若a=b，则在r中含有a短语必含有b，反之亦然31最左素短语：定义：设有文法G[S]，其中句型