编泽原理 第五章语法分析 自下而上分析 刘小豫 信息工程学院 Email:.shz灯y@126.com
编译原理 第五章 语法分析 ——自下而上分析 刘小豫 信息工程学院 Email：shzlxy@126.com
编泽原理 培法分折一自下而上分析 本章内容概要 马自下而上分析基本问题 @归约 @规范归约 算符优先分析 @算符优先文法 @算符优先分析表的构造 LR分析法 OLR分析器 OLR文法 ©LR(O)项目集族和LR(O)分析表的构造 第2列
编译原理 第2页 语法分析-自下而上分析 自下而上分析基本问题 归约 规范归约 算符优先分析 算符优先文法 算符优先分析表的构造 LR分析法 LR分析器 LR文法 LR(0)项目集族和LR(0)分析表的构造 本章内容概要
编译原理 培法分析一自下而上分析 语法分析的方法： @自下而上分析法(Bottom-up) ©自上而下分析法(Top-dowm) ◇基本思想：它从文法的开始符号出发，反复 使用各种产生式，寻找”匹配”的推导。 ◇递归下降分析法：对每一语法变量（非终结 符)构造一个相应的子程序，每个子程序识别 一定的语法单位，通过子程序间的信息反馈 和联合作用实现对输入串的识别。 令预测分析程序 优点：直观、简单和宜于手工实现。 第3觉
编译原理 第3页 语法分析-自下而上分析 语法分析的方法： 自下而上分析法(Bottom-up) 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反复 使用各种产生式，寻找"匹配"的推导。 递归下降分析法：对每一语法变量(非终结 符)构造一个相应的子程序，每个子程序识别 一定的语法单位，通过子程序间的信息反馈 和联合作用实现对输入串的识别。 预测分析程序 优点：直观、简单和宜于手工实现
编泽原理 培法分析-自下而上分析 5.1自下而上分析基本问题 5.1.1自下而上分析法(Bottom-up) ©基本思想：从输入串开始，逐步进行 “归约”，直到文法的开始符号。即从 树末端开始，构造语法树。 第苑
编译原理 第4页 语法分析-自下而上分析 5.1.1 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行 “归约”，直到文法的开始符号。即从 树末端开始，构造语法树。 5.1 自下而上分析基本问题
编泽原理 培法分析一自下而上分析 归约 @所谓归约，是指根据文法的产生式规则， 把产生式的右部替换成左部符号。 ©采用“移进一归约”思想进行自下而上分 析。 ©实现思想：用一个寄存符号的先进后出栈， 把输入符号一个一个地移进到栈里，当栈 顶形成某个产生式的候选式时，即把栈顶 的这一部分（可归约串）替换成（归约为） 该产生式的左部符号。 返回 第5页
编译原理 第5页 语法分析-自下而上分析 归约 所谓归约，是指根据文法的产生式规则， 把产生式的右部替换成左部符号。 采用“移进－归约”思想进行自下而上分 析。 实现思想：用一个寄存符号的先进后出栈， 把输入符号一个一个地移进到栈里，当栈 顶形成某个产生式的候选式时，即把栈顶 的这一部分（可归约串）替换成(归约为) 该产生式的左部符号。 返回
编泽原理 培法分折一自下而上分析 构造语法树 例：设文法G(S)如下，试对abbcde进行 移进一归约”分析。 (1)S→aAcBe (2)A→b (3)A→Ab (4)B→d a B d 第6页
编译原理 第6页 语法分析-自下而上分析 构造语法树 例：设文法G(S)如下，试对abbcde进行 “移进－归约”分析。 (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d b b d a c e S A B A
编译原理 培法分析一自下而上分析 在栈中实现“移进一归约” e B 专 e A 文法G(S): (1)S→aAcBe (2)A→b (3)A→Ab (4)B→d 第7觉
编译原理 第7页 语法分析-自下而上分析 在栈中实现“移进－归约” a bbcde b bcde A b cde c de d abbcdee e B c A Sa B c A a e 文法G(S): (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d
编泽原理 培法分折一自下而上分析 实现“移进一归约”，符号栈的变迁 步骤：123 45 67 8 9 10 动作：进a进b归(2)进b归(3)进c进d归(4)进e 归(1) e d B B b c c b A A A A A A A a a a a a a a a a 琶自下而上分析过程：边输入单词符号，边归约。 影8页
编译原理 第8页 语法分析-自下而上分析 步骤: 1 2 3 4 5 6 7 8 9 10 动作: 进a 进b 归(2) 进b 归(3) 进c 进d 归(4) 进e 归(1) e d B B b c c c c b A A A A A A A a a a a a a a a a S 自下而上分析过程：边输入单词符号，边归约。 实现“移进－归约”，符号栈的变迁
编译原理 培法分析一自下而上分析 移进归约分析中的问题 @1) 移进-归约冲突 令在分析到某一步时，既可以移进，又可以 归约 @2)归约-归约冲突 ◇存在两个可选的句柄，可对栈顶符号进行归约 @各种分析方法中处理冲突的技术不同 第9觉
编译原理 第9页 语法分析-自下而上分析 移进归约分析中的问题 1) 移进-归约冲突 在分析到某一步时，既可以移进，又可以 归约 2) 归约-归约冲突 存在两个可选的句柄，可对栈顶符号进行归约 各种分析方法中处理冲突的技术不同
编泽原理 培法分析-自下而上分析 ©关键问题：精确定义“可归约串”。 ©主要分析方法 ◇算符优先分析法：按照算符的优先关系和结合性 质进行语法分析。适合分析表达式。 令LR分析法：规范归约 @核心问题：识别可归约串。 第0
编译原理 第10页 语法分析-自下而上分析 主要分析方法 算符优先分析法：按照算符的优先关系和结合性 质进行语法分析。适合分析表达式。 LR分析法：规范归约 关键问题：精确定义“可归约串”。 核心问题：识别可归约串
