第四章语法分析.docxVIP

第四章语法分析

本章介绍的语法分析方法通常被用于编译器中。我们首先给出基本概念，然后给出适用于手工实现的技术，最后是已经被用于自动化工具的算法。因为源程序可能包含语法错误，我们讨论了如何扩展语法分析方法，使之可以从常见错误中恢复。

在语言设计时，每个程序设计语言都有一组精确的规则来描述了良构(well-formed)程序的语法结构。比如，在C中一个程序由多个函数组成，一个函数由声明和语句组成，一个语句由表达式组成，等等。程序设计语言构造的语法可以使用2.2节中介绍的上下文无关文法或者BNF(-)表示法来描述。文法给语言和编译器作者都提供了很大的帮助。

●文法给出了一个程序设计语言的精确易懂的语法规约。

●对于某些类型的文法，我们可以自动地构造出高效的语法分析器，它能够得出一个源程序的语法构造。另一个附带的好处是，语法分析器的构造过程可以揭示出语法的二义性，同时还可能发现一些容易在语言的初始设计阶段被忽略的问题。

●一个正确设计的文法给出了一个语言的结构。该结构有助于把源程序翻译为正确的目标代码，也有助于错误检测。

●一个文法允许语言迭代地演化和开发，逐步加入可以完成新任务的新语言构造。如果对语言的实现遵循语言的文法结构，那么加入这些新构造的工作就变得相对容易。

在本节中，我们将考察语法分析器是按照什么方法被集成到一个典型的编译器中的。然后我们将研究算术表达式的典型文法。表达式文法已经足以演示语法分析的本质，因为处理表达式的语法分析技术可以被用于处理程序设计语言的大部分构造。这一节的最后讨论了错误处理的问题，因为当语法分析程序发现它的输入不能由它的文法生成时，它必须作出得体的反应。

1语法分析器的角色

在我们的编译器模型中，语法分析器从词法分析器获得一个由词法单元组成的串，并验证这个串可以由源语言的文法生成，如图4.1所示。我们期望语法分析器能够以易于理解的方式报告语法错误，并且能够从常见的错误中恢复并继续处理程序的其余部分。从概念上讲，对于良构的程序，语法分析器构造出一棵语法分析树，并把它传递给编译器的其余部分进一步处理。实际上并不需要显式地构造出这棵语法分析树，因为正如我们将看到的，对源程序的检查和翻译处理可以和语法分析过程交错完成。因此，语法分析器和前端的其它部分可以用一个模块来实现。

Sourceprogram源程序LexicalAnalyzer词法分析器token词法单元getnexttoken获取下一个词法单元Parser语法分析器parsetree语法分析树

RestofFrontEnd前端的其余部分intermediaterepresentation中间表示SymbolTable符号表

图4.1:语法分析器在编译器模型中的位置

处理文法的语法分析器大体上可以分为三种类型：通用的、自顶向下的、和自底向上的。象Cocke-Younger-Kasami算法和Earley算法这样的语法分析方法可以对任意文法进行语法分析(见参考文献)。然而，这些通用方法效率很低，不能用于编译器产品。

编译器中常用的方法可以分为自顶向下的和自底向上的。正如它们的名字所指出的，自顶向下的方法从语法分析树的顶部(根结点)开始向底部(叶子结点)构造树，而自底向上的方法从叶子结点开始，逐渐向顶部构造。这两种分析方法中，语法分析器的输入总是按照从左向右的方式被扫描，每次扫描一个符号。

最高效的自顶向下方法和自底向上方法只能处理某些文法子类，但其中的某些子类，特别是LL和LR文法，的表达能力已经足以描述现代程序设计语言的大部分语法构造了。手工实现的语法分析器通常使用LL文法；比如2.4.2节中的预测分析方法能够处理LL文法。处理较大的LR文法类的语法分析器常常是由自动化工具构造得到的。

在本章中，我们假设语法分析器的输出是语法分析树的某种表示形式。该语法分析树对应于来自词法分析器的词法单元流。在实践中，语法分析过程中可能完成多个任务，比如将不同词法单元的信息收集到符号表中，进行类型检查和其它类型的语义分析，以及生成中间代码。我们把所有这些活动都归到图4.1中的方框“前端的其余部分”里面。在后续几章中将详细讨论这些活动。

4.1.2代表性的文法

为了便于参考，我们在这里给出一些即将在本章中分析的文法。对那些以while或int这样的关键字开头的构造进行语法分析相对容易，因为这个关键字可以引导我们选择适当的文法产生式来匹配输入。因此我们主要关注表达式。因为表达式的结合性和优先级问题，对表达式的处理更具挑战性。

下面的文法指明了表达式的结合性和优先级。这个文法和我们在第2章中使用的文法类似，它描述了表达式、项和因子。E表