编译原理第七章LR分析法.docVIP

第七章 LR分析法 课前索引 【课前思考】　　◇ 复习自顶向下和自底向上语法分析思想的区别　　◇ 自底向上分析方法是一种移进-归约过程　　◇ 算符优先分析法是如何确定可归约串的？　　◇ 什么是规范推导和规范归约？它们之间有什么关系？　　◇ 什么是规范句型？　　◇ 什么是规范句型的句柄？　　◇ 移进-归约过程是当分析的栈顶符号串形成句柄时就采取归约动作　　◇ 自底向上分析法的关键问题是在分析过程中如何确定句柄。　　◇ 如何确定一个输入符号串是否是所给文法的句子？【学习目标】　　本章将介绍自底向上分析的另一种方法，即LR分析法。 　　◇ 理解LR分析法的基本思想　　◇ 理解可归前缀和子前缀概念　　◇ 理解识别活前缀的有限自动机概念　　◇ 掌握LR分析器的构造思想和方法　　◇ 对给定的文法能构造LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器，并能判断所给文法是四种分析器的哪几类。　　◇ 对给定的输入符号串能用构造的分析器判断该输入串是否是所给文法的句子　　◇ 了解某些二义性文法在LR分析中的应用。 【学习指南】　　LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K≥0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。其中LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，然而，它是构造其它LR类分析器的基础。因此，首先应学好LR(0)项目集规范族构造的基本原理和方法。当K=1时，已能满足当前绝大多数高级语言编译程序实现的需要。SLR(1)分析是为学习LR(1)分析做准备，LR(1)项目集族的构造是LALR(1)分析器的构造原理和基础。LALR(1) 分析器是当前大多数高级程序设计语言编译程序所采用的语法分析技术，也是编译程序语法分析器自动构造工具YACC(将在第13章介绍）的实现基本原理。由此，LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器的构造方法都必须深入理解和掌握。【难 重 点】　　◇ 可归前缀和子前缀概念　　◇ 识别活前缀的有限自动机概念　　◇ 对可归前缀为规范归约的句柄的理解　　◇ 构造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分析中的应用【知识结构】 在第6章中已经讨论过，自底向上分析方法是一种移进-归约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K≥0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。 LR(K)分析方法是1965年Knuth提出的，括号中的K表示向右查看输入串符号的个数。这种方法比起自顶向下的LL(K)分析方法和算符优先分析方法对文法的限制要少得多，也就是说对于大多数用无二义性上下文无关文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、即时地指出出错位置。它的主要缺点是对于一个实用语言文法的分析器的构造工作量相当大，K愈大构造愈复杂，实现相当困难。目前对于真正实用的编译程序，所采用的LR分析器都是借助于美国Bell实验室1974年推出的一个编译器的编译器-YACC来实现的。它能接受一个用BNF描述的满足LALR(1)的上下文无关文法并将自动构造LALR(1)语法分析器。　　本章将主要介绍LR分析的基本思想和当K≤1时LR分析器的基本构造原理和方法。其中LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，对绝大多数高级语言的语法分析器是不能适用的，然而，它是构造其它LR类分析器的基础。当K=1时，已能满足当前绝大多数高级语言编译程序的需要。因此，我们将着重介绍LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器的构造方法。其中SLR(1)和LALR(1)分别是LR(0)和