语法分析——自底向上

《语法分析——自底向上》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、语法分析概述短语、直接短语及句柄算符优先分析LR分析LR分析的错误处理与恢复语法分析程序自动生成器第五章语法分析——自底向上2基本思想：从输入串开始逐步归约基本问题：归约的问题优先分析法优先文法、算符优先文法优先算符优先函数的构造分析方法基础知识LR(0)项目及项目集LR(1)项目及项目集规范句型活前缀LR分析法LR分析器分析栈、分析表分析方法LR分析表的构造实现技术——移进归约自下而上语法分析§5.1自下而上的语法分析CompilerPrinciples3自下而上分析基本思想从给定的输入串$开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替(归约)之，逐

2、步归约到SCompilerPrinciples41.归约与语法分析树例文法G[S]:(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dW=abbcde，构造其语法分析树：abbcdeAABS52.移进－归约输入串：abbcde#动作：符号栈：步骤：12345678910移进a移进b归约b移进b归约Ab移进c移进d归约d归约aAcBe移进e归约产生式：#a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S(2)(3)(4)(1)例文法G[S]:(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d§5.1自下而上的语法分析CompilerPrinci

3、ples6自下而上分析的关键：(1)确定可归约串(2)如何归约——归约条件——归约原则5.1.2规范规约与句柄定义：定义5.1短语：令G是一个文法，S是开始符号，αβδ是文法G的一个句型，如果有S*αAδ且A+β，则称β是句型αβδ相对于非终结符A的短语。特别的，如果有Aβ，则称β是句型αβδ相对于规则A→β的直接短语（简单短语）定义5.2句柄：一个句型的最左直接短语称为该句型的句柄。CompilerPrinciples75.1.2规范规约与句柄注意：直接短语一定是短语；句柄一定是直接短语且具有最左性；句子的句柄是语法树中最左子树的所有叶节点从左到右的排列或在句子的规范推导

4、序列中，最后使用的产生式的右部；CompilerPrinciples8思考：用什么方法找出所有短语、直接短语和句柄？例：设有文法G和输入串$G:S→aAcBA→PP→abB→d$:aabcd对$存在推导S=>aAcB=>aPcB=>aabcB=>aabcdCompilerPrinciples9则P是句型aPcB相对于A的短语，也是相对于A的直接短语，也是句型aPcB的句柄。ab是句型aabcB相对于A的短语；相对于P的直接短语和最左直接短语即是句型aabcB的句柄。d是句子aabcd相对于B的短语；相对于B的直接短语；例例：文法G[E]:E→E+T∣TT→T*F

5、FF→(E)

6、i

7、求句型T+T+i的短语、简单短语和句柄短语：T+T+i、T+T、T、i简单短语：T、i句柄：TCompilerPrinciples10EE+TE+TFTi规范归约假定α是文法G的一个句子，有序列αn,αn-1,…α0，如果此序列满足：ⅰ.αn＝α;ⅱ.α0＝S;ⅲ.对任何i,0

8、bcdeRRRRCompilerPrinciples12abbcdeAABS规范归约（1）（1）（2）（2）（3）（3）（4）（4）13基本思想：从输入串开始逐步归约基本问题：归约的问题优先分析法优先文法、算符优先文法优先算符优先函数的构造分析方法基础知识LR(0)项目及项目集LR(1)项目及项目集规范句型活前缀LR分析法LR分析器分析栈、分析表分析方法LR分析表的构造二义性文法的分析实现技术——移进归约自下而上语法分析5.2.1直观的优先分析方法基本思想对给定的G按照一定原则求出G的文法符号间的优先关系，按照优先关系寻找句柄实施归约。CompilerPrinciples14a⋖

9、b表示的a优先关系低于ba⋗b表示的a优先关系高于ba≐b表示的a优先关系同等于b优先关系确定优先关系的规则（1）X≐Y当且仅当G中存在产生式A…XY…——（在语法树的同一层）（2）X⋖Y当且仅当G中存在产生式A…XB…，且BY…——（Y在X的下一层）（3）X⋗Y当且仅当G中存在产生式A…BD…，且B…X和DY…——（X在Y的下一层或X比Y先归约——规范归约/最左归约）++*例：有文法G(S):S→bAbA→(B

10、aB→Aa)解：文法符号优先关系推导如下：(1)求≐关