《现代编译原理-C语言描述》（3）- 语法分析

底层

发布日期: 2019-04-01

第三章语法分析

语法(syn-tax):组合单词以形成词组,从句或句子的方法。
—-韦氏词典

* 一个状态数为N的自动机无法记忆嵌套深度大于N的括号 *,因为状态数为N的自动机一定会到达终态，并无法继续读入。词法分析器Lex实现上一章中的digits时，只要简单的用digits右部的式子[0-9]+来替换就可以了。但是这种方式对于下面给出的三个正则表达式却行不通：

digits=[0-9]+
sum=expr"+"expr
expr="("sum")"|digits

我们可以尝试一下将expr中的sum替换掉expr="("expr"+"expr")"|digits,但是如果继续用expr替换自身，右部依然会出现expr，并且数量会越来越多。

所以这种形式的缩写并不能增强正则表达式的语言描述能力（它并没有定义额外的语言），除非这种缩写形式是递归的。但是这种递归带来的额外的表达能力正是语法分析所需要的，一旦有了递归的缩写形式，则出来在表达式的顶层之外，可以不再需要可选操作。克林闭包也不再是必须的。

这样我们就得到了一种简单的表示法，称为上下文无关文法（context-free grammer）。事实上文法也可以用来描述词法单词的结构。但是我们需要比DFA更强大的方法来分析文法所描述的语言。

上下文无关文法

对于语法分析而言：

字符串---源程序
符号---词法单词
字母表---词法分析器返回的单词类型集合

每一个符号或是终结符（terminal）（老子字母表中的单词），非终结符（nonterminal）（绝不会出现在产生式的左部）。还有一个开始符号。

文法3-1直线式程序的语法：

终结符：id print num + ,（ ） := ；
非终结符：S E L

由3-1写成的源程序

a := 7;
b := c + (d := 5+ 6, d)

其中名字a，b，c，d和数字是与其中一些单词相关联的语义值（semantic value）。

推导

derivation，从开始符号，对右部的每一个非终结符都用此非终结符对应的产生式中的一个右部来替换。

这里很容易想到一个句子可以存在多种不同的推导，其中有两种推导：

最左推导（leftmost derivation）：是一种总是扩展最左边非终结符的推导
最右推导（rightmost derivation）：是一种总是扩展最右边非终结符的推导

3-1既不是最左推导也不是最右推导

语法分析树

parse tree，将推导中的各符号连接从他推导出来的符号

如上图，两种不同的推导可以有相同的语法树。

二义性语法

如果一个文法能够推导出两种不同语法树的句子，则该文法有二义性（ambiguous），句子有两颗语法分析树

二义性文法会给编译带来问题，通常我们希望文法是无二义性的。二义性的文法通常也可以转换称无二义性的文法。

例如，文法3-2是一种而二义性的文法：

我们假定*比+具有更紧密的约束，换言之，*具有较高的优先级。其次，假定每一种操作符都是左结合的，通过引入一个新的非终结符得到无二义性的文法3-3：

E---表达式expression
T---项term
F---因子factor

如果我们想让*是右结合的，只要将表达式改写为$T \rightarrow F*T$即可。

这种方法可以消除一些语言的二义性，但是一些语言只有有二义性的文法。

文件结束符

语法分析器不仅会读入终结符，也会读入文件结束标志我们用$来表示。为了指明$必须出现在一个完整的S词组之后，需要引入一个新的开始符号$ S’ $ 以及一个新的产生式$ S’ \rightarrow S＄$
例如文法3-4：

预测分析

有一些文法使用一种称为递归下降（recursive descent）的简单算法就很容易进行分析，这种方法的本质是将文法产生式传唤为递归函数中的一个字句。下面为文法3-5写一个递归下降文法分析器。文法3-5：

这个语言的递归下降语法分析器对每一个非终结符有一个函数，非终结符的每个产生式对应一个字句：

enum token{IF,THEN,ELSE,PRINT,BEGIN,END,NUM,EQ,SEMI};
extern enum token getToken(void);

enum token tok;
void advance() {tok=getToken();}
void eat(enum token t){if(tok==t) advance();else error();}

void S(void){
    switch(tok){
        case IF: eat(IF);E();eat(THEN);S();
                             eat(ELSE); S(); break;
        case BEGIN:eat(BEGIN); S(); L(); break;
        case PRINT:eat(PRINT); E(); break;
        default: error();
    }
}

void L(void){
    switch(tok){
        case END: eat(END); break;
        case SEMI: eat(SEMI); S(); L(); break;
        default: error();
    }
}

voidE(void){
    eat(NUM); eat(EQ); eat(NUM);
}

对于文法3-4：

void S(void){ E(); eat(EOF);}
void E(void){
    switch(tok){
        case ?:E(); eat(PLUS); T(); break;
        case ?:E(); eat(MINUS); T(); break;
        case ?:T(); break;
        default: error();
    }
}

void T(void){
    switch(tok){
        case ?:T();eat(TIMES);F();break;
        case ?:T();eat(DIV); F(); break;
        case ?:F();break;
        default:error();
    }
}

这事产生了一个冲突，函数E的前两个字句E并不知道该使用哪一个。

递归下降分析也称为预测（predictIve）分析，只适合于每个子表达式的第一个终结符号能够为产生式的选择提供足够信息的文法。

