该部分利用YACC实现了生成普通语法树，并进行了错误报告、处理和恢复。

1.1语法分析方法概述

第一步：运用Flex，将词法分析程序扫描源程序字符串、识别并生成的记号序列作为输入，语法分析阶段根据我们定制好的Pascal各个语法结构的产生式，利用Bison将其语法规则转化成自底向上的分析器，进而验证这个记号序列的合法性。若合法，则生成并输出完整的语法分析树，并转化为抽象语法树（AST）；若不合法，则对错误进行适当的恢复，向用户输出错误的性质以及发生位置。

第二步：语法树转化为AST的过程，具体见普通语法树转化为AST的详细设计。

1.2工具介绍

1.2.1 YACC概述

YACC（Yet Another Compiler Compiler），是 Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）。YACC生成的编译器主要是用 C 语言编写的语法解析器（Parser），本来只在 Unix 系统上才有，但现在已普遍移植往 Windows 及其他平台。YACC源程序文件名约定为yacc.y，通过Bison工具的编译生成yacc.tab.cpp和yacc.tab.h两个文件。

1.2.2 YACC规则

YACC的输入是巴科斯范式（BNF）表达的 LALR(1) 文法，输出是基于分析表驱动的编译器。

其源程序规则如下，与 Flex 非常相似：

  1. %{  
  2. Declarations  
  3. %}  
  4. Definitions  
  5. %%  
  6. Translation rules  
  7. %%  
  8. User subroutines

Declarations 是 C 代码的声明与实现，YACC会将这部分代码直接拷贝到生成的 C 程序中，Definitions 是 YACC的辅助说明部分，目的是为翻译规则（Translation rules）服务。在该部分一般可以定义，Translation rules 部分为翻译规则，User subroutines 是用户自定义程序段。

1.2.3 YACC冲突解决

移进/归约冲突时，执行移进动作，即移进先于归约；
归约/归约冲突时，用YACC源程序中第一个出现的产生式进行归约。

1.3 语法规则的定义

根据需求分析，我们对讲义上给出的文法产生式做出了一定的改进，并注释了改进的原因。以下产生式中，小写的字符串代表非终结符即非叶结点，反之大写的字符串以及字符常量是终结符相应的叶节点。
1 programstruct –> program_head ‘;’ program_body ‘.’ （1.1）
2 program_head –> PROGRAM IDENTIFIER ‘(‘ idlist ‘)’ （2.1）
3 program_body –> const_declarations var_declarations subprogram_declarations compound_statement （3.1）
4 idlist –> idlist ‘,’ IDENTIFIER （4.1）
| IDENTIFIER （4.2）
5 const_declarations –> CONST const_declaration ‘;’ （5.1）
| ε （5.2）
6 const_declaration –> const_declaration ‘;’ IDENTIFIER ‘=’ const_value （6.1）
| IDENTIFIER ‘=’ const_value （6.2）
//词法分析器对于常数的输出分为无符号常数和无符号常浮点数，且词法分析器也可以识别字符常量，即’字符’。故我们对常量表达式const_value的表达式作出改进如下所示（其中UINUM表示无符号常整数，UFNUM表示无符号常浮点数，CHAR表示字符常量）：
7 const_value –> ‘+’ IDENTIFIER （7.1）
| ‘-‘ IDENTIFIER (7.2)
| IDENTIFIER (7.3)
| ‘+’ UINUM (7.4)
| ‘-‘ UINUM (7.5)
| UINUM (7.6)
| ‘+’ UFNUM (7.7)
| ‘-‘ UFNUM (7.8)
| UFNUM (7.9)
| CHAR (7.10)
8 var_declarations –> VAR var_declaration ‘;’ (8.1)
| ε (8.2)
9 var_declaration –> var_declaration ‘;’ idlist ‘:’ type (9.1)
| idlist ‘:’ type (9.2)
10 type –> TYPE (10.1)
| ARRAY ‘[‘ period ‘]’ OF TYPE (10.2)
//词法分析器能够识别TYPE并将其分为integer, real, boolean和char，故我们作出改进，将“简单类型”TYPE视为了终结符。
11 period –> period ‘,’ UINUM RANGEDOT UINUM (11.1)
| UINUM RANGEDOT UINUM (11.2)
12 subprogram_declarations –> subprogram_declarations subprogram ‘;’ (12.1)
| ε (12.2)
13 subprogram –> subprogram_head ‘;’ subprogram_body (13.1)
14 subprogram_head –> PROCEDURE IDENTIFIER formal_parameter (14.1)
| FUNCTION IDENTIFIER formal_parameter ‘:’ TYPE (14.2)
15 formal_parameter –> ‘(‘ parameter_list ‘)’ (15.1)
| ε (15.2)
16 parameter_list –> parameter_list ‘;’ parameter (16.1)
| parameter (16.2)
17 parameter –> var_parameter (17.1)
| value_parameter (17.2)
18 var_parameter –> VAR value_parameter (18.1)
19 value_parameter –> idlist ‘:’ TYPE (19.1)
20 subprogram_body –> const_declarations var_declarations compound_statement (20.1)
21 compound_statement –> _BEGIN statement_list END (21.1)
22 statement_list –> statement_list ‘;’ statement (22.1)
| statement (22.2)
//对于statement文法产生式，我们在实现基本要求的基础上，增添了分别对应WHILE DO循环语句以及REPEAT UNTIL循环语句的文法产生式（23.5、 23.6）。
23 statement –> variable ASSIGNOP expression (23.1)
| procedure_call (23.2)
| compound_statement (23.3)
| IF expression THEN statement else_part (23.3)
| FOR IDENTIFIER ASSIGNOP expression TO expression DO statement (23.4)
| WHILE expression DO statement (23.5)
| REPEAT statement UNTIL expression (23.6)
| ε (23.7)
//不难知道，当处理if-then和if-then-else语句时，若不采用“最近最后匹配原则”，语法分析器将会发生臭名昭著的移进/归约冲突。Bison在处理这样的冲突时缺省的动作是进行移进，为了让冲突的解决过程更加清晰，我们定义了各个结点的优先级（注：最先定义的优先级最低，%left和%right分别代表左结合和右结合，而%nonassoc代表该记号在同一行内只能出现一次，否则发生语法错误）：

