yacc语法笔记

这篇笔记是从网上下载的文档中摘录的，简明扼要，对yacc新手会有一点帮助。

1.yacc源程序的一般格式

一个yacc源程序一般包括三部分：说明部分；语法规则部分；程序段部分，这三部分内容，依次按下面的格式组织在一起：

说明部分

％％

语法规则部分

％％

程序段部分

2. yacc源程序说明部分的写法

yacc源程序的说明部分定义语法规则中要用的终结符号，语义动作中使用的数据类型、变量、语义值的联合类型以及语法规则中运算符的优先级等。这些内容的组织方式如下：

％｛

头文件表

宏定义

数据类型定义

全局变量定义

％｝

语法开始符定义

语义值类型定义

终结符定义

运算符优先级及结合性定义

2.1.1头文件表

yacc直接把这部分定义抄到所生成的C语言程序y.tab.c中去的，所以要按C语言的语法规定来写。头文件表是一系列C语言的＃include 语句，要从每行的第一列开始写。

2.1.2宏定义

这部分用C语言的 ＃define语句定义程序中要用的宏。

2.1.3数据类型定义

这部分定义语义动作中或程序段部分中要用到的数据类型，例如：

％｛

typedefstruct interval｛

doublelo，hi；

｝INTERVAL；

％｝

2.1.4全局变量定义

外部变量（external variable）和yacc源程序中要用到的全局变量都在这部分定义，例如：