有时候使用分析器生成器并不方便，预测分析器的优点就在于我们可以使用它手工构造分析器。

FIRST集合和FOLLOW集合

为了便于理解，下面我们形式化FIRST的概念，然后用一个简单的算法导出无冲突的递归下降语法分析器。

给定一个由终结符和非终结符组成的字符串 $\gamma$ ,FIRST( $\gamma$ ), 是可以从 $\gamma$中推导出的由终结符组成的字符串都必定以id,num,(开始。因此有
$$
FIRST(T*F)={id,num,(}
$$
但是如果两个不同的产生式 $X \rightarrow \gamma_1$和 $X \rightarrow \gamma_2$具有相同的左部符号(X),并且它们的右部有重合的FIRST集合,则这个文法不能使用预测分析法来分析。

下面对文法3-6进行分析，文法3-6：

对一个特定的文法，当给定由终结符和非终结符组成的字符串 $\gamma$时下列论述成立：

若X可以导出空串，那么nullable（X）为真。
FIRST（$\gamma$）是可从$\gamma$推导出的字符串的开头终结符的集合。
FOLLOW（X）是可以直接跟随于X之后的终结符集合。也就是说
- 如果存在着任意一推导包含 Xt，则$t \in FOLLOW(X)$
  - 当推导包含XYZt，其中Y和Z都推导出 $\epsilon$时，也有$t \in FOLLOW(X)$。

下面我们就可以给出计算字符串FIRST，FOLLOW，nullable集合的算法

计算这三个关系式时可不必同时计算，例如对于文法3-6，我们初始有：

	nullable	FIRST	FOLLOW
X	no
Y	no
Z	no

在第一次迭代中，我们可以发现关系产生了变化

	nullable	FIRST	FOLLOW
X	no	a	c d
Y	yes	c	d
Z	no	d

在第二次迭代中我们可以发现X也是可以为空的。因此

	nullable	FIRST	FOLLOW
X	yes	a c	a c d
Y	yes	c	a c d
Z	no	a c d

在第三次迭代中，没有新的信息，于是算法中止。

也可以将FIRST关系推广到符号串中：
$$
\begin{align}
&FIRST(X\gamma)=FIRST[X] \qquad \qquad \qquad \qquad 若！nullable[X]\\
&FIRST(X\gamma)=FIRST[X] \cup FIRST(\gamma) \qquad 若nullable[X]\\
\end{align}
$$

构造预测分析器

下面来介绍一种较为简单的方法。可以让我们手工构造预测分析器。假设我们有一个递归下降分析器，如果能为每一个 $(X,T)$ ,选择正确的产生式.我们所需要的所有信息都可以由一张二维表表示，即预测分析表（predicative parsing table）。

上图的文法具有二义性,会导致预测分析器有多重定义的项，这样无法得到一个程序设计语言。

若文法不含多重定义的项，则称其为 $LL（1）$ 型文法， $LL（1）$ 代表 从左到右分析，最左推导和超前查看一个符号（Left-to-right parse,Leftmost-derivation，1-symbol lookhead） 。推广 $ FIRST $ 集合的概念，对于任何k，不存在任何有二义性的文法是
$ LL（k）$ 型文法，但是这样会预测分析表过于庞大，很少会采用这种方法，但有时在手工编写递归下降分析器时会遇到这样的情况。

消除左递归

$$
\begin{align}
& E \rightarrow E + T \\
& E \rightarrow T
\end{align}
$$
会导致左递归（left recursion），具有左递归的文法不是 $LL（1）$ 型文法。为了消除左递归，我们可以用右递归来重写产生式，引入一个新的非终结符 $E’$ ,并将产生式重写为：

$$
\begin{align}
& E \rightarrow T E’ \\
& E \rightarrow +T E’ \\
& E’ \rightarrow
\end{align}
$$

这样就获得了一个没有左递归的文法

提取左因子

同左递归一样，当一个非终结符的的两个产生式以相同的符号开始时 会发生类似的问题，如：
$$
\begin{align}
& S \rightarrow if\quad E \quad then\quad S \quad else\quad S \\
& S \rightarrow if\quad E \quad then\quad S
\end{align}
$$
对文法提取左因子，取出非公共的尾部：
$$
\begin{align}
& S \rightarrow if\quad E \quad then\quad S \quad X \\
& S \rightarrow \\
& S \rightarrow else \quad S
\end{align}
$$

错误恢复

文法3-7的代码：

void T(void){
    switch (tok) {
        case ID:
        case NUM:
        case LPAREN: F(); Tprime(); break;
        default: error!
    }
}
void Tprime(void){
    switch (tok) {
        case PLUS: break;
        case TIMES: eat(TIMES); F(); Tprime(); break;
        case RPAREN: break;
        default: error!
    }
}

错误处理的较好方式是：输出一条信息，然后尝试恢复错误，并继续后继处理，从而可以发现更多错误。

插入单词
插入单词来进行错误恢复是一种危险的做法，可能插入会进一步导致其他错误，陷入死循环。插入法不必对实际的输入调整，假装存在某个单词，输出错误信息，然后返回即可
```
void T(void){
  switch (tok) {
      case ID:
      case NUM:
      case LPAREN: F(); Tprime(); break;
      default: printf("expected id,num, or left-paren");
  }
}
```
删除单词
跳过若干个单词直至达到一个属于 FOLLOW 集合的单词为止.
```
int TPrime_follow [] = {PLUS ,RPAREN,EOF,-1};
void Tprime(void){
  switch (tok) {
      case PLUS: break;
      case TIMES: eat(TIMES); F(); Tprime(); break;
      case RPAREN: break;
      case EOF: break;
      default: printf("expected +,*,right-paren, or end-of-file");
      skipto(TPrime_follow);
  }
}
```
递归下降分析器的错误恢复必须具有调整机制。尝试-出错-再尝试。
LR分析
LL(k)技术在看到等式右部的前k个单词就必须预测要使用的是哪一个产生式，另一种技术LR（k）分析，LR分析使用栈，这样可以在输入整个右部以后再做判断。LR（k）代表 从左到右分析,最右推导，超前查看k个单词（Left-to-right parse，Rightmost-derivation，k-tocken lookhead）。

LR（k）分析有一个栈和一个输入，输入中的前k个单词为超前查看的单词。根据栈和超前查看的单词，分析器执行两种动作

移进：压栈，最后移进文件爱你结束符的动作称为接收（accepting）
归约：选择文法，弹出文法表达式的单词，移进等式左部。

LR分析引擎

又是Kunth真神开发的。ORZ

LR通过作用于栈的DFA来判断应该采取的策略，DFA的边是由非终结符和终结符来标记的。

转换表中的元素有四种动作：

sn 移进到状态n
gn 转换到状态n
rk 根据规则k归约
a 接受
错误

对于每一个单词，分析器不是重新扫描栈，而是记住没一个栈元素到达的状态

LR（0）分析器生成器

上表说明了当k等于1时，当k=2时，这个表的每个序列是又两个单词组成的序列，实际编译器并不使用k>1的表。我们使用文法3-8来构造一个LR（0）分析器，
文法3-8

最开始的状态是1

其中圆点代表分析器当前的位置，，文法规则与指出其右部位置的圆点组合称为项

移进动作（shift action）
根据文法3-8可能会出现两个状态
转换动作（goto action）位移圆点，当某个文法被归约时，弹出所有右部符号
归约动作（reduce action）

可以得到DFA

然后根据DFA可以构造出分析表

SLR分析器的生成

比LR(0)更好的一种技术是SLR即Simple LR的简称，SLR和LR（0）的构造方法近乎相同，但是SLR只在FOLLOW集合制定的地方放置归约动作。

回忆LR(0)分析表的构造过程

对于任意一条边 $I \xrightarrow{X} J$
- 若X为终结符，则在表中 $(I,X)$ 加移进J(sJ)
  - 若X为非终结符，则在表中 $(I,X)$加转换J(gJ)
对于包含项 $S’ \rightarrow S.＄$ 的每个状态I我们在位置 $(I,＄)$ 放置接收动作（a）
对于包含项 $A \rightarrow \gamma$ 的状态，对每一个单词Y，放置归约n（rn）于 $(I,Y)$ 中。

得到LR（0）的分析表以后我们判断是否rn的这个单词属于FOLLOW(A)，如果不属于则删除。

LR（1）项和LR（1）分析表

LR（1）比SLR更为强大，相对于LR(0)分析，LR(1)分析表项的概念更见复杂，由三个要素构成：

一个文法产生式
一个右部位置（圆点表示）
一个超前查看的符号

即项 $(A \rightarrow \alpha,\beta,x)$ 指出：序列 $\alpha$ 在栈顶，且输入中开头的死可以从 $\beta x$ 中导出的符号串。

例如一个不是SLR的文法3-10有这样的DFA

只要产生式的结尾有圆点，那么在LR(1)分析表中，行为状态号，列为超前查看符的地方就存在一个归约动作。

LALR（1）分析表

LALR(1)表即（Look-head LR(1)），观察DFA我们可以发许多状态都是重复的，为了节省空间，我们可以吧除了超前插卡符号，其他状态都相同的状态合并，这样就可以得到一个储存空间的较小的表，但是对于某些文法，LALR(1)含有归约-归约冲突，但是使劲应用中，这种影响非常小。

各类文法的层次

所有的SLR型文法都是LALR(1)文法，但反之不成立。

LALR(1)文法已经变成程序设计语言和自动语法分析器的生成器的标准。

二义性文法的LR分析

许多文法含有二义性，这里我们采取最近匹配的原则，或者引入两个非终结符来重写语法。但是最好的方法还是消除二义性。

使用分析器的生成器

Yacc(Yet another complier-complier)的规范分为三部分：

parse declaration //终结符，非终结符组成的表
%%
grammer rules //产生式like  exp： exp PLUS exp { semantic action}
%%
programs  //原始C代码

冲突

Yacc可以指出两种冲突并自动解决

移进-归约：优先移进
归约-归约：优先文法中靠前的规则

优先级指导

之前我们解决优先级的方法是引入两个辅助符号，但是还有一种方法是先构造出二义性文法的LR(1)分析表，然后修改表中的填入的内容来设定优先级的顺序。

Yacc有一种指明这类移进-归约冲突的 优先级指导命令 ，like：

%nonassoc EQ NEQ
%left PLUS MINUS
%left TIMES DIV
%right EXP

指出+和-是左结合的且优先级相同，*和/是左结合的且优先级相同并高于+,^是右结合的且优先级最高，=和！=是非结合的，且优先级低于+。当比较一个单词和一个规则的优先级时，规则的优先级有规则最右部的单词的优先级给出当单词和规则的优先级相同时，用%left指明的偏向于归约，而%right指明的偏向于移进。

我们也可以使用命令%prec来指明明确的优先级，可以解决这类问题，如一元负运算问题

%{ declarations of yylex and yyerror %}
%token INT PLUS MINUS TIMES UMINUS
%start exp
%left PLUS MINUS
%left TIMES
%left UMINUS
%%
exp :INT
    |exp PLUS exp
    |exp MINUS exp
    |exp TIMES exp
    |MINUS exp %prec UMINUS

语法和语义

假如一个文法中既有布尔表达式又有算数表达式，算术运算的优先级高于布尔表达式，且布尔表达式不能与算数表达式相加。可以得到文法

%{ declarations of yylex and yyerror %}
%token ID ASSIGN PLUS MINUS AND EQUAL
%start stm
%left OR
%left AND
%left PLUS
%%
stm : ID ASSIGN ae
    | ID ASSIGN be
be  :
    |be OR be
    |be AND be
    |ae EQUAL ae
    |ID
ae  : ae PLUS ae
    | ID

文法存在一个移进-归约冲突。解决办法是将问题推迟到语义分析的阶段，可以修改文法使其在文法上是合法的。

错误恢复

我们希望编译器能够找出所有的错误，而不是在第一个错误处就停下并报错。

用error符号恢复

局部错误分析

他哦难过调整分析栈和错误查出点的输入以允许分析能够继续进行的来实现的。 $error$ 符号控制对错误恢复的处理， $error$ 可以匹配一串出错的输入单词。

分析器在表达式的中间遇到错误时，应该跳到下一个分号或右括号处[aka 同步单词（synchronizing token）]。可以通过增加两个错误恢复产生式，实现这一点
$$
\begin{align}
& exp \rightarrow (error) \\
& eps \rightarrow error;exp
\end{align}
$$

$error$被看作是一个终结符，当LR分析器遇到 $error$时采取：

依次弹出栈顶的符号直至达到某个状态关于 $error$的状态是移进
移进 $error$ 单词
必要时依次跳过输入符号直至达到一个超前查看单词，这个单词在当前状态有一个非错误的动作
重新开始分析

需要注意的是Yacc的文法规则可能带有语义动作（semantic action）。可能会导致一些难以想象的语义动作

全局错误分析（global error repair）

最好的办法是在输入流出错点之前插入或删除单词。我们寻找的是可以将原先程序变为正确语法的最小的插入或删除集合，即使插入和删除的位置并不是LL或LR分分析器首先报告错误的地点。

Burke-Fisher错误修复

顾名思义是Burke和Fisher发明的错误分析方法啊，这是一个通过管理一个K个单词的序列和两个分析栈来实现错误修复的策略。也就是说，假设K=15，若分析器在扫描到输入的第100个单词时遇到了语法错误，那将在第85到100之间的单词尝试每一种可能的修复。，通常若一次修复能够使分析器超过错误点继续前进R=4个单词，就是一次足够好的修复。分析器要回退到K个单词之后重新开始分析，所以要管理两个栈，当前栈和老栈。每当移进一个新单词，将新单词压当前栈，，将新单词压入队列尾部，并取出队列头压老栈。

在有N个单词的序列中存在 $K+KN+KN$种可能性。

语义动作

BF错误恢复法，在当前栈并不执行语义动作，而是推迟到老栈进行。也就是说语义执行的地点会提前K+R个单词，如果语义对词法分析的行为有影响，那就很不妙。

插入单词的语义值

分析器需要为每个插入的单词提供一个语义值，使得语义动作的执行就像这些单词原本就来自词法分析器，Yacc提供了一个%value指导命令，允许程序员指明插入的单词的值。

%value ID ("bogus")
%value INT (1)
%value STRING ("")

程序员制定的替代

程序员可以使用%change指导命令来给出首选尝试的建议

%change  |EQ -> ASSIGN | ASSIGN -> EQ
SEMICOLON ELSE -> ELSE
| -> IN INT END

插入in 0 end是非常重要的更正，成为作用域关闭器（scope closer），可以在编译器需要三个单词才能关闭作用域时，关闭作用域。

程序设计：语法分析

在chap03目录下的文件分别是

errormsg.c   \\存放出错的数据结构，帮助产生文件名和行号的报错信息
lex.yy.c     \\作者提供的词法分析器的输出
parsetest.c  \\驱动程序，运行分析器来分析输入文件
util.c
y.output
errormsg.h   \\存放出错的数据结构，帮助产生文件名和行号的报错信息
makefile     \\工程创建文件
tiger.grm    \\我们需要完善的语法框架
util.h

可以使用优先级指导命令，但是不要给文法附加任何语义动作。

这里我们先使用作者提供的lex输出，如果要修改为自己的词法分析器只要将makefile中的注释打开就行了

a.out: parsetest.o y.tab.o lex.yy.o errormsg.o util.o
    cc -g parsetest.o y.tab.o lex.yy.o errormsg.o util.o

parsetest.o: parsetest.c errormsg.h util.h
    cc -g -c parsetest.c

y.tab.o: y.tab.c
    cc -g -c y.tab.c

y.tab.c: tiger.grm
    yacc -dv tiger.grm

y.tab.h: y.tab.c
    echo "y.tab.h was created at the same time as y.tab.c"

errormsg.o: errormsg.c errormsg.h util.h
    cc -g -c errormsg.c

lex.yy.o: lex.yy.c y.tab.h errormsg.h util.h
    cc -g -c lex.yy.c

#lex.yy.c: tiger.lex
#    lex tiger.lex

util.o: util.c util.h
    cc -g -c util.c

clean:
    rm -f a.out util.o parsetest.o lex.yy.o errormsg.o y.tab.c y.tab.h y.tab.o

然后我们就来看一下tiger.grm文件

%{
#include <stdio.h>
#include "util.h"
#include "errormsg.h"

int yylex(void); /* function prototype */

void yyerror(char *s)
{
 EM_error(EM_tokPos, "%s", s);
}
%}


%union {
    int pos;
    int ival;
    string sval;
    }

%token <sval> ID STRING
%token <ival> INT

%token
  COMMA COLON SEMICOLON LPAREN RPAREN LBRACK RBRACK
  LBRACE RBRACE DOT
  PLUS MINUS TIMES DIVIDE EQ NEQ LT LE GT GE
  AND OR ASSIGN
  ARRAY IF THEN ELSE WHILE FOR TO DO LET IN END OF
  BREAK NIL
  FUNCTION VAR TYPE

%start program

%%

program:    exp

exp:   ID

文件的前半部分已经完善，我们需要书写的是后面的grammer rules和programs部分。

要书写语法分析器，首先我们要把Tiger语言转化为一般的文法形式。Tiger语言的文法显然要比我们之前讨论的文法形式更多也更复杂，所以我们使用更明显的的名称来书写等式左部。

首先考虑一下，在附录中我们可以知道，Tiger语言共有种语句，26种表达式，分别是

得到了Tiger语言的文法以后我们就可以根据Yacc的规范来书写tiger.grm文件了。

我使用的是Ubuntu 18.04系统安装的是Yacc的一个较新的实现Bison

$ yacc --version
bison (GNU Bison) 3.0.4
Written by Robert Corbett and Richard Stallman.

Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

这里简单介绍一下Bison的基本使用，在Bison官网我们可以了解到Bison的语法和使用规则。

最终的tiger.grm文件如下：

%{
#include <stdio.h>
#include "util.h"
#include "symbol.h"
#include "errormsg.h"
#include "absyn.h"
int yylex(void); /* function prototype */
A_exp absyn_root;
void yyerror(char *s)
{
EM_error(EM_tokPos, "%s", s);
}

%}

%union {
    int pos;
    int ival;
    string sval;
    A_var var;
    A_exp exp;
    /* et cetera */
    A_expList    expList;
    A_decList    decList;
    A_dec dec;
    A_ty ty;
    A_namety namety;
    A_nametyList nametyList;
    A_fundec funcdec;
    A_fundecList funcdecList;
    A_field    field;
    A_fieldList fieldList;
    A_efield efield;
    A_efieldList efieldList;
}

%token <sval> ID STRING
%token <ival> INT
%token
COMMA COLON SEMICOLON LPAREN RPAREN LBRACK RBRACK
LBRACE RBRACE DOT
PLUS MINUS TIMES DIVIDE EQ NEQ LT LE GT GE
AND OR ASSIGN
ARRAY IF THEN ELSE WHILE FOR TO DO LET IN END OF
BREAK NIL
FUNCTION VAR TYPE
%nonassoc LOWER
%nonassoc OF
%nonassoc IF THEN WHILE DO FOR TO
%left ELSE
%nonassoc ASSIGN
%left OR AND
%nonassoc EQ NEQ GT LT GE LE
%left PLUS MINUS
%left TIMES DIVIDE
%nonassoc TYPE
%nonassoc FUNCTION

%start program
%%
program
    : exp   {}

exp : varExp {}
        | nilExp {}
        | intExp {}
        | stringExp {}
        | callExp {}
        | opExp {}
        | recordExp {}
        | seqExp {}
        | assignExp {}
        | ifExp {}
        | whileExp {}
        | forExp {}
        | breakExp {}
        | letExp {}
        | arrayExp {}

varExp
    : lvalue {}

nilExp
    : NIL {}

intExp
    : INT {}

stringExp
    : STRING {}

callExp
    : ID LPAREN argList RPAREN  {}

opExp
    : exp PLUS exp {}
        | exp MINUS exp {}
        | exp TIMES exp {}
        | exp DIVIDE exp {}
        | exp EQ exp {}
        | exp NEQ exp {}
        | exp LT exp {}
        | exp LE exp {}
        | exp GT exp {}
        | exp GE exp {}
        | MINUS exp {}

recordExp
    : ID LBRACE efieldList RBRACE {}

seqExp
    : LPAREN seqList RPAREN {}

assignExp
    : lvalue ASSIGN exp {}

ifExp
    : IF exp THEN exp ELSE exp {}
        | IF exp THEN exp {}
        | exp OR exp {}
        | exp AND exp {}

whileExp
    : WHILE exp DO exp {}

forExp
    : FOR ID ASSIGN exp TO exp DO exp {}

breakExp
    : BREAK {}

letExp
    : LET decList IN seqList END {}

arrayExp
    : ID LBRACK exp RBRACK OF exp {}

lvalue
    : ID  {}
        | lvalue DOT ID {}
        | lvalue LBRACK exp RBRACK {}
        | ID LBRACK exp RBRACK {}

argList
    : %empty {}
        | exp argList_ {}

argList_
    : %empty {}
        | COMMA exp argList_ {}

efield
    : ID EQ exp {}

efieldList
    : %empty {}
        | efield efieldList_ {}

efieldList_
    : %empty {}
        | COMMA efield efieldList_ {}

seqList
    : %empty {}
        | exp {}
        | exp SEMICOLON seqList {}

decList
    : dec %prec LOWER {}
        | dec decList {}

dec : typeDec {}
        | varDec {}
        | funcDec {}

typeDec
    : nametyList {}

varDec
    : VAR ID ASSIGN exp {}
        | VAR ID COLON ID ASSIGN exp {}

funcDec
    : funcDecList {}

funcDecList
    : funcDec_ %prec LOWER {}
        |   funcDec_ funcDecList {}

funcDec_
    : FUNCTION ID LPAREN fieldList RPAREN COLON ID EQ exp {}
        | FUNCTION ID LPAREN fieldList RPAREN EQ exp {}

nametyList
    : namety %prec LOWER {}
        | namety nametyList {}

namety
    : TYPE ID EQ ID {}
        | TYPE ID EQ LBRACE fieldList RBRACE {}
        | TYPE ID EQ ARRAY OF ID {}

field
    : ID COLON ID {}

fieldList
    : %empty {}
        | field fieldList_ {}

fieldList_
    : %empty {}
        | COMMA field fieldList_ {}

每个文法生成式之后的括号是为了后面第四章要使用到的语义分析，这里暂且先留空，第一次make的时候出现了这个问题（开玩笑的，其实make好几遍了）：

$ make
cc  -g -c parsetest.c
parsetest.c: In function main:
parsetest.c:16:59: warning: implicit declaration of function exit [-Wimplicit-function-declaration]
  if (argc!=2) {fprintf(stderr,usage: a.out filename\n); exit(1);}
                                                           ^~~~
parsetest.c:16:59: warning: incompatible implicit declaration of built-in function exit
parsetest.c:16:59: note: include ‘<stdlib.h>’ or provide a declaration of ‘exit’
yacc -dv tiger.grm
tiger.grm: warning: 3 shift/reduce conflicts [-Wconflicts-sr]
cc -g -c y.tab.c
cc -g -c lex.yy.c
In file included from lex.yy.c:1:0:
lex.yy.c:20:15: error: initializer element is not constant
 FILE *yyin = {stdin}, *yyout = {stdout};
               ^
lex.yy.c:20:15: note: (near initialization for ‘yyin’)
lex.yy.c:20:33: error: initializer element is not constant
 FILE *yyin = {stdin}, *yyout = {stdout};
                                 ^
lex.yy.c:20:33: note: (near initialization for ‘yyout’)
lex.yy.c:31:10: fatal error: symbol.h: No such file or directory
 #include "symbol.h"
          ^~~~~~~~~~
compilation terminated.
makefile:20: recipe for target lex.yy.o failed
make: *** [lex.yy.o] Error 1

作者好像没在/chap3这个目录下给出symbol.h文件，不过这些文件存放在/chap4目录下，在/chap4下执行

$ cp symbol.c symbol.h absyn.h absyn.c ../chap3
$ make clean
$ make

然后就可以获得y.output:

State 1 conflicts: 1 shift/reduce
......
State 1

   21 callExp: ID . LPAREN argList RPAREN
   33 recordExp: ID . LBRACE efieldList RBRACE
   44 arrayExp: ID . LBRACK exp RBRACK OF exp
   45 lvalue: ID .
   48       | ID . LBRACK exp RBRACK

    LPAREN  shift, and go to state 30
    LBRACK  shift, and go to state 31
    LBRACE  shift, and go to state 32

    LBRACK    [reduce using rule 45 (lvalue)]
    $default  reduce using rule 45 (lvalue)
......

这里我们有很多方法可以解决这种移进/规约冲突的问题。

在介绍方法之前，我们先来分析一下这个问题，这个语法分析器在ID这里exp遇到了两种可能性：

shift移进.
exp在这里可以被移进为ID [exp] OF exp

ID '[' exp ']' OF exp        --> exp    (rule 25)

reduce规约.
exp在这里是ID[exp],

ID                           --> lvalue (rule 34)
lvalue '[' exp ']'           --> lvalue (rule 36)
lvalue                       --> exp    (rule 2)

问题是语法分析器无法在看到OF单词之前，明确的作出判断该使用哪一个生成式。

这里的解决方案是避免语法分析器在此时作出判断：

1.因为表达式只能是ID [ exp ] OF，所以我们可以从冲突中提出公因子ID：

exp   : ID
      | lvalue_not_id
      | ...

lvalue: ID
      | lvalue_not_id

lvalue_not_ID
      : lvalue DOT ID
      | ID            LBRACK exp RBRACK
      | lvalue_not_ID LBRACK exp RBRACK

2.看到文法中存在一个移进/规约冲突在State1,这是因为我们使用Apple在书中提到的使用一个冗余的表达式来解决移进/规约冲突，但是这个表达式依然会引发一个移进规约冲突，实际上，它是一个与原始语法完全相同的shift-reduce冲突。但是这一次，冲突是在两个不同的制作之间进行的lvalue，默认的移进动作是我们想要的ID接受[。在转换之后，lvalue生产和exp仍然可用，因此解析器在]之前不必作出决定。这里的移进规约冲突实际上不会影响我们的语法的判断。
3.另一个解决方案就是使用bison的%glr-parser指令来生成GLR解析器。GLR算法能够通过有效地同时维护两个（或更多个）不同的可能解析器堆栈来延迟减少决策。对于明确的语法，在输入的长度上仍然是O（n），但它稍慢。（此外，此选项在许多其他yacc衍生产品中不可用。）

可以看到如果我们自己手写DFA那将是一项非常复杂的工作。然后套用我们自己的词法分析器看看是否成功，修改makefile的文件，将注释符号#去掉，将第二章完成的词法分析器复制到目录下：

~/chap2 $ cp tiger.lex token.h ../chap03
~/chap3 $ make clean
~/chap3 $ make

结果也是顺利生成了语法分析器。这里有个比较有意思的Bison选项是--graph，这个选项可以根据你的DFA生成图像，比较适合初学者理解

$ sudo apt-get install graphviz
$ bison --graph tiger.grm
$ dot tiger.dot -Tsvg -o tiger.svg

ps：这个过程常常由于内存不够而崩溃。我这里已经跑了30mins了还没有完成做图

添加error表达式

下面要求添加一个error表达式，并且举例证明可以完成错误修复。由于我们没有使用语义动作，所以我们可以不用考虑语义动作对错误恢复带来的影响。

错误恢复有两种方式，一种是局部恢复技术，第二种是全局恢复技术。全局恢复技术主要针对的是语义动作的影响，而且全局回复技术并不需要error产生式的辅助，所以这里我们使用局部错误恢复的方法来重新设计文法。这一节的内容可以在Bison文档第6节Error Recovery

修改文法的第一步是找到同步单词synchronizing token，然后再继续分析。
修改后的文法如下：

$$
\begin{align}
& program \rightarrow exp \\
& \\
& exp \rightarrow INT \\
& exp \rightarrow STRING \\
& exp \rightarrow LValue \\
& exp \rightarrow NIL \\
& exp \rightarrow exp \quad exps \\
& exp \rightarrow - INT \\
& exp \rightarrow - ID \\
& exp \rightarrow ( exp ) \\
& exp \rightarrow () \\
& exp \rightarrow Functioncall \\
& exp \rightarrow Arithmetic \\
& exp \rightarrow Comparison \\
& exp \rightarrow exp \quad AND \quad exp \\
& exp \rightarrow exp \quad OR \quad exp \\
& exp \rightarrow RecordCreation \\
& exp \rightarrow ArrayCreation \\
& exp \rightarrow LValue := exp \\
& exp \rightarrow IF \quad exp \quad THEN \quad exp \quad ELSE \quad exp
& exp \rightarrow error
\\
& exp \rightarrow IF \quad exp \quad THEN \quad exp \\
& exp \rightarrow WHILE \quad exp \quad DO \quad exp \\
& exp \rightarrow FOR \quad ID \quad ASSIGN \quad exp \quad TO \quad exp \quad DO \quad exp \\
& exp \rightarrow BREAK \\
& exp \rightarrow LET \quad DeclarationSequence \quad IN \quad exp \quad END \\
& \\
& exps \rightarrow ;exp \\
& exps \rightarrow exps;exp \\
& \\
& DeclarationSequence \rightarrow \varepsilon \\
& DeclarationSequence \rightarrow Declaration \\
& \\
& Declaration \rightarrow TypeDelarations \\
& Declaration \rightarrow VarDeclaration \\
& Declaration \rightarrow FunctionDeclatations \\
& \\
& TypeDelarations \rightarrow TypeDelaration \\
& TypeDelarations \rightarrow TypeDelarations \quad TypeDelaration \\
& \\
& FunctionDeclatations \rightarrow FunctionDeclatation \\
& FunctionDeclatations \rightarrow FunctionDeclatations \quad FunctionDeclatation \\
& \\
& TypeDelaration \rightarrow Type \quad ID = OtherType \\
& \\
& OtherType \rightarrow ID \\
& OtherType \rightarrow {TypeFields} \\
& OtherType \rightarrow ARRAY \quad OF \quad ID \\
& \\
& TypeFields \rightarrow \varepsilon \\
& TypeFields \rightarrow TypeKV \quad TypeKVList \\
& \\
& TypeKV \rightarrow ID:ID \\
& \\
& TypeKVList \rightarrow \varepsilon \\
& TypeKVLsit \rightarrow TypeKVList\quad ,TypeKV \\
& \\
& VarDeclaration \rightarrow Var \quad ID := exp \\
& VarDeclaration \rightarrow Var \quad ID ,ID :=exp \\
& FunctionDeclatation \rightarrow FUNCTION \quad ID (TypeFields) =exp \\
& FunctionDeclatation \rightarrow FUNCTION \quad ID (TypeFields):ID =exp \\
& \\
& LValue \rightarrow ID \quad LValue_extension \\
& \\
& LValue_extension \rightarrow \varepsilon \\
& LValue_extension \rightarrow .ID \quad LValue_extension \\
& LValue_extension \rightarrow [exp]LValue_extension \\
& \\
& Functioncall \rightarrow ID() \\
& Functioncall \rightarrow ID(expList) \\
& \\
& expList \rightarrow exp \\
& expList \rightarrow expList,exp \\
& \\
& Arithmetic \rightarrow exp + exp \\
& Arithmetic \rightarrow exp - exp \\
& Arithmetic \rightarrow exp \times exp \\
& Arithmetic \rightarrow exp / exp \\
& \\
& Comparison \rightarrow exp = exp \\
& Comparison \rightarrow exp \neq exp \\
& Comparison \rightarrow exp \leq exp \\
& Comparison \rightarrow exp \geq exp \\
& Comparison \rightarrow exp < exp \\
& Comparison \rightarrow e& program \rightarrow exp \\
& \\
& exp \rightarrow INT \\
& exp \rightarrow STRING \\
& exp \rightarrow LValue \\
& exp \rightarrow NIL \\
& exp \rightarrow exp \quad exps \\
& exp \rightarrow - INT \\
& exp \rightarrow - ID \\
& exp \rightarrow ( exp ) \\
& exp \rightarrow () \\
& exp \rightarrow Functioncall \\
& exp \rightarrow Arithmetic \\
& exp \rightarrow Comparison \\
& exp \rightarrow exp AND exp \\
& exp \rightarrow exp OR exp \\
& exp \rightarrow RecordCreation \\
& exp \rightarrow ArrayCreation \\
& exp \rightarrow LValue := exp \\
& exp \rightarrow IF exp THEN exp ELSE exp \\
& exp \rightarrow IF exp THEN exp \\
& exp \rightarrow WHILE exp DO exp \\
& exp \rightarrow FOR ID ASSIGN exp TO exp DO exp \\
& exp \rightarrow BREAK \\
& exp \rightarrow LET DeclarationSequence IN exp END \\
& \\
& exps \rightarrow ;exp \\
& exps \rightarrow exps;exp \\
& \\
& DeclarationSequence \rightarrow \varepsilon \\
& DeclarationSequence \rightarrow Declaration \\
& \\
& Declaration \rightarrow TypeDelarations \\
& Declaration \rightarrow VarDeclaration \\
& Declaration \rightarrow FunctionDeclatations \\
& \\
& TypeDelarations \rightarrow TypeDelaration \\
& TypeDelarations \rightarrow TypeDelarations TypeDelaration \\
& \\
& FunctionDeclatations \rightarrow FunctionDeclatation \\
& FunctionDeclatations \rightarrow FunctionDeclatations FunctionDeclatation \\
& \\
& TypeDelaration \rightarrow Type ID = OtherType \\
& \\
& OtherType \rightarrow ID \\
& OtherType \rightarrow {TypeFields} \\
& OtherType \rightarrow ARRAY OF ID \\
& \\
& TypeFields \rightarrow \varepsilon \\
& TypeFields \rightarrow TypeKV TypeKVList \\
& \\
& TypeKV \rightarrow ID:ID \\
& \\
& TypeKVList \rightarrow \varepsilon \\
& TypeKVLsit \rightarrow TypeKVList,TypeKV \\
& \\
& VarDeclaration \rightarrow Var ID := exp \\
& VarDeclaration \rightarrow Var ID ,ID :=exp \\
& FunctionDeclatation \rightarrow FUNCTION ID (TypeFields) =exp \\
& FunctionDeclatation \rightarrow FUNCTION ID (TypeFields):ID =exp \\
& \\
& LValue \rightarrow ID LValue_extension \\
& \\
& LValue_extension \rightarrow \varepsilon \\
& LValue_extension \rightarrow .ID LValue_extension \\
& LValue_extension \rightarrow [exp]LValue_extension \\
& \\
& Functioncall \rightarrow ID() \\
& Functioncall \rightarrow ID(expList) \\
& \\
& expList \rightarrow exp \\
& expList \rightarrow expList,exp \\
& \\
& Arithmetic \rightarrow exp + exp \\
& Arithmetic \rightarrow exp - exp \\
& Arithmetic \rightarrow exp \times exp \\
& Arithmetic \rightarrow exp / exp \\
& \\
& Comparison \rightarrow exp = exp \\
& Comparison \rightarrow exp \neq exp \\
& Comparison \rightarrow exp \leq exp \\
& Comparison \rightarrow exp \geq exp \\
& Comparison \rightarrow exp < exp \\
& Comparison \rightarrow exp > exp \\
& \\
& RecordCreation \rightarrow ID{} \\
& RecordCreation \rightarrow ID{FieldAssignmentList} \\
& \\
& FieldAssignmentList \rightarrow FieldAssignment \\
& FieldAssignmentList \rightarrow FieldAssignmentList,FieldAssignment \\
& \\
& FieldAssignment \rightarrow ID = exp \\
& \\
& ArrayCreation \rightarrow ID [exp] OF exp \\
xp > exp \\
& \\
& RecordCreation \rightarrow ID{} \\
& RecordCreation \rightarrow ID{FieldAssignmentList} \\
& \\
& FieldAssignmentList \rightarrow FieldAssignment \\
& FieldAssignmentList \rightarrow FieldAssignmentList,FieldAssignment \\
& \\
& FieldAssignment \rightarrow ID = exp \\
& \\
& ArrayCreation \rightarrow ID [exp] OF \quad exp \\
\end{align}
$$
error是在Bison中定义好的，所以我们不需要再次声明直接使用即可。