概述

语法分析是编译过程的核心部分，语法分析程序的输入是词法分析程序在扫描字符串源程序的过程中识别并生成的记号序列，语法分析程序分析验证这个记号序列是不是符合该语言语法规则的一个程序，若是，则输出其语法树，若不是，则表明输入的记号序列中存在语法错误，需要报告错误的性质和位置。

语法分析需要输出一棵抽象语法树。

我们将借助YACC工具，以LALR（1）的自底向上分析方法进行语法分析。为此，我们需要学习PASCAL_S语言，从中抽象出其语法结构，以文法表示。

我们需要一层一层（从简单到复杂）的分析PASCAL_S的各种语法单位，为详细设计中的文法设计奠定基础。

PASCAL程序由三大部分组成：程序首部（head），说明部分（变量、常量、子过程、子函数的定义），语句部分（body，主程序，是一个复合语句块）。

常量

const关键字用以说明接下来的定义语句都属于常量定义。常量定义需要指定初值，且不必指定类型。常量的初值可以由整数、浮点数、字符常量、别的常量标识符等指明，可以是一个可以由编译器计算出结果的常量表达式（这里我们将其简化，限定为只能是+、-等弹幕运算符加上一个常量标识符组成的最简单的常量表达式）。PASCAL-S的常量定义不包含类型，因此其类型需要编译器判断。

变量的定义

var关键字用以说明接下来的定义语句都属于变量定义。变量定义必须指明类型，无需指定初值。变量也可以是一维或多维数组，数组的各维下标由表达式组成。

类型

可以是最简单的基本类型：integer、real、boolean、char，也可以是由这些基本类型组成的数组。

参数表

函数/过程的头部最重要的就是参数列表，参数列表由一系列的标识符、类型关键字组成的参数变量定义组成。PASCAL_S的参数有两种，引用和传值，语法上的区别在于是否包含var关键字。

表达式

表达式是由一系列的操作符和操作数组成的，其定义一般是递归的，也就是说，操作数不止是“数”，也可以是一个表达式。我们从操作符优先级的角度进行了分层，使得表达式的语法结构更加清晰。

首先引入最底层的因子概念，因子包括：（1）一个常量；（2）一个变量；（3）由单目运算符not、-与另一因子组成的新的因子（这些单目运算符的优先级通常是最高的）；（4）括号括起来的表达式；（5）函数调用；

然后是项的概念，项可以是一个因子，也可以是由*、/、div、mod、and等优先级较高的双目运算符和两个因子组成的。

接下来是简单表达式的概念，简单表达式可以是一个项，也可以是由+、-、or等优先级较低的双目运算符和两个项组成。

最终是表达式的概念，表达式可以是一个简单表达式，可以是由>、=、<、<=、>=、<>等优先级最低的关系双目运算符和两个简单表达式组成。

语句

语句除了函数（通常表现为赋值语句）、过程调用（过程调用单独作为一条语句，产生某种副作用）外，主要以顺序结构、分支结构、循环结构分成三类。
顺序结构是由begin和end关键字及其包括的递归定义的复合语句块。

分支结构我们只支持if条件语句，其结构如下：

  1. IF <条件>
  2. THEN <语句1>
  3. ELSE <语句2>

注：1、ELSE与最近的并且未被配对的ELSE配对；
2、 复合，如果THEN或ELSE带有多个语句，则要用BEGIN—END括起来

循环结构我们支持FOR语句、WHILE语句和REPEAT语句。
FOR语句的结构如下：

FOR<循环变量>:=<初值> TO<终值> DO<语句>

WHILE语句与C语言中的WHILE语句基本一致，其结构如下：

WHILE <条件> DO <语句>

   REPEAT语句则类似于C语言中的DO-WHILE语句，即至少会执行一次循环体，但是在条件测试上有所区别，REPEAT-UNTIL语句在UNTIL指明的条件为真时退出循环。其结构如下：

REPEAT
<循环体>
UNTIL
<条件>分程序

子函数/过程

函数和过程的头部中都包括名称和参数表，此外函数头还需指明返回值的类型，然后是子函数/过程的主体。子函数/过程中不能再嵌套函数/过程，另外，常量定义、变量定义、复合语句块等都与主程序类似。

分程序

分程序指的是PASCAL-S的主程序部分，首先要给出常量和变量的定义，然后是函数/过程的定义，最后是语句主体（begin和end包括的复合语句块）

程序

程序由程序名称标识符、参数列表和分程序组成。这里的参数列表给出的参数标识符，通常用于命令行参数的指定。与子函数/过程不同的是，这里不指出标识符的类型。因此，如果程序主体中用到了该参数，就必须在变量定义区中再定义一次，指明具体类型。

语法分析和语义分析都可以用YACC进行，其中语法分析的侧重点在于错误处理和提示，以便为后续语义分析提供正确的语法结构（语法树）。接下来我们从语法分析的错误处理角度进行需求分析。

错误处理

据统计，源程序中出现的错误多是语法错误，所以，编译时大多数错误的诊断和恢复工作集中在语法分析阶段。

语法分析程序进行错误处理的基本目标如下：
（1） 能够清楚而准确地报告发现的错误，如错误的位置和性质。
（2） 能够迅速地从错误中恢复过来，以便继续诊断后面可能存在的错误。
（3） 错误处理功能不应该明显地影响编译程序对正确程序的处理效率。

要完成目标（1），需要我们主观积累经验，收集可能的错误，如常见的算法表达式的括号不匹配、缺少运算对象等，并对症下药。其次，准确地识别到错误发生的位置后，应无误地将位置（错误代码行数）和性质输出。在我们采用的LALR(1)分析中，分析程序总是根据当前的栈顶状态和当前输入符号去查分析表，若找不到合法的动作，则意味着发现了一个语法错误。

实现目标（2）和（3），需要采用合理的错误恢复策略。例如小范围的短语级恢复，对于算法表达式的括号不匹配，可选择向前指针跳过当前符号，继续分析。结合利弊，对不同的错误进行分别处理和恢复。

二义性消除

所有的二义性文法都不是LR文法。但PASCAL的某些结构用二义性文法描述比较直观且使用方便，例如if条件语句的直观描述产生式为S->if E then S else S | if E then S | others，根据PASCAL规定语法，需要在语法分析阶段增加“最近最后匹配原则”解决可能引发的冲突问题。

总之，在PASCAL语言中，有的文法表示可能是二义性的，但都说明了消除二义性的一些规则，以保证对每个句子的解释是唯一的，我们需要利用这些规则，确保语法分析不会受困于二义性的陷阱。