Redy语法分析--YACC简介

返回文档首页

（1）yacc简介

YACC的全名为Yet Another Compiler-Compiler ，是LALR(1)分析器的自动生成工具，它的第一版于20世纪70年代初发表，是美国贝尔实验实的产品，作者为S.C.Johnson

使 用YACC构造语法分析程序非常方便，它要求用户按一定的规则编写出“文法处理说明文件”，简称YSP（Yacc Specification）文件，文件的扩展名为".y"，当输入YSP文件时，YACC会自动构造出相应的C语言形式的语法分析器。该分析器主要包括 由YACC提供的标准总控制程序和一个LALR（1）分析表。

（2）YSP文件结构

一个完整的YSP文件由说明，规则，程序三个部分组成各部分之间由双百分号隔开：

[说明部分]
%%
规则部分
[%%
程序部分
]

其中用方括号括起来的说明部分和程序部分可以空缺，但是规则部份是必须的。因此YSP文件最简章的形式是

%%
规则部分

（3）YSP说明部分的组成

YSP文件的说明部分用于定义规则部分所使用的变量及语法符号，它可以包含以下几类信息：

1. 变量定义

变量的定义需要用一对持殊括号 "%{"和 "%}括起来，其内容包括规则部份中语义动作及程序部分所需使用的有关文件（如C语言的有关头文件）的引用及说明、数据结构的定义，全局和外部变量的定义以及函数原型的定义等等，这部分内部，应该遵守C语言的规定

2. 开始符号定义

文法的开始符号由说明符号%start 指明（Yacc中所有的说明符号均由"%"引出），例如：

%start  StartSymbol

指明的StartSymbol为文法的开始符号，若未给出开始符号的定义，则系统将自动以第一个语法规则的左部符号作为开始符号

3. 词汇表定义

在这部分，用户可以给出终结符号表，联合(uniion)和类型（type）说明，YACC要求所用到的所有终结符号都应明确的加以说明；对于未说明者，则均按非终结符号处理，终结符号说明由说明符号%token 或%term 引出，其书写格式有两种，第一种书写格式为

%token Tname [Tname2 ...]

各个终结符号之间用空格分隔。在一行写不下时，可以%token 别起一行继续定义。第二种书写格式允许用户自行定义终结符号的内部编码值，其格式为

%token Tname

其 中，应为大于256的整数，当用户未给定终结符号的内部编码时，系统将按终结符号的出现顺序，从257开始，依次为其定义 内部码值：257,257,...。YACC内部约定，当词法分析程序从输入字符串中识别出一个终结符号时，将返回该终节符号的内部编码值。还需指出，除 文主字型的终结符号外，对于程序设计语言中的单字符运算符、分隔符等终结符号，可在文法中用单引号括起来直接使用，不必使用%token定义，其内部码值 就是它的ASCII码（其值不将不会大于256，这也是用户自定义的终结符号内部码之值不能小于257的原困

在 词汇表定义中，还可以通过使用联合(%union)和类型说明（%type），对每个文法符号定义其语义属性应具有的数据类型。例如，假定非终结符号A具 有属性Attr_a，其值为整型；非终结符号B具有两个属性b1各b2，其中b1为整数，b2为浮点数；则可以通过联合说明告诉Yacc，文法符号具有两 种类型：

%union
{
    int attr_a;
    struct
    {
        int b1;
        float b2;
   }attr_b;
}

然后再用%type说明非终结节符号A和B所具有的类型：

%type <attr_a> A
%type <attr_b> B

其 中尖括号<>中的名字是联合定义中的成员，一般来说若使用了联合定义，则须使用类型说明（%type）对每个文法符号的数据类型进行定义（每 个文法符号有且仅有一个符号类型），否则YACC将会报错。使用上述方式，允许在一行中定义多个文法符号，只需用空格将其隔开即可，若在一行写不下时，则 需别起一行后重新用%type命定继续定义。若在说明部分未用联合进行说明，则YACC自动使用缺省类型，Yacc约定，每一个文法符号的缺省类型为整 型。

（4）YSP文件程序部分的组成

YSP 文件的和序部分是可选的，它由例行C语言程序（函数）组成，主要包括主程序main()，词法分析程序yylex（），出错处理子程序 yyerror()，语法规则部份语义动作中所调用的用户自定义函数以及其它辅助函数等等。下面对它们的格式，功能和用法作用概括地说明。

（1）YACC 在处理YSP文件之后，将输入一个名为y.tab.c的C程序文件，此文件含有名为yyparser()的语法分析程序。主程序main（）的主要作用， 在于调用函数yyparser（）对源程序进行语法分析。当语法分析成功结束时，yyparser（）返回值为0，而在发现源程序有语法错语的，除返加值 为1外，它还调用yyerror（）函数输出出错信息。函数main（）和yerror（）可由yacc库提供（只需在编译命令中加入选择项-ly即 可）。如果用户认为上述函数的功能不满足要求，例如还需要在主程序中做其它的辅助处理，或需要yyerror输出更详细的出错信息，也可以自行编写这个函 数。

（2）YACC 系统规定，在语法分析程序yyparser（）运行时，需要一个名为yylex（）的词法分析程序对其支持，每当yyparse（）调用yylex（） 时，yylex（）就从输入字符流中识别出一个单词，并将该单词的内部码及其语义值（若有的话）分别通过return语句及全局变量yylval回送给 yyparser（），可见yyparser（）的输入来源于yylex（）的返回信息。

（5）YACC的安装

在linux平台，yacc的GUN版本为bison

ubuntu用户可以用下面命令来安装：

sudo apt-get install bison

返回文档首页