第六章 自底向上优先分析(编译原理)
- 格式:ppt
- 大小:402.00 KB
- 文档页数:30
第6章⾃底向上优先分析法⾃底向上分析⽅法,也称移进-归约分析法,粗略地说它的实现思想是对输⼊符号串⾃左向右进⾏扫描,并将输⼊符逐个移⼊⼀个后进先出栈中,边移⼊边分析,⼀旦栈顶符号串形成某个句型的句柄时,(该句柄对应某产⽣式的右部),就⽤该产⽣式的左部⾮终结符代替相应右部的⽂法符号串,这称为归约。
重复这⼀过程直到归约到栈顶中只剩⽂法的开始符号时则为分析成功,也就确认输⼊串是⽂法的句⼦。
本章将在介绍⾃底向上分析思想基础上,着重介绍算符优先分析法。
例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由此我们可以构造它的逆过程即归约过程。
先设⼀个后进先出的符号栈,并把句⼦左括号”#”号放⼊栈底。
对上述分析过程也可看成⾃底向上构造语法树的过程,每步归约都是构造⼀棵⼦树,最后当输⼊串结束时刚好构造出整个语法树。
在上述移进-归约或⾃底向上构造语法树的过程中,考虑⼏个问题:u 何时移进?u 何时归约?u 将哪个字符串归约?当⼀个⽂法⽆⼆义性时,那么它对⼀个句⼦的规范推导是唯⼀的,规范规约也必然是唯⼀的。
因⽽每次归约时要找当前句型的句柄,也就是说,任何时候栈中的符号串和剩余的输⼊串组成⼀个句型,当句柄出现在栈顶符号串中时,则可⽤句柄归约,这样⼀直归约到输⼊串只剩结束符,⽂法符号栈中只剩开始符号。
由此可见,⾃底向上分析的关键问题是在分析过程中如何确定句柄,即如何知道何时在栈顶符号串中已形成某句型的句柄。
然⽽⾃底向上的分析算法很多,我们仅在本章和第7章介绍⽬前常⽤的算符优先分析和LR类分析法。
6.1 ⾃底向上优先分析法概述优先分析法⼜可分简单优先法和算符优先分析法。
编译原理武汉大学计算机学院编译原理课程组自上而下语法分析·基本思想·存在的问题·解决方法·LL(1)方法·递归子程序法消除左递归FIRST集、FOLLOW集·LL(1)文法递归子程序的构造LL(1)分析表的构造6.1 自下而上语法分析1.自下而上语法分析的基本思想从输入的符号串开始,利用文法的产生式步步向上归约,试图归约到文法的识别符号。
如果从语法树的角度看,自下而上分析的过程是以输入符号串作为末端结点符号串,向着根结点的方向往上构造语法树,使识别符号正好是该语法树的根结点。
相应于高级语言的编译过程,自下而上语法分析就是从该高级语言文法的源程序或与其等价的单词串出发,试图归约得到该文法的开始符号——<程序>。
6.1 自下而上语法分析3.自下而上语法分析遇到的基本问题例如,对文法G[S]:S→aAcBeA→bA→AbB→d分析符号串abbcde。
1.短语、直接短语与句柄6.2 短语和句柄则称句型xuy 中的子串u 为句型xuy (相对于非终结符号U )的短语。
设有文法G[Z],w=xuy 是它的一个句型,如果有Z *⇒xUy +⇒且U u U ⇒u则称u为句型xuy的直接(简单)短语。
特别地,如果前述条件中U +⇒u为句型的最左直接(简单)短语称为句柄。
6.2 短语和句柄例:设有文法G[S]:S→ABA→Aa|bBB→a|Sb请给出句型baabaab的所有短语、直接短语和句柄。
6.2 短语和句柄2.短语、简单(直接)短语、句柄与语法树的关系语法树子树的末端结点符号串即是语法树所描述句型(相对于子树的根)的短语;简单子树(只有父子两代)的末端结点符号串即是直接短语。
最左简单子树的末端结点符号串即是句柄。
6.2 短语和句柄例:设有文法G[S]:S→ABA→Aa|bBB→a|Sb请给出句型baabaab的所有短语、直接短语和句柄。
第 6 章自学内容第 6 章作业P100 6.8求下列句型的所有短语、简单(直接)短语和句柄。
第6章自底向上优先分析第1题已知文法G[S]为:S T a|A |(T)T,S|S(1)计算 G[S]的 FIRSTVT 和 LASTVT。
(2)构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。
⑶计算G[S]的优先函数。
(4)给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。
答案:文法展开为:S^aS T AS T (T)T T T,ST T S猱符优先关系表:友情提示:记得增加拓广文法S' T#S#,所以# FIRSTVT(S) , LASTVT(S) # 。
Success!对输入串(a,(a,a) ) #的算符优先分析过程为:栈〔STACK) 为询字符WH恋)剩余输入笊(INPUT_STRING)动作〔ACTION)岸n a.(a.a))# e ill * a 伽)># itove iiima{aa)> Reduce: S—q <a.a)># Move iii( a.a))# Move iiia 讪Move iiia))# Reduce: S—日#(N,(N i a))# \tove iii#(N.(N a Move m粼屈)Reduce: S—R粼N(N.N)Reduce; T—丁占)h【ovE iii)#Reduce: S—*(T) #(N,N )#Reduce: T—*T,S #(N )Move iiiKN) ##Reduce: S—"(T) Success!第2题已知文法G[S]为:S T a|A |(T)T,S|S(1)给出(a,(a,a))和(a,a)的最右推导,和规范归约过程。
⑵ 将⑴和题1中的⑷进行比较给出算符优先归约和规范归约的区另叽答案:(1 ) (n・a)的授右推导过程为: sn(T) =(T.S)=^(T.a)=>(S.a)=>(a.a)(a.(a.a))的最右推导过程为:S=>(T)O(T.S)=(T.(T))=>(r.(r.s))=>(T.(T.a))=>(T.(S.a))=>(T-(a.a))=>(S.(a.a))=>(a.(a.a))(a.(a.a))的规范归约过程:(冇)的规范!H约过阻(2)非终结符无关,只需知道把当前可归约串归约为某一个非终结符,不必知道该非终结符的名字是什么,因此去掉了单非终结符的归约。