1、第六 七章自下而上语法分析法1【 课前思考 】 自顶向下和自底向上语法分析思想的区别 自底向上分析方法是一种移进 -归约过程 算符优先分析法是如何确定可归约串的？ 什么是规范推导和规范归约？它们之间有什么关系？ 什么是规范句型？ 什么是规范句型的句柄？ 移进 -归约过程是当分析的栈顶符号串形成句柄时就采取归约动作 自底向上分析法的关键问题是在分析过程中如何确定句柄。 如何确定一个输入符号串是否是所给文法的句子？2【 学习目标 】本章将主要介绍自底向上分析的一种方法，即LR分析法。 理解 LR分析法的基本思想 理解可归前缀和子前缀概念 理解识别活前缀的有限自动机概念 掌握 LR分析器的构造思想和
2、方法 对给定的文法能构造 LR(0)、 SLR(1)、LALR(1)、 LR(1)四种分析器，并能判断所给文法是四种分析器的哪几类。 对给定的输入符号串能用构造的分析器判断该输入串是否是所给文法的句子 了解某些二义性文法在 LR分析中的应用。 3【 学习指南 】LR分析法的归约过程是规范推导的逆过程，所以 LR分析过程是一种规范归约过程。 LR分析法正是给出一种能根据当前分析栈中的符号串 (通常以状态表示 )和向右顺序查看输入串的 K个 (K0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。其中 LR(0)分析器是在分析过程中不需向右查看输入符号，因
3、而它对文法的限制较大，然而，它是构造其它 LR类分析器的基础。因此，首先应学好 LR(0)项目集规范族构造的基本原理和方法。当 K=1时，已能满足当前绝大多数高级语言编译程序实现的需要。4SLR(1)分析是为学习 LR(1)分析做准备， LR(1)项目集族的构造是 LALR(1)分析器的构造原理和基础。LALR(1) 分析器是当前大多数高级程序设计语言编译程序所采用的语法分析技术，也是编译程序语法分析器自动构造工具 YACC(将在第 13章介绍）的实现基本原理。由此， LR(0)、 SLR(1)、 LALR(1)、LR(1)四种分析器的构造方法都必须深入理解和掌握。5【 难 重 点 】 可归前
4、缀和子前缀概念 识别活前缀的有限自动机概念 对可归前缀为规范归约的句柄的理解 构造 LR(1)项目集族时搜索符的计算 LR分析器的关键部分是分析表的构造 对给定的文法能构造 LR(0)、 SLR(1)、LALR(1)、 LR(1)四种分析器 当一个文法能构造出不含移进 -归约或归约 -归约冲突时的 LR(0)/ SLR(1)/ LALR(1)/ LR(1)分析表时，称这个文法为 LR(0) / SLR(1)/ LALR(1)/ LR(1)文法。 对给定的文法能判断是四种 LR类文法的哪几类 了解某些二义性文法在 LR分析中的应用【 知识结构 】 67一、 自底向上分析概述 自底向上分析法，也称
5、移进 -归约分析法，或自下而上分析。自底向上分析是自顶向下推导的逆过程 ,它是从待分析的句子出发逆向使用产生式逐步归约的过程。从语法分析树的角度讲，就是从语法树的叶结点（句子）出发自下而上逐层构造语法树，每一层对应归约过程中的一个句型。自底向上分析法的关键问题是：在分析过程中如何确定句型中的可归约子串。现举例说明。 例 6.1 设文法 GS为：(1) SaAcBe (2) Ab(3) AAb (4) Bd8对输入串 abbcde#进行分析，检查该符号串是否是 GS的句子。由于自底向上分析的移进 -归约过程是自顶向下最右推导的逆过程，而最右推导为规范推导，自左向右的归约过程也称规范归约。容易看出对输入串 abbcde的最右推导是：S aAcBe aAcde aAbcde abbcde由此我们可以构造它的逆过程即归约过程。先设一个先进后出的符号栈，并把句子左括号“#”号放入栈底，其分析过程如表 6.1。下表 6.1 用移进 -归约对输入串 abbcde#的分析过程9(1) SaAcBe (2) Ab(3) AAb (4) Bd10