％{

externint nfg;

doubledreg[ 26]；

INTERVALVreg[26]；

％｝

另外非整型函数的类型声明也包含在这部分中。

上述四部分括在 ％{和％}之间的内容是由yacc原样照抄到y.tab.c中去，所以必

须完全符合C语言文法。

2.2.1语法开始符定义

上下文无关文法的开始符号是一个特殊的非终结符，所有的推导都从这个非终结符开始，

在yacc中，语法开始符定义语句是：

%start 非终结符

如果没有上面的说明，yacc自动将语法规则部分中第一条语法规则左部的非终结符作为语

法开始符。

2.2.2语义值类型定义

如果没有对语义值的类型做定义，那么yacc认为它是整型（int）的。因为不同的语法符号的语义值类型可能不同，所以语义值类型说明就是将语义值的类型定义为一个联合（union），这个联合包括所有可能用到的类型。同时，在语义值类型定义部分还要求用户说明每一个语法符号（终结符和非终结符）的语义值是哪一个联合成员类型。

例：

％union｛

intival

doubledval

INTERVALvval;

｝

％token ＜ival＞DREGVREG

％token ＜dval＞CONST

％type  ＜dval＞dexp

％type  ＜vval＞vexp

在上述定义中，以％union开始的行定义了语义值的联合类型，共有三个成员类型分别取名为ival,dval, vval。

以％token开始的行定义的是终结符，所以DREG,VREG和CONST都是终结符，尖括号中的名字就是这些终结符的语义值的具体类型。如DREG和VREG这两个终结符的语义值将是整型（int）的，成员名是ival。

以％type开始的行是说明非终结符语义值的类型。如非终结符dexp的语义值将是双精度

浮点类型，请注意，在yacc中非终结符不必特别声明，但是当说明部分有对语义值类型的定义，而且某非终结符的语义值将被存取，就必须用上面的方法定义它的类型。

2.2.3终结符定义

在yacc源程序语法规则部分出现的所有终结符（文字字符literal 除外）必须在这部分定义，定义方法如下例：

％token DIGIT LETTER

每个终结符定义行以％token开头，注意％与token之间没有空格，一行中可以定义多个终结符，它们之间用空格分开，终结符名可以由字母，数字，下划线组成，但必须用字母开头。非终结符名的组成规则与此相同。终结符定义行可多于一个。

在2.2.2中说过如果用户定义了语义值的类型，那么那些具有有意义的语义值的终结符，其义值的类型要用union中的成员名来说明，除了在2.2.2中介绍的定义方法外，还可以把对终结符的定义和其语义值的类型说明分开，例如：

%tokenDREG VREG CONST

％type ＜ival＞DREG VREG

％type ＜dval＞CONST

2.2.4算符优先级及结合性定义

yacc允许用户规定运算符的优先级和结合性，这样就可以消除上述文法的二义性。

在说明部分中以％left 开头的行就是定义算符的结合性的行。％left 表示其后的算符是遵循左结合的；％right表示右结合性，而％nonassoc则表示其后的算符没有结合性。优先级是隐含的，在说明部分中，排在前面行的算符较后面行的算符的优先级低；排在同一行的算符优先级相同。

当一元运算符和二元运算符发生冲突时（如负号和减号），使用%prec子句说明它所在的语法规则中最右边的运算符或终结符的优先级与％prec后面的符号的优先级相同，注意％

prec子句必须出现在某语法规则结尾处分号之前。

例：

expr；expr'+' expr

|expr'-’expr

|expr'*'expr

|expr'／’ expr

|'-'expr％prec'*'

|NAME

;

3.yacc源程序中语法规则部分的写法

语法规则部分是yacc源程序的核心部分，这一部分定义了要处理的语言的语法及要采用的语义动作。下面介绍语法规则的书写格式、语义动作的写法以及yacc解决二义性和冲突的具体措施。最后介绍错误处理。

3.1语法规则的书写格式

每条语法规则包括一个左部和一个右部，左右部之间用冒号‘:’来分隔，规则结尾处要用分号“;”标记。

3.2语义动作

当语法分析程序识别出某个句型时，它即用相应的语法规则进行归约，yacc在进行归约之

前，先完成用户提供的语义动作。终结符的语义值是通过词法分析程序返回的，这个值由全局变量（yacc自动定义的）yylval带回。如果用户在词法分析程序识别出某终结符时给yylval赋与相应的值，那么这个值就自动地作为该终结符的语义值。当语义值的类型不是int 时，要注意yylval的值的类型须与相应的终结符的语义值类型一致。

3.3yacc解决二义性和冲突的方法

Yacc提供了下面两条消除二义性的规则：

A1．出现移进／归约冲突时，进行移进；

A2. 出现归约／归约冲突时，按照产生式在yacc源程序中出现的次序，用先出现的产生式归约。

Yacc如何利用优先级和结合性来解决冲突的？

Yacc源程序中的产生式也有一个优先级和结合性。这个优先级和结合性就是该产生式右部

最后一个终结符或文字字符的优先级和结合性，当使用了％prec子句时，该产生式的优先级和结合性由％prec子句决定。当然如果产生式右部最后一个终结符或文字字符没有优先级或结合性，则该产生式也没有优先级或结合性。

根据终结符（或文字字符）和产生式的优先级和结合性，Yacc又有两个解决冲突的规则：

P1. 当出现移进/归约冲突或归约／归约冲突，而当时输入符号和语法规则（产生式）均没有优先级和结合性，就用AI和A2来解决这些冲突。

P2．当出现移进／归约冲突时，如果输入符号和语法规则（产生式）都有优先级和结合性，那么如果输入符号的优先级大于产生式的优先级就移进如果输入符号的优先级小于产生式的优先级就归约。如果二者优先级相等，则由结合性决定动作，左结合则归约，右结合则移进，无结合性则出错。

3.4 语法分析中的错误处理

yacc处理错误的方法是：当发现语法错误时，yacc丢掉那些导致错误的符号适当调整状态

栈。然后从出错处的后一个符号处或跳过若干符号直到遇到用户指定的某个符号时开始继续分析。

Yacc内部有一个保留的终结符error。把它写在某个产生式的右部，则Yacc就认为这个地

方可能发生错误，当语法分析的确在这里发生错误时，Yacc就用上面介绍的方法处理，如果没有用到error的产生式，则Yacc打印出“parse error”，就终止语法分析。

例：

1．下面的产生式

stat: error

;

使yacc在分析stat推导出的句型时，遇到语法错误时跳过出错的部分，继续分析（也会打

印语法错信息）

2．下面的产生式

stat: error ';'

;

使yacc碰到语法错时，跳过输入串直到碰到下一个分号才继续开始语法分析。

4. 程序段部分

程序段部分主要包括以下内容：主程序main（）；错误信息执行程序yyerror（s）；词法分析程序yylex（）；用户在语义动作中用到的子程序。

4.1主程序

主程序的主要作用是调用语法分析程序yyparse（），yyparse（）是yacc 从用户写的yacc

源程序自动生成的，在调用语法分析程序yyparse（）之前或之后用户往往需要做一些其他处理，这些也在main（）中完成，如果用户只需要在main()中调用yyparse（），则也可以使用Unix的yacc库（-ly）中提供的main（）而不必自己写。库里的main（）如下：

main（） ｛

return（yyparse（））；

｝

4.2 错误信息报告程序

 yacc的库也提供了一个错误信息报告程序，其源程序如下:

＃include <stodio. h＞

yyerror (char * s）{

fprintf (stderr, “%s\n”,s);

｝

如果用户觉得这个yyerror（s）太简单。也可以自己提供一个，如在其中记住输入串的行号并当yyerror（s）被调用时，可以报告出错行号。

4.3 词法分析程序

词法分析程序必须由用户提供，其名字必须是yylex，调法分析程序向语法分析程序提供当

前输入的单词符号。yylex提供给yyparse的不是终结符本身，而是终结符的编号，即token

number，如果当前的终结符有语义值，yylex必须把它赋给yylval。

用户也可以用Lex为工具编写记号词法分析程序，如果这样，在yacc源程序的程序段部分

就只需要用下面的语句来代替词法分析程序：

#include "lex.yy.c"

如果在命令中使用选择项-v，例如：

yacc －v plo.y

则yacc除产生y.tab.c外，还产生一个名叫y.output的文件，其内容是被处理语言的LR状态转换表。

4.4其他程序段

语义动作部分可能需要使用一些子程序，这些子程序都必须遵守C语言的语法规定。