编译原理与实践-L语言设计

本节以L语言中几种最常见的、基本的语法单位的分析为例，介绍如何实现L语言的递归下降语法分析程序。程序采用了简化的设计方式，去除了语法分析树的具体构造方法和错误处理的过程，当出现错误时将终止分析过程。

L语言源程序的组织结构（忽略注释等与语法分析无关的内容）包括三部分，分别是程序头、说明部分和可执行部分。L语言程序的特点是每部分都由前导词开始，程序头以关键字program开头，变量说明以var开头，常量说明以const开头，由begin开始到end之间是可执行语句。

词法分析程序将源程序变成token串存放在token文件中，作为语法分析程序的输入文件。语法分析程序的任务就是不断读入token文件中的单词，判断单词串构成的语法单位是否符合语法规则，即是否为语法正确的程序，直到token文件结束。L语言的文法参见第2章，根据语法结构描述，可以构造如下递归下降分析程序的总控程序。

L语言的执行语句分为五种，包括由关键字for、while和repeat引导的循环语句，由关键字if引导的分支语句，以及以标识符开头的赋值语句。每当分析程序读到相应的关键字，则表明一个新的语法结构的开始，进而识别该语法单位是否符合文法定义。总控程序中的函数stSort（）将根据所读入的第一个单词对语句进行分类，以便调用不同的函数进行不同的处理。

下面以if语句为例来说明不同类型语句语法分析程序的实现。子程序采用递归下降分析法，并以抽象语法树作为语法分析的输出。

(www.xing528.com)

悬挂else问题

由于可选else的影响，文法具有二义性。例如，利用文法为语句

if true then if false then x:=x+y else x:=x*y

构建语法分析树时，有两种构造方式，如图4-11所示。左图表明else部分与第一个if语句配对，右图表明else部分与第二个if语句配对，这种二义性称为悬挂else问题。

图4-11　悬挂else问题

程序设计语言通常采用最近嵌套规则解决悬挂else问题。最近嵌套规则要求else部分与距离其最近的一个尚未得到匹配的if语句配对，也就是为语句构造如图4-11右侧所示的语法分析树。

通常，在文法产生式中建立最近嵌套规则将增加文法的复杂性，但是分析过程却非常容易实现最近嵌套规则。即使这是一个二义性文法，利用其编写程序时，只要每当遇到else关键字时，就匹配其分析程序，则正好与消除二义性的最近嵌套原则相对应。