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

第五章 语法分析-自下而上分析 5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析法 5.4 语法分析器的自动产生工具YACC 5.1 自下而上分析基本问题 5.1.1 归约 5.1.2 规范归约简述 5.1.3 符号栈的使用与语法树的表示 5.1.1 归约 “移进-归约”法： 用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。 例子：假定文法G S→aAcBe A→b A→Ab B→d 输入串abbcde归约到S过程。 5.1.2 规范归约简述 短语、直接短语和句柄定义： 令G是一个文法，S是文法的开始符号，假定???是文法的一个句型，如果有 S?* ?A? 且A?+? 则?称是句型???相对于非终结符A的短语。特别是，如果有 A?? 则称?是句型???相对于规则A→ ?的直接短语 一个句型的最左直接短语称为该句型的句柄。 利用句柄规约的例子： 句型 归约规则 abbcde (2)A→b aAbcde (3)A→Ab aAcde (4)B→d aAcBe (1)S→aAcBe S 规范规约的一般定义： 假设?是文法G的一个句子，我们称序列 ?n, ?n-1,…,?0 是?的一个规范规约，如果此序列满足： (1) ?n=? (2) ?0=S (3)对任意的i,?i-1是从?i经句柄替换的结果。 规范推导： 最右推导常被称为规范推导 规范句型： 最右推导的句型称为规范句型 规范归约： 规范推导的逆过程（最左规约）称为规范归约 5.1.3 符号栈的使用与语法树的表示 规范规约的数据结构和动作： 采用栈作为语法分析的基本数据结构。 符号栈 输入串 # w# … … #S # 语法分析对符号栈的使用有四类操作：“移进”、“归约”、“接受”和“出错处理”。 任何可规约串的出现必须在栈顶。 例5.3：输入串i1*i2+i3的分析步骤： 步骤 符号栈 输入串 所用产生式 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用F→i 3 #T *i2+i3# 归，用T→F 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 ………………………………… 13 #E # 归，用E→E+T 14 #E # 接受 5.2 算符优先分析 5.2.1 算符优先文法及优先表构造 5.2.2 算符优先分析算法 5.2.3 优先函数 5.2.4 算符优先分析中的出错处理 算符优先分析法的主要思想： 是自下而上的归约过程，但这种归约未必是严格的最左归约。而是借助于两个终结符之间的优先关系来寻找“可归约串”进行归约。 算符优先关系定义： (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… 算符优先文法定义： 如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三关系之一： a?b，a?b ，a?b 例5.4 构造下面算法优先文法的优先表 (1)E→E+T|T (2)T→T*F|F (5.3) (3)F→P↑F|P (4)P→(E)|i 解： 由(4)可得‘(’?‘)’；由(2)(