%left '+' '-' ADD  
%left '*' '/' MUL  
%right UMINUS  
%nonassoc LOWER_THAN_ELSE  
%nonassoc ELSE  
%nonassoc ONE  
%nonassoc TWO  
%nonassoc THREE

24 else_part –> ELSE statement (24.1)
| %prec LOWER_THAN_ELSE (24.2)
25 variable –> IDENTIFIER id_varpart (25.1)
26 id_varpart –> ‘[‘ expression_list ‘]’ (26.1)
| ε (26.2)
27 procedure_call –> IDENTIFIER (27.1)
| IDENTIFIER ‘(‘ expression_list ‘)’ (27.2)
28 expression_list –> expression_list ‘,’ expression (28.1)
| expression (28.2)
29 expression –> simple_expression RELOP simple_expression (29.1)
| simple_expression ‘=’ simple_expression (29.2)
| simple_expression (29.3)
30 simple_expression –> simple_expression ADDOP term (30.1)
| simple_expression ‘-‘ term (30.2)
| term (30.3)
31 term –> term MULOP factor (31.1)
| factor (31.2)
//由于字符常量也是可以参加运算的，因此作出改进，增添文法产生式32.8。
32 factor –> UINUM (32.1)
| UFNUM (32.2)
| variable (32.3)
| IDENTIFIER ‘(‘ expression_list ‘)’ (32.4)
| ‘(‘ expression ‘)’ (32.5)
| NOT factor (32.6)
| ‘-‘ factor (32.7)
| CHAR (32.8)

1.4 语法分析树涉及的数据结构

1.4.1 结点的数据类型

首先，我们重新定义了Flex和Bison共享的yylval的数据类。在词法分析阶段将记号以该类的形式传递给语法分析，从而在语法分析树的构建过程中，各个结点具有统一封装的特性。

//重新定义属性类型
class Type {
    public:
    string str;
    //终结符号的具体属性
    string token;
    //终结符号或非终结符号本身的名称
    int lineNumber;
    //终结符号的行号，参照语法分析指导.docx
    vector<Type*> children;
    //对应产生式下面的结点
    Type() {
    }
    Type(string typ, string name, int ln): str(typ), token(name), lineNumber(ln) {
    }
    Type(string name, vector<Type*> cdn): token(name), children(cdn) {
    }
}
;
#define YYSTYPE Type*

1.4.2 错误处理相关全局变量

extern int yylineno;
//当前行号
extern char* yytext;
//词法分析当前缓冲区（单词）的内容
extern char lineBuffer[500];
//当前行的所有内容
extern int yyleng;
//当前匹配字符串的长度
extern int yycolumn;
//当前列号
extern string itos(int num);
//整型转string型函数
//以上全局变量来自于词法分析，故有extern关键字
bool haveSemanticError=false;
//是否有语法错误
vector<string> syntaxErrorInformation;
//存放语法错误信息
Type* ParseTreeHead=NULL;
//整棵语法分析树的根节点

1.4.3 错误处理相关函数声明

void yyerror(const char *s, YYLTYPE *loc); //处理单个文法符号的错误信息
void yyerror(const char *s, int line, int col); //处理位于一行以内的错误信息
void yyerror(const char *s, int startLine, int startCol, int endLine, int endCol); //处理涉及到多行的错误信息

由此，加上Bison(YACC)自带的void yyerror(const char *s)用于报告致命性（终止型）语法错误，我们采用重载的机制，共有四类错误信息处理函数，应对不同的情况。

1.5 构建语法树过程描述

我们知道：
一个文法G是下述元素构成的一个四元组（N, Σ,P,S）：

  • “非终结符号”集合N。
  • “终结符号”集合Σ，Σ与N无交。
  • 取如下形式的一组“产生式规则”P，
  • (Σ ∪N)中的字符串→ (Σ ∪N) 中的字符串，并且产生式左侧的字符串中必须至少包括一个非终结符号。
  • “起始符号”S，S属于N。

故语法树构建过程的设计如下流程图所示：
image.png

