编译原理第五章语法分析-自下而上分析

《编译原理第五章语法分析-自下而上分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章语法分析-自下而上分析5.1自下而上分析基本问题5.2算符优先分析5.3LR分析法5.4语法分析器的自动产生工具YACC5.1自下而上分析基本问题5.1.1归约5.1.2规范归约简述5.1.3符号栈的使用与语法树的表示5.1.1归约“移进-归约”法：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。例子：假定文法GS→aAcBeA→bA→AbB→d输入串abbcde归约到S过程。步骤12345

2、678910动作进进归进归进进归进归ab(2)b(3)cd(4)e(1)edBBbccccbAAAAAAAaaaaaaaaaS图5.1规约中符号栈的变迁SaAbcBdeAb问题：如果步骤5用规则(2)，而不是用规则(3)则会有不同的结果。这就是“可规约串”问题。对可规约串的刻画不同，分析的方法也不同，本课程讨论“最左素短语”和“句柄”两种可规约串刻画方法。5.1.2规范归约简述短语、直接短语和句柄定义：令G是一个文法，S是文法的开始符号，假定是文法的一个句型，如果有S⇒*A且A⇒+则

3、称是句型相对于非终结符A的短语。特别是，如果有A⇒则称是句型相对于规则A→的直接短语一个句型的最左直接短语称为该句型的句柄。利用句柄规约的例子：句型归约规则abbcde(2)A→baAbcde(3)A→AbaAcde(4)B→daAcBe(1)S→aAcBeS规范规约的一般定义：假设是文法G的一个句子，我们称序列n,n-1,…,0是的一个规范规约，如果此序列满足：(1)n=(2)0=S(3)对任意的i,i-1是从i经句柄替换的结果。规范推导：最右推导常被称为规

4、范推导规范句型：最右推导的句型称为规范句型规范归约：规范推导的逆过程（最左规约）称为规范归约SaAbcBdeAbSaAbcBdeASaAcBde(a)(b)(c)图5.2句柄规约的消减树5.1.3符号栈的使用与语法树的表示规范规约的数据结构和动作：采用栈作为语法分析的基本数据结构。符号栈输入串#w#……#S#语法分析对符号栈的使用有四类操作：“移进”、“归约”、“接受”和“出错处理”。任何可规约串的出现必须在栈顶。例5.3：输入串i1*i2+i3的分析步骤：步骤符号栈输入串所用产生式0#i1*i2

5、+i3#预备1#i1*i2+i3#进2#F*i2+i3#归，用F→i3#T*i2+i3#归，用T→F4#T*i2+i3#进5#T*i2+i3#进…………………………………13#E#归，用E→E+T14#E#接受5.2算符优先分析5.2.1算符优先文法及优先表构造5.2.2算符优先分析算法5.2.3优先函数5.2.4算符优先分析中的出错处理算符优先分析法的主要思想：是自下而上的归约过程，但这种归约未必是严格的最左归约。而是借助于两个终结符之间的优先关系来寻找“可归约串”进行归约。算符优先关系定义：(

6、1)a⋖b:a的优先性低于b。当且仅当G中含有形如P→…aR…的产生式，而R⇒b…或R⇒Qb…；但并不意味b高于a。(2)a≖b:a的优先性等于b。当且仅当G中含有形如P→…ab…的产生式或P→…aQb…的产生式；但并不意味b等于a。(3)a⋗b：a的优先性高于b。当且仅当G中含有形如P→…Rb…的产生式，而R⇒…a或R⇒…aQ。a的优先性高于b。5.2.1算符优先文法及优先表构造算符文法定义：一个文法，如果它的任一产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：…QR…

7、算符优先文法定义：如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三关系之一：a≖b，a⋖b，a⋗b例5.4构造下面算法优先文法的优先表(1)E→E+T

8、T(2)T→T*F

9、F(5.3)(3)F→P↑F

10、P(4)P→(E)

11、i解：由(4)可得‘(’≖‘)’；由(2)(3)可得*⋖↑…最后可得表5.1所示优先表。算符优先文法G构造优先关系表的算法FIRSTVT(P)和LASTVT(P)定义：FIRSTVT(P)={a

12、P⇒+a…或P⇒+Qa…,aVT而QVN}LASTVT(P)={a

13、

14、P⇒+…a或P⇒+…aQ,aVT而QVN}FIRSTVT(P)构造：若有产生式P→a…或P→Qa…，则a∈FIRSTVT(P);若a∈FIRSTVT(Q)，且产生式P→Q…，则a∈FIRSTVT(P)。算法程序运算如下：PROCEDUREINSERT(P,a);IFNOTF[P,a]THENBEGINF[P,a]:=TRUE;把(P,a)下推进STACK栈END;主程序：BEGINFOR每个非终结符P和终结符aDOF[P,a]:=FALSE;FOR每个形如P→a…或P→Qa…的