第 5章本讲要点
YACC
5.5 Yacc：一个 LALR(1)分析程序的生成器
Yacc 代表 Yet Another Compiler Compiler。
由 S.C.Johnson等人在 AT&T贝尔实验室研制开发的，早期作为 UNIX操作系统中的一个实用程序，
现在 Yacc得到广泛使用。
Yacc有多个版本,Bison是它的一个常用版本。
L语言语法分析器
Yacc程序
Yacc的使用
Yacc 程序将任何一种编程语言的所有语法说明文件（,Y)翻译成针对此种语言的 Yacc 语法解析器。
L语言的 Yacc说明文件（,Y) L语言语法分析器输入串 语法树
Yacc的使用
1,采用命令
yacc [选择项 ] filename.y
生成 y.tab.c(或者 ytab.c)的文件。
2,在 C环境下将其编译成可执行文件。
一,Yacc说明文件的结构
Yacc说明文件基本格式如下：
{ definitions } 定义部分
%%
{ rules } 规则部分
%%
{auxiliary routines} 辅助程序部分
定义部分包括了 Yacc分析程序的有关记号、
数据类型以及文法规则的信息。
它还包括了必须直接进入输出文件的任何 C代码，
如 #include语句等 )，
注,定义部分可为空。
① 变量定义变量定义需用一对 %{和 %}包括起来，其内容包括有关文件的引用说明、数据结构的定义、全局和外部变量的定义等等，
应遵循 C语言的规定。例如,%{
#include <stdio.h>
…
int count;
extern double value;
…
int function(int a,float b);
…
%}
规则部分包括 BNF格式的文法规则以及在识别出相应文法规则时要执行的动作,
动作用 C代码表示，当用该规则去归约时执行与之对应的动作 )。
Yacc中文法规则使用的元符号约定,
竖线 |用作替换。
箭头符号 → 改成冒号：，
每个文法规则末以分号结束。
辅助程序部分包括了过程和函数声明 (可空！ )。
Yacc还允许将 C-风格的注解插入到输入文件中。
编写 yacc说明文件
Yacc识别记号的方法
1）文法规则的单引号中的任何字符都被识别为它本身。如运算符记号 ‘ +‘,‘ -‘和 ‘ *’ 。
2）在 %记号 (%token)中声明符号记号，如
%token NUMBER 。
编写 yacc说明文件
Yacc对记号的处理
Yacc为每个记号自动分配一个不与任何字符值冲突的数字值，通常从 258开始赋值。
yacc将这些定义作为 #define语句插入到输出代码中。
如,#define NUMBER 258
用户也可指定将赋给记号的数字。
例,%token NUMBER 18，就将给 NUMBER赋值 18。
例：简单整型算术表达式文法,
exp → exp addop term | term
addop→ + | -
term → term mulop factor | factor
mulop → *
factor → ( exp ) | number
的 yacc说明文件如下：
％ {
#include <stdio.h>
#include <ctype.h>
%}
%token NUMBER
%%
定义部分在输出文件开头直接加的代码声明记号
command,exp {printf(“%d\n”,$1);}; /* 打印结果 */
exp,exp?+? term { $$ = $1+$3; }
| exp?-? term { $$ = $1-$3; }
| term { $$ = $1; };
term,term?*? factor { $$ = $1*$3; }
| factor { $$ = $1; };
factor,NUMBER { $$ = $1; }
|?(? exp?)? { $$ = $2; };
规则部分注：第一条规则的左部为文法的开始符号。
也可以用 %start 文法符号 来指定文法的开始符号。
%start command
此处进行了文法的拓广。
$$代表刚识别出的非终结符的值，
(文法规则左边的符号值 )。
$1,$2,$3…
代表文法规则右边的第 1,2,3…
个符号值。
%%
main()
{ return yyparse(); }
int yylex(void)
{ int c;
while((c=getchar())==) ;
/* 删除空格 */
if ( isdigit(c) ) {
ungetc(c,stdin);
scanf(“%d”,&yylval);
return(NUMBER);
}
if (c ==?\n?) return 0;
/* 标识分析结束 */
return(c);
}
void yyerror(char *s)
{ fprintf(stderr,”%s”,s);
} /* 打印错误信息 */
辅助部分
Yacc假设记号的值被赋给了由 Yacc内部定义的变量 yylval，且在识别记号时必须给
yylval赋值。
由文法的一组产生式及每一产生式相应的语义动作组成。
对于文法中的每个产生式：
A→ α 1|α 2|… |α n
相应地写成：
A,α 1 {语义动作 1;}
| α 2 {语义动作 2;}
…
| α n {语义动作 n;};
2、规则部分
规则部分动作书写为 c代码
在书写动作时，可用 Yacc伪变量 (pseudo variable)。
当识别一个文法规则时，规则中的每个符号都有一个整型值。这些值保存在值栈 (value stack)中，可通过以 $开始的伪变量来引用。
例,exp,exp '+' term { $$=$1+$3; }
表示当识别规则 exp→ exp+term时，
将右边的 exp值与 term值之和赋值给左边的 exp。
赋值时机非终结符是由用户定义的动作赋值。
记号在扫描过程中赋值，如,NUMBER。
factor,NUMBER { $$ = $1; }
$1是 yylval的值，后者是当识别记号 NUMBER时被赋值的。
由例行 C语言程序（函数）组成，主要包括：
主程序 main()
词法分析程序 yylex()
出错处理程序 yyerror()
语法规则部分语义动作中所调用的用户自定义函数以及其他辅助函数等等。
这个部分也可为空。
3、辅助程序部分
主程序 main()的主要作用在于调用函数
yyparse()对源程序进行语法分析。
yyparse()分析成功返回 0；否则返回为 1，并调用 yyerror()函数输出出错信息。
函数 main()和 yyparse()可由 Yacc库提供
（只需在编译命令行中加入选择项 -ly即可）。
3、辅助程序部分在语法分析程序 yyparse()运行时，将调用词法分析程序 yylex()，从输入字符流中识别出一个单词，
并将该单词的内码及语义分别通过 return语句及全局变量 yylval回送给 yyparse()。
5.5.2 Yacc选项
Yacc的 -d选项将自动生成一个头文件 (y.tab.h
或 ytab.h)，供其它文件使用。
如,yacc –d calc.y将产生头文件 y.tab.h，其中包括：
#ifndef YYSTYPE
#define YYSTYPE int
#endif
#define NUMBER 258
extern YYSTYPE yylval;
该文件可通过 #include y.tab.h来使用。
－ d
5.5.2 Yacc选项
Yacc的 -v选项 (verbose option)将产生名为
y.output的输出文件，其中包括分析程序使用的 LALR(1)分析表的文本描述。
这个文件将使用户可以判断出 Yacc生成的分析程序将要采取的动作，这是处理文法中的二义性和不准确性的有效方法。
一般，在向说明添加动作或辅助过程之前，将
Yacc与这个选项一起在文法上运行，以确保
Yacc生成的分析程序将确实正确执行。
－ v
5.5 Yacc：一个 LALR(1)分析程序的生成器
例如，程序清单 5-2中的 Yacc说明。它是程序清单 5-1
中 Yacc说明的简化：
yacc –v calc.y
程序清单 5-2 使用 -v选项的 Yacc说明提纲
%token NUMBER
%%
command,exp;
exp,exp?+‘ term
| exp?-‘ term
| term;
term,term?*‘ tactor
| factor;
factor,NUMBER
|?(‘ exp?)‘;
5.5 Yacc：一个 LALR(1)分析程序的生成器
程序清单 5-3是该文法完整的典型 y.output文件。
其中列出了 DFA中的所有状态，还有统计情况。
状态由 0开始编号。
在每个状态下,Yacc列出了核心项目、不同先行对应的分析动作、每个非终结符的 goto动作等内容。
Yacc使用下划线 _来表示 LR(0)项目中的分隔位置
(.)。
句点 (.)表示缺省先行记号。
5.5 Yacc：一个 LALR(1)分析程序的生成器
state 0
$accept:_command $end
NUMBER shift 5
'(' shift 6
,error
command goto 1
exp goto 2
term goto 3
factor goto 4
5.5 Yacc：一个 LALR(1)分析程序的生成器
State 1
$accept,command_$end
$end accept
,error
5.5 Yacc：一个 LALR(1)分析程序的生成器
状态 0包含核心项目 $accept,_command $end。
新的非终结符为 $accept。 $end表示输入结束。
状态 0的动作包括：
NUMBER shift 5
( shift 6
,error
command goto 1
exp goto 2
term goto 3
factor goto 4
5.5 Yacc：一个 LALR(1)分析程序的生成器
在先行记号 NUMBER,(时移进到状态 5,6中，
其他记号则错误。在非终结符时有 4个 goto转换。
再看状态 2，输出列表为：
state 2
command,exp_ (1)
exp,exp_+term
exp,exp_-term
+ shift 7
- shift 8
,reduce 1
5.5 Yacc：一个 LALR(1)分析程序的生成器
这里，核心项目是完整项目，需要归约动作。
Yacc在完整项目后有产生式编号。此时，编号为 1，要用产生式 command→ exp归约。
Yacc按说明顺序为产生式编号。例中有 8个产生式。
Yacc与纯 LALR(1)分析的不同在于它并不检查归约时的合法先行，而是在若干个归约中进行选择。上例中除了 +和－要执行移进动作外其它任何符号处都进行归约。
Yacc会在声明错误前作出多个归约。这样，分析表会十分简单。
5.5 Yacc：一个 LALR(1)分析程序的生成器表 5-11与程序清单 5-3的 Yacc输出对应的分析表状态输入 Goto
number （ ＋ — ＊ ） $ commandexp term factor
0 s5 s6 1 2 3 4
1 accept
2 r1 r1 s7 s8 r1 r1 r1
3 r4 r4 r4 r4 s9 r4 r4
4 r6 r6 r6 r6 r6 r6 r6
5 r7 r7 r7 r7 r7 r7 r7
6 s5 s6 10 3 4
7 s5 s6 11 4
8 s5 s6 12 4
9 s5 s6 13
10 s7 s8 s14
11 r2 r2 r2 r2 s9 r2 r2
12 r3 r3 r3 r3 s9 r3 r3
13 r5 r5 r5 r5 r5 r5 r5
14 r8 r8 r8 r8 r8 r8 r8
5.5.3 分析冲突与消除二义性的规则
Yacc使用了简单的消除二义性的规则，即使在发生分析冲突时，也能产生一个分析程序。
在 y.output中会报告分析冲突。用户可检查是否存在分析冲突，以及 Yacc产生的分析程序是否正确。
上例的输出报告为：
0 shift/reduce,0 reduce/reduce conflicts
reported
没有产生分析冲突。
考虑例 5.12中的悬挂 else文法。
Yacc会报告二义性，并消除二义性。 Yacc将状态 5的报告如下：
5,shift/reduce conflict(shift 6,redn 3) on ELSE
state 5
I,IF S_ (3)
I,IF S_ ELSE S
ELSE shift 6
,reduce 3
Yacc还会有小结报告：
1 shift/reduce,0 reduce/reduce conflicts reported
5.5.3 分析冲突与消除二义性的规则
5.5 Yacc：一个 LALR(1)分析程序的生成器
出现归约 -归约冲突时,Yacc只取前面的一个归约，从而消除了二义性。
例 5.18考虑以下的文法：
S→ A|B
A→ a
B→ a
因串 a有两个推导,S?A?a和 S?B?a，故是二义性文法。
5.5 Yacc：一个 LALR(1)分析程序的生成器
y.output文件见 P182程序清单 5-4 。
状态 4有归约 -归约冲突,
State 4
A,a_ (3)
B,a _(4)
,Reduce 3
只使用前一个规则 A→ a归约。 Yacc还报告：
Rule not reduced,B,a。
5.5 Yacc：一个 LALR(1)分析程序的生成器
Yacc可指定算符的优先级及结合性，无需为此而修改文法，可使文法更简单。
相应的分析表也可小一些，分析程序更有效。
程序清单 5-5中的 Yacc说明中的文法是没有定义算符的优先权和结合性，具有二义性。
5.5 Yacc：一个 LALR(1)分析程序的生成器
在 Yacc中，算符的优先权和结合性可在定义部分中写出来：
%left?+‘?-‘
%left?*‘
说明算符 +,-,*具左结合性，且后者具更高的优先权 (顺序决定 )。
在 Yacc中,%right和 %nonassoc说明右结合性和不能结合性。
程序清单 5-5是一个简单计算器的 Yacc说明，
该文法有二义性，优先权及结合性在定义部分说明。
5.5 Yacc：一个 LALR(1)分析程序的生成器程序清单 5-5
%{
#include <stdio.h>
#include <ctype.h>
%}
%token NUMBER
%left?+‘?-‘
%left?*‘
%%
command,exp { printf(―%d\n‖,$1); };
exp,NUMBER { $$=$1; }
| exp?+‘ exp { $$=$1+$3; }
| exp?-‘ exp { $$=$1-$3; }
| exp?*‘ exp { $$=$1*$3; }
|?(? exp?)‘ { $$=$2; };
5.5.4 描述 Yacc分析程序的执行
Yacc生成的分析程序能打印出分析过程，包括分析栈的情况、分析程序动作等。
这需要将符号常量 YYDEBUG和变量 yydebug都设置为 1。
方法：将以下两行加到定义部分：
#define YYDEBUG 1
extern int yydebug;
再在 main中加入一行 yydebug=1。
5.5 Yacc：一个 LALR(1)分析程序的生成器程序清单 5-6 输入 2+3Starting parse
Entering state 0Input,2+3
Reading a token,Next token is 258 (NUMBER)Shifting token 258 (NUMBER),Entering state 1
Reducing 1 value via rule 7 (line 18),state stack now 0Entering state 5
Reducing 1 value via rule 6 (line 16),state stack now 0Entering state 4
Reading a token,Next token is 43 ('+')Reducing 1 value via rule 4 (line 13),state stack now 0
Entering state 3Next token is 43 ('+')
Shifting token 43 ('+'),Entering state 7Reading a token,Next token is 258 (NUMBER)
Shifting token 258 (NUMBER),Entering state 1Reducing 1 value via rule 7 (line 18),state stack now 0 3 7
Entering state 5Reducing 1 value via rule 6 (line 16),state stack now 0 3 7
Entering state 11Reading a token,Now at end of input.
Reducing 3 values via rule 2 (line 11),state stack now 0Entering state 3
Now at end of input.Reducing 1 value via rule 1 (line 9),5
state stack now 0Entering state 14
Now at end of input.Shifting token 0 ((null)),Entering state 15
Now at end of input.
5.5 Yacc：一个 LALR(1)分析程序的生成器
5.5.5 Yacc中的任意值类型
Yacc伪变量的缺省类型是整型。
可对 Yacc伪变量的值类型进行重定义。这个数据类型由 C预处理器符号 YYSTYPE定义。
若需要浮点型的伪变量，可定义：
#define YYSTYPE double
有时，不同的非终结符可能需要不同类型的值。
例如，以下规则：
exp→ exp addop term | term
addop→ + | -
5.5 Yacc：一个 LALR(1)分析程序的生成器
这里,addop返回算符 (一个 char)，但 exp返回计算的值 (一个 double)，可将 YYSTYPE定义为
double与 char的联合。
方法一：在 Yacc中用 %union声明：
%union { double val;
char op; }
再用 %type指定每个非终结符的返回值的类型：
%type <val> exp term factor
%type <op> addop mulop
5.5 Yacc：一个 LALR(1)分析程序的生成器
将程序清单 5-1的 Yacc说明改成：
...%token NUMBER
%union { double val;char op; }
%type <val> exp term factor NUMBER%type <op> addop mulop
%%comand,exp{ printf("%d\n",$1); };exp,exp op term { switch($2) {
case'+?,$$=$1+$3; break;case'-?,$$=$1-$3; break;
}}
| term { $$=$1; };
op,'+? { $$='+'; }| '-? { $$='-'; };
5.5 Yacc：一个 LALR(1)分析程序的生成器
方法二：在一个包含 (头 )文件中定义一个数据类型，再将 YYSTYPE
定义为这个类型。最后在相关的动作代码中构造出恰当的值。
5.5.6 Yacc中嵌入的动作
在分析时，有时需要在完整地识别一个文法规则之前先执行某个代码。例如文法：
decl→ type var-list
type→ int | float
var-list→ var-list,id | id
5.5 Yacc：一个 LALR(1)分析程序的生成器
当识别 var-list时，要将当前类型 (整型和浮点 )
加到每个变量。在 Yacc中可表示成：
decl,type { current_type=$1; }
var_list;
type,INT { $$=INT_TYPE; }
| FLOAT { $$=FLOAT_TYPE; };
var_list,var_list?;‘ ID
{ setType(tokenString,current_type); }
| ID
{ setType(tokenString,current_type); };
在 decl规则中有一个嵌入动作用于设置
current_type的值。
5.5 Yacc：一个 LALR(1)分析程序的生成器
嵌入动作形如：
A,B {/*嵌入动作 */} C ;
Yacc认为嵌入动作与一个新的非终结符和用它的 ε—产生式进行归约等价：
A,B E C ;
E,{ /*嵌入动作 */ };
表 5-12对 Yacc的定义和内部名称进行了小结。
5.5 Yacc：一个 LALR(1)分析程序的生成器
表 5-12Yacc内置名称和定义机制
Yacc的内置名称 含义／用处
y.tab.c Yacc输出文件名称
y.tab.h Yacc生成的头文件，包含了记号定义
yyparse Yacc分析例程
yylval 栈中当前记号的值
yyerror 由 Yacc使用的用户定义的错误信息打印机
error Yacc错误伪记号
yyerrok 在错误之后重置分析程序的过程
yychar 包括导致错误的先行记号
YYSTYPE 定义分析栈的值类型的预处理器符号
yydebug 变量，当由用户设置为 1时则导致生成有关分析动作的运行信息
Yacc的定义机制 含义／用处
%token 定义记号预处理器符号
%start 定义开始非终结符符号
%union 定义和 YYSTYPE，允许分析程序栈上的不同类型的值
%type 定义由一个符号返回的和类型
%left %right %nonassoc 定义算符的结合性和优先权 (由位置 )
YACC
5.5 Yacc：一个 LALR(1)分析程序的生成器
Yacc 代表 Yet Another Compiler Compiler。
由 S.C.Johnson等人在 AT&T贝尔实验室研制开发的，早期作为 UNIX操作系统中的一个实用程序，
现在 Yacc得到广泛使用。
Yacc有多个版本,Bison是它的一个常用版本。
L语言语法分析器
Yacc程序
Yacc的使用
Yacc 程序将任何一种编程语言的所有语法说明文件（,Y)翻译成针对此种语言的 Yacc 语法解析器。
L语言的 Yacc说明文件（,Y) L语言语法分析器输入串 语法树
Yacc的使用
1,采用命令
yacc [选择项 ] filename.y
生成 y.tab.c(或者 ytab.c)的文件。
2,在 C环境下将其编译成可执行文件。
一,Yacc说明文件的结构
Yacc说明文件基本格式如下：
{ definitions } 定义部分
%%
{ rules } 规则部分
%%
{auxiliary routines} 辅助程序部分
定义部分包括了 Yacc分析程序的有关记号、
数据类型以及文法规则的信息。
它还包括了必须直接进入输出文件的任何 C代码，
如 #include语句等 )，
注,定义部分可为空。
① 变量定义变量定义需用一对 %{和 %}包括起来，其内容包括有关文件的引用说明、数据结构的定义、全局和外部变量的定义等等，
应遵循 C语言的规定。例如,%{
#include <stdio.h>
…
int count;
extern double value;
…
int function(int a,float b);
…
%}
规则部分包括 BNF格式的文法规则以及在识别出相应文法规则时要执行的动作,
动作用 C代码表示，当用该规则去归约时执行与之对应的动作 )。
Yacc中文法规则使用的元符号约定,
竖线 |用作替换。
箭头符号 → 改成冒号：，
每个文法规则末以分号结束。
辅助程序部分包括了过程和函数声明 (可空！ )。
Yacc还允许将 C-风格的注解插入到输入文件中。
编写 yacc说明文件
Yacc识别记号的方法
1）文法规则的单引号中的任何字符都被识别为它本身。如运算符记号 ‘ +‘,‘ -‘和 ‘ *’ 。
2）在 %记号 (%token)中声明符号记号，如
%token NUMBER 。
编写 yacc说明文件
Yacc对记号的处理
Yacc为每个记号自动分配一个不与任何字符值冲突的数字值，通常从 258开始赋值。
yacc将这些定义作为 #define语句插入到输出代码中。
如,#define NUMBER 258
用户也可指定将赋给记号的数字。
例,%token NUMBER 18，就将给 NUMBER赋值 18。
例：简单整型算术表达式文法,
exp → exp addop term | term
addop→ + | -
term → term mulop factor | factor
mulop → *
factor → ( exp ) | number
的 yacc说明文件如下：
％ {
#include <stdio.h>
#include <ctype.h>
%}
%token NUMBER
%%
定义部分在输出文件开头直接加的代码声明记号
command,exp {printf(“%d\n”,$1);}; /* 打印结果 */
exp,exp?+? term { $$ = $1+$3; }
| exp?-? term { $$ = $1-$3; }
| term { $$ = $1; };
term,term?*? factor { $$ = $1*$3; }
| factor { $$ = $1; };
factor,NUMBER { $$ = $1; }
|?(? exp?)? { $$ = $2; };
规则部分注：第一条规则的左部为文法的开始符号。
也可以用 %start 文法符号 来指定文法的开始符号。
%start command
此处进行了文法的拓广。
$$代表刚识别出的非终结符的值，
(文法规则左边的符号值 )。
$1,$2,$3…
代表文法规则右边的第 1,2,3…
个符号值。
%%
main()
{ return yyparse(); }
int yylex(void)
{ int c;
while((c=getchar())==) ;
/* 删除空格 */
if ( isdigit(c) ) {
ungetc(c,stdin);
scanf(“%d”,&yylval);
return(NUMBER);
}
if (c ==?\n?) return 0;
/* 标识分析结束 */
return(c);
}
void yyerror(char *s)
{ fprintf(stderr,”%s”,s);
} /* 打印错误信息 */
辅助部分
Yacc假设记号的值被赋给了由 Yacc内部定义的变量 yylval，且在识别记号时必须给
yylval赋值。
由文法的一组产生式及每一产生式相应的语义动作组成。
对于文法中的每个产生式：
A→ α 1|α 2|… |α n
相应地写成：
A,α 1 {语义动作 1;}
| α 2 {语义动作 2;}
…
| α n {语义动作 n;};
2、规则部分
规则部分动作书写为 c代码
在书写动作时，可用 Yacc伪变量 (pseudo variable)。
当识别一个文法规则时，规则中的每个符号都有一个整型值。这些值保存在值栈 (value stack)中，可通过以 $开始的伪变量来引用。
例,exp,exp '+' term { $$=$1+$3; }
表示当识别规则 exp→ exp+term时，
将右边的 exp值与 term值之和赋值给左边的 exp。
赋值时机非终结符是由用户定义的动作赋值。
记号在扫描过程中赋值，如,NUMBER。
factor,NUMBER { $$ = $1; }
$1是 yylval的值，后者是当识别记号 NUMBER时被赋值的。
由例行 C语言程序（函数）组成，主要包括：
主程序 main()
词法分析程序 yylex()
出错处理程序 yyerror()
语法规则部分语义动作中所调用的用户自定义函数以及其他辅助函数等等。
这个部分也可为空。
3、辅助程序部分
主程序 main()的主要作用在于调用函数
yyparse()对源程序进行语法分析。
yyparse()分析成功返回 0；否则返回为 1，并调用 yyerror()函数输出出错信息。
函数 main()和 yyparse()可由 Yacc库提供
（只需在编译命令行中加入选择项 -ly即可）。
3、辅助程序部分在语法分析程序 yyparse()运行时，将调用词法分析程序 yylex()，从输入字符流中识别出一个单词，
并将该单词的内码及语义分别通过 return语句及全局变量 yylval回送给 yyparse()。
5.5.2 Yacc选项
Yacc的 -d选项将自动生成一个头文件 (y.tab.h
或 ytab.h)，供其它文件使用。
如,yacc –d calc.y将产生头文件 y.tab.h，其中包括：
#ifndef YYSTYPE
#define YYSTYPE int
#endif
#define NUMBER 258
extern YYSTYPE yylval;
该文件可通过 #include y.tab.h来使用。
－ d
5.5.2 Yacc选项
Yacc的 -v选项 (verbose option)将产生名为
y.output的输出文件，其中包括分析程序使用的 LALR(1)分析表的文本描述。
这个文件将使用户可以判断出 Yacc生成的分析程序将要采取的动作，这是处理文法中的二义性和不准确性的有效方法。
一般，在向说明添加动作或辅助过程之前，将
Yacc与这个选项一起在文法上运行，以确保
Yacc生成的分析程序将确实正确执行。
－ v
5.5 Yacc：一个 LALR(1)分析程序的生成器
例如，程序清单 5-2中的 Yacc说明。它是程序清单 5-1
中 Yacc说明的简化：
yacc –v calc.y
程序清单 5-2 使用 -v选项的 Yacc说明提纲
%token NUMBER
%%
command,exp;
exp,exp?+‘ term
| exp?-‘ term
| term;
term,term?*‘ tactor
| factor;
factor,NUMBER
|?(‘ exp?)‘;
5.5 Yacc：一个 LALR(1)分析程序的生成器
程序清单 5-3是该文法完整的典型 y.output文件。
其中列出了 DFA中的所有状态，还有统计情况。
状态由 0开始编号。
在每个状态下,Yacc列出了核心项目、不同先行对应的分析动作、每个非终结符的 goto动作等内容。
Yacc使用下划线 _来表示 LR(0)项目中的分隔位置
(.)。
句点 (.)表示缺省先行记号。
5.5 Yacc：一个 LALR(1)分析程序的生成器
state 0
$accept:_command $end
NUMBER shift 5
'(' shift 6
,error
command goto 1
exp goto 2
term goto 3
factor goto 4
5.5 Yacc：一个 LALR(1)分析程序的生成器
State 1
$accept,command_$end
$end accept
,error
5.5 Yacc：一个 LALR(1)分析程序的生成器
状态 0包含核心项目 $accept,_command $end。
新的非终结符为 $accept。 $end表示输入结束。
状态 0的动作包括：
NUMBER shift 5
( shift 6
,error
command goto 1
exp goto 2
term goto 3
factor goto 4
5.5 Yacc：一个 LALR(1)分析程序的生成器
在先行记号 NUMBER,(时移进到状态 5,6中，
其他记号则错误。在非终结符时有 4个 goto转换。
再看状态 2，输出列表为：
state 2
command,exp_ (1)
exp,exp_+term
exp,exp_-term
+ shift 7
- shift 8
,reduce 1
5.5 Yacc：一个 LALR(1)分析程序的生成器
这里，核心项目是完整项目，需要归约动作。
Yacc在完整项目后有产生式编号。此时，编号为 1，要用产生式 command→ exp归约。
Yacc按说明顺序为产生式编号。例中有 8个产生式。
Yacc与纯 LALR(1)分析的不同在于它并不检查归约时的合法先行，而是在若干个归约中进行选择。上例中除了 +和－要执行移进动作外其它任何符号处都进行归约。
Yacc会在声明错误前作出多个归约。这样，分析表会十分简单。
5.5 Yacc：一个 LALR(1)分析程序的生成器表 5-11与程序清单 5-3的 Yacc输出对应的分析表状态输入 Goto
number （ ＋ — ＊ ） $ commandexp term factor
0 s5 s6 1 2 3 4
1 accept
2 r1 r1 s7 s8 r1 r1 r1
3 r4 r4 r4 r4 s9 r4 r4
4 r6 r6 r6 r6 r6 r6 r6
5 r7 r7 r7 r7 r7 r7 r7
6 s5 s6 10 3 4
7 s5 s6 11 4
8 s5 s6 12 4
9 s5 s6 13
10 s7 s8 s14
11 r2 r2 r2 r2 s9 r2 r2
12 r3 r3 r3 r3 s9 r3 r3
13 r5 r5 r5 r5 r5 r5 r5
14 r8 r8 r8 r8 r8 r8 r8
5.5.3 分析冲突与消除二义性的规则
Yacc使用了简单的消除二义性的规则，即使在发生分析冲突时，也能产生一个分析程序。
在 y.output中会报告分析冲突。用户可检查是否存在分析冲突，以及 Yacc产生的分析程序是否正确。
上例的输出报告为：
0 shift/reduce,0 reduce/reduce conflicts
reported
没有产生分析冲突。
考虑例 5.12中的悬挂 else文法。
Yacc会报告二义性，并消除二义性。 Yacc将状态 5的报告如下：
5,shift/reduce conflict(shift 6,redn 3) on ELSE
state 5
I,IF S_ (3)
I,IF S_ ELSE S
ELSE shift 6
,reduce 3
Yacc还会有小结报告：
1 shift/reduce,0 reduce/reduce conflicts reported
5.5.3 分析冲突与消除二义性的规则
5.5 Yacc：一个 LALR(1)分析程序的生成器
出现归约 -归约冲突时,Yacc只取前面的一个归约，从而消除了二义性。
例 5.18考虑以下的文法：
S→ A|B
A→ a
B→ a
因串 a有两个推导,S?A?a和 S?B?a，故是二义性文法。
5.5 Yacc：一个 LALR(1)分析程序的生成器
y.output文件见 P182程序清单 5-4 。
状态 4有归约 -归约冲突,
State 4
A,a_ (3)
B,a _(4)
,Reduce 3
只使用前一个规则 A→ a归约。 Yacc还报告：
Rule not reduced,B,a。
5.5 Yacc：一个 LALR(1)分析程序的生成器
Yacc可指定算符的优先级及结合性，无需为此而修改文法，可使文法更简单。
相应的分析表也可小一些，分析程序更有效。
程序清单 5-5中的 Yacc说明中的文法是没有定义算符的优先权和结合性，具有二义性。
5.5 Yacc：一个 LALR(1)分析程序的生成器
在 Yacc中，算符的优先权和结合性可在定义部分中写出来：
%left?+‘?-‘
%left?*‘
说明算符 +,-,*具左结合性，且后者具更高的优先权 (顺序决定 )。
在 Yacc中,%right和 %nonassoc说明右结合性和不能结合性。
程序清单 5-5是一个简单计算器的 Yacc说明，
该文法有二义性，优先权及结合性在定义部分说明。
5.5 Yacc：一个 LALR(1)分析程序的生成器程序清单 5-5
%{
#include <stdio.h>
#include <ctype.h>
%}
%token NUMBER
%left?+‘?-‘
%left?*‘
%%
command,exp { printf(―%d\n‖,$1); };
exp,NUMBER { $$=$1; }
| exp?+‘ exp { $$=$1+$3; }
| exp?-‘ exp { $$=$1-$3; }
| exp?*‘ exp { $$=$1*$3; }
|?(? exp?)‘ { $$=$2; };
5.5.4 描述 Yacc分析程序的执行
Yacc生成的分析程序能打印出分析过程，包括分析栈的情况、分析程序动作等。
这需要将符号常量 YYDEBUG和变量 yydebug都设置为 1。
方法：将以下两行加到定义部分：
#define YYDEBUG 1
extern int yydebug;
再在 main中加入一行 yydebug=1。
5.5 Yacc：一个 LALR(1)分析程序的生成器程序清单 5-6 输入 2+3Starting parse
Entering state 0Input,2+3
Reading a token,Next token is 258 (NUMBER)Shifting token 258 (NUMBER),Entering state 1
Reducing 1 value via rule 7 (line 18),state stack now 0Entering state 5
Reducing 1 value via rule 6 (line 16),state stack now 0Entering state 4
Reading a token,Next token is 43 ('+')Reducing 1 value via rule 4 (line 13),state stack now 0
Entering state 3Next token is 43 ('+')
Shifting token 43 ('+'),Entering state 7Reading a token,Next token is 258 (NUMBER)
Shifting token 258 (NUMBER),Entering state 1Reducing 1 value via rule 7 (line 18),state stack now 0 3 7
Entering state 5Reducing 1 value via rule 6 (line 16),state stack now 0 3 7
Entering state 11Reading a token,Now at end of input.
Reducing 3 values via rule 2 (line 11),state stack now 0Entering state 3
Now at end of input.Reducing 1 value via rule 1 (line 9),5
state stack now 0Entering state 14
Now at end of input.Shifting token 0 ((null)),Entering state 15
Now at end of input.
5.5 Yacc：一个 LALR(1)分析程序的生成器
5.5.5 Yacc中的任意值类型
Yacc伪变量的缺省类型是整型。
可对 Yacc伪变量的值类型进行重定义。这个数据类型由 C预处理器符号 YYSTYPE定义。
若需要浮点型的伪变量，可定义：
#define YYSTYPE double
有时，不同的非终结符可能需要不同类型的值。
例如，以下规则：
exp→ exp addop term | term
addop→ + | -
5.5 Yacc：一个 LALR(1)分析程序的生成器
这里,addop返回算符 (一个 char)，但 exp返回计算的值 (一个 double)，可将 YYSTYPE定义为
double与 char的联合。
方法一：在 Yacc中用 %union声明：
%union { double val;
char op; }
再用 %type指定每个非终结符的返回值的类型：
%type <val> exp term factor
%type <op> addop mulop
5.5 Yacc：一个 LALR(1)分析程序的生成器
将程序清单 5-1的 Yacc说明改成：
...%token NUMBER
%union { double val;char op; }
%type <val> exp term factor NUMBER%type <op> addop mulop
%%comand,exp{ printf("%d\n",$1); };exp,exp op term { switch($2) {
case'+?,$$=$1+$3; break;case'-?,$$=$1-$3; break;
}}
| term { $$=$1; };
op,'+? { $$='+'; }| '-? { $$='-'; };
5.5 Yacc：一个 LALR(1)分析程序的生成器
方法二：在一个包含 (头 )文件中定义一个数据类型，再将 YYSTYPE
定义为这个类型。最后在相关的动作代码中构造出恰当的值。
5.5.6 Yacc中嵌入的动作
在分析时，有时需要在完整地识别一个文法规则之前先执行某个代码。例如文法：
decl→ type var-list
type→ int | float
var-list→ var-list,id | id
5.5 Yacc：一个 LALR(1)分析程序的生成器
当识别 var-list时，要将当前类型 (整型和浮点 )
加到每个变量。在 Yacc中可表示成：
decl,type { current_type=$1; }
var_list;
type,INT { $$=INT_TYPE; }
| FLOAT { $$=FLOAT_TYPE; };
var_list,var_list?;‘ ID
{ setType(tokenString,current_type); }
| ID
{ setType(tokenString,current_type); };
在 decl规则中有一个嵌入动作用于设置
current_type的值。
5.5 Yacc：一个 LALR(1)分析程序的生成器
嵌入动作形如：
A,B {/*嵌入动作 */} C ;
Yacc认为嵌入动作与一个新的非终结符和用它的 ε—产生式进行归约等价：
A,B E C ;
E,{ /*嵌入动作 */ };
表 5-12对 Yacc的定义和内部名称进行了小结。
5.5 Yacc：一个 LALR(1)分析程序的生成器
表 5-12Yacc内置名称和定义机制
Yacc的内置名称 含义／用处
y.tab.c Yacc输出文件名称
y.tab.h Yacc生成的头文件，包含了记号定义
yyparse Yacc分析例程
yylval 栈中当前记号的值
yyerror 由 Yacc使用的用户定义的错误信息打印机
error Yacc错误伪记号
yyerrok 在错误之后重置分析程序的过程
yychar 包括导致错误的先行记号
YYSTYPE 定义分析栈的值类型的预处理器符号
yydebug 变量，当由用户设置为 1时则导致生成有关分析动作的运行信息
Yacc的定义机制 含义／用处
%token 定义记号预处理器符号
%start 定义开始非终结符符号
%union 定义和 YYSTYPE，允许分析程序栈上的不同类型的值
%type 定义由一个符号返回的和类型
%left %right %nonassoc 定义算符的结合性和优先权 (由位置 )