以上这三个步骤在我们编写的文法文件（Bison Grammar File）有清晰的展示。

  • 非终结符的定义：加上%token的前缀。

    %token PROGRAM
%token CONST
%token VAR
%token ARRAY
%token OF
%token PROCEDURE
%token FUNCTION
%token _BEGIN
%token END
…………

  • 起始符的定义：加上%start的前缀

    %start programstruct

  • 构造结点和子树（即后两个步骤）

下面以idlist的产生式为例，说明结点和子树的改造过程：

idlist: idlist ',' IDENTIFIER{
    $$=new Type;
    $$->token = "idlist";
    $$->children.push_back($1); $$->children.push_back($2); $$->children.push_back($3);
}|IDENTIFIER{
    $$=new Type;
    $$->token = "idlist";
    $$->children.push_back($1);
};

$$表示产生式左部符号，$1、$2、$3……表示产生式右部第一个、第二个、第三个……符号。

1.6 错误处理相关设计

1.6.1 错误处理种类

  1. 程序识别失败，遇到该错误时报错并终止语法分析程序
    2. 出现非法记号，遇到该错误时报错并跳过该非法记号继续分析。
    3. 非终结符号识别失败，如不完整的函数头、过程头，不完整的参数列表，不完整的数组下表列表，错误的关键字等，遇到该错误时报错并继续分析。
    4. 标点符号缺失，遇到该错误时报错并继续分析。
    5. 运算符号缺失，遇到该错误时报错并继续分析。
    6. 常数初始化右值缺失，遇到该错误时报错并继续分析。

    1.6.2 错误处理相关产生式处理

    在YACC工具中，采用引入错误产生式的方法，即在出错的位置插入一个名为error的token到输入中，并在相应翻译方案中调用yyerror错误处理函数。错误产生式的翻译方案中建立残缺的语法树，只将产生式左部符号的节点加入到语法树中，右部的文法符号抛弃。

以id_varpart的产生式为例：

id_varpart: '[' expression_list ']'{ //正常
    $$=new Type;
    $$->token="id_varpart";
    $$->children.push_back($1);$$->children.push_back($2);$$->children.push_back($3);
}|'[' error{ //ERROR 不完整的数组下标列表 checked
    $$=new Type;
    $$->token="id_varpart";
    yyerror("incomplete expression list of array subindex", &@$);
}|'[' expression_list error{ //ERROR 缺失右中括号 checked
    $$=new Type;
    $$->token="id_varpart";
    yyerror("missing a right square bracket here", @2.last_line, @2.last_column+1);
}|{ //正常
    $$=new Type;
    $$->token="id_varpart";
};

error代替了正确文法符号的位置，这里有两种错误情况，第一种是不完整的数组下标列表，第二种是右括号缺失，分别对应的是处理单个符号的错误信息和处理一行内的错误信息。

在词法分析详细设计中已经提到YYLTYPE的数据结构，first_line表示当前文法符号代表的内容的起始行，first_column表示当前文法符号代表的内容的起始列，last_line表示当前文法符号代表的内容的终止行，last_column表示当前文法符号代表的内容的终止列。

1.6.3 错误处理相关函数设计

除YACC自带的yyerror函数用于报告致命性（终止型）语法错误以外，我们使用重载设计了另外三种错误处理机制：

void yyerror(const char *s) {
    haveSemanticError = true;
    //错误标志，含有语法错误
    string errorInformation;
    //定义错误信息
    errorInformation += string(s);
    //添加错误信息
    errorInformation += ", location: " + itos(yylineno-1) + "." + itos(yycolumn-yyleng);
    //添加错误位置
    syntaxErrorInformation.push_back(errorInformation);
    //存放错误信息
}
void yyerror(const char *s, YYLTYPE *loc) {
    //处理单个字符的错误
    haveSemanticError = true;
    string errorInformation;
    errorInformation = "syntax error, " + string(s) + ", location: " + itos(loc->first_line) + "." + itos(loc->first_column) + "-" + itos(loc->last_line) + "." + itos(loc->last_column);
    syntaxErrorInformation.push_back(errorInformation);
}
void yyerror(const char *s, int line, int col) {
    //处理一行以内的错误
    haveSemanticError = true;
    string errorInformation;
    errorInformation = "syntax error, " + string(s) + ", location: " + itos(line) + "." + itos(col);
    syntaxErrorInformation.push_back(errorInformation);
}
void yyerror(const char *s, int startLine, int startCol, int endLine, int endCol) {
    //处理涉及多行的错误
    haveSemanticError = true;
    string errorInformation;
    errorInformation = "syntax error, " + string(s) + ", location: " + itos(startLine) + "." + itos(startCol) + "-" + itos(endLine) + "." + itos(endCol);
    syntaxErrorInformation.push_back(errorInformation);
}

错误信息格式为：
syntax error +错误内容+location：错误内容起始位置所在行.起始位置所在列-终止位置所在行.终止位置所在列（若是一行内单个符号出现错误，只需报告该符号的所在行.所在列）。
将所有错误信息存入 syntaxErrorInformation中，便于语法分析结束后将所有的语法错误一并输出。