天津大学编译原理讲义-Part5自底向上的语法分析ppt课件.ppt

《天津大学编译原理讲义-Part5自底向上的语法分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Part5语法分析授课：胡静自底向上的语法分析概述目录自底向上语法分析是一个更加强大的分析技术。LR文法——比LL描述能力更强构造程序的最右推导几乎所有的程序设计语言都是左递归的更加容易描述程序设计语言的语法。移进-归约分析LR文法的语法分析器语法生成器的自动生成器(e.g.,yacc)自顶向下vs自底向上自底向上：只需要对当前的输入给出足够的语法树的部分就行自底向上的语法分析较常用的自底向上语法分析法移动－归约分析法用栈实现移动归约分析最易于实现的移动归约分析法算符优先分析法算符优先分析法定义、优先分析表的确定、优先函数的定义使用算符优先关系进行分析算符优

2、先分析中的错误恢复最一般的移动归约分析方法LR分析法自底向上语法分析概述自底向上的语法分析方法，也称为移动归约分析法。最易于实现的一种移动归约分析方法，叫做算符优先分析法，而更一般的移动归约分析方法叫做LR分析法，LR分析法可以用作许多自动的语法分析器的生成器。移动归约分析法为输入串构造分析数时是从叶结点（底端）开始，向根结点（顶端）前进。我们可以把该过程看成是把输入串ω“归约”成文法开始符号的过程。在每一步归约中，如果一个子串和某个产生式的右部匹配，则用该产生式的左部符号代替该子串。如果每一步都能恰当的选择子串，我们就可以得到最右推导的逆过程。移进-归约分

3、析分析就是移进和归约动作的序列移进：将当前扫描的token移动到堆栈中。归约：将栈顶的符号串β移除，用非终结符X代替，这对应着产生式A→β(popβ,pushA)短语、直接短语、句柄的定义：文法G[S]，αβδ是文法G的一个句型，S=>*αAδ且A=>+β则称β是句型αβδ相对于非终结符A的短语。若有Aβ则称β是句型αβδ相对于该规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。用子树解释短语，直接短语，句柄:短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成

4、的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。EE+TE+T*FE+T*a3E+F*a3E+a2*a3T+a2*a3F+a2*a3E+TT*F,E+T*Fa3,T*a3,E+T*a3a3,F,F*a3,E+F*a3a3,a2,a2*a3,E+a2*a3a3,a2,T,a2*a3,T+a2*a3a3,a2,F,a2*a3,F+a2*a3a1,a2,a3,a2*a3a1+a2*a3EE+TTFa1T*FFa2

5、a3a1+a2*a3短语移动归约分析法相关概念规范归约文法的最右推导为规范推导，自底向上分析是自顶向下最右推导的逆过程，叫规范归约句柄直观来看：一个符号串的“句柄”是和一个产生式右部匹配的子串，而且把它归约到该产生式左部的非终结符代表了最右推导逆过程的一步。形式定义：右句型（最右推导可得到的句型）γ的句柄是一个产生式A→β以及γ的一个位置，在该位置可以找到串β，而且用A代替β可以得到γ的最右推导的前一个右句型对于有二义性的文法而言，由于最右推导不一定，则句柄不一定唯一。只有当文法没有二义性时，每个右句型才只有一个句柄。句柄剪裁通过“剪裁句柄”可以得到最右推

6、导的逆过程在归约过程中用到的产生式序列的逆序就是输入串的最右推导(1)SaABe(2)Ab(3)AAbc(4)BdS＝>aABe＝>aAde＝>aAbcde＝>abbcde步骤符号栈输入符号串动作1$abbcde$移动2$abbcde$移动3$abbcde$归约(2)4$aAbcde$移动5$aAbcde$移动6$aAbcde$归约（3）7$aAde$移动8$aAde$归约(4)9$aABe$移进10$aABe$归约(1)11$S$接受移动归约分析中需要解决的问题定位右句型中将要归约的子串（可归约串）在用堆栈实现时，这个子串总是在栈顶。语法分析器不需

7、要深入到栈中去寻找句柄选择产生式对选定的串进行归约如果选定的子串是多个产生式的右部，要确定选择哪个产生式进行归约移动归约分析过程中的冲突根据栈中的内容和下一个输入符号不能决定是移动还是归约（移动-归约冲突）不能决定按哪一个产生式进行归约（归约-归约冲突）算符优先分析法算符优先分析法算符文法的定义：所有产生式的右部都不是ε或两个相邻的非终结符设有一个文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法(OperatorGrammar)也称OG文法.算符优先文法的特点：一旦我们构造了算符优先语法分析器，就可以忽略原来的文法，栈中的

8、非终结符仅仅作为与这些非终结符相关的属性的占位符难以