Yacc使用指南

YACC（BISON）使用指南YACC（YetAnotherCompile-Compiler）是语法分析器生成工具，它生成的是LALR分析器。Yacc于上世纪70年代产生，是美国贝尔实验室的产品，已经用于帮助实现了几百个编译器。Yacc是linux下的工具，本实验使用的编译工具是cygwin（cygwin在windows下模拟一个linux环境）下的bison，它与Yacc的使用方法基本相同，只有很少的差别。一．YACC的使用方法：1.用户按照Yacc规定的规则写出文法说明文件，该文件一般以.y为扩展名（有的系统以.grm为扩展名。）2.Yacc编译器将此文法说明文件（假设该文件为filename.y）转换成用C编写的语法分析器文件filename.tab.c（如果在编译时加上某些参数还可以生成头文件filename.tab.h）。这个文件里至少应该包含语法分析驱动程序yyparse()以及LALR分析表。在这个文件里，语法分析驱动程序调用yylex()这个函数获取输入记号，每次调用yylex()都能获取一个输入记号。yylex()可以由lex生成，也可以自己用c语言写一个yylex()函数，只要每次调用该函数时返回一个记号即可。3.用C编译器（本实验所给工具为cygwin下的gcc）将filename.tab.c编译为可执行文件（cygwin下默认为a.exe）。4.a.exe即为可执行的语法分析器。二．文法说明文件（即Yacc源程序）的写法：文法说明文件，顾名思义，就是将一个语言的文法说清楚。在Yacc中，这个说明文件可以分为三部分，以符号%%分开：[第一部分：定义段]%%第二部分：规则段[%%第三部分：辅助函数段]其中，第一部分及第三部分和第三部分之上的%%都可以省略（即上述方括号括起的部分可以省略）。以%开头的符号和关键字，或者是规则段的各个规则一般顶着行首来写，前面没有空格。1.第一部分定义段的写法：定义段可以分为两部分：第一部分以符号%{和%}包裹，里面为以C语法写的一些定义和声明：例如，文件包含，宏定义，全局变量定义，函数声明等。第二部分主要是对文法的终结符和非终结符做一些相关声明。这些声明主要有如下一些：%token，%left，%right，%nonassoc，%union，%type，%start。下面分别说明它们的用法。%token定义文法中使用了哪些终结符，定义形式为：%tokenTOKEN1TOKEN2TOKEN3….其中TOKEN1，TOKEN2等为终结符，终结符一般全大写。%left，%right，%nonassoc也是定义文法中使用的终结符，定义形式与%token类似，但是他们定义的终结符具有某种优先级和结合性，%left表示左结合，%right表示右结合，%nonassoc表示不可结合（即它定义的终结符不能连续出现：例如，如果文法中不允许出现形如abc的句子，则就是不可结合的）。而优先级关系则是以他们定义出现的顺序决定的，先定义的优先级低，最后定义的优先级最高，同时定义的优先级相同。例如，如果有如下定义：%leftAB%nonassocC%rightD则表示优先级关系为：A=BCD，而结合性关系为：A,B左结合，C不可结合，D右结合。%start指定文法的开始符号（非终结符），定义形式为：%startstartsym，其中startsym为文法的开始符号。如果不使用%start定义文法开始符号，则默认在第二部分规则段中定义的第一条产生式规则的左部非终结符为开始符号。%union和%type用来处理文法中各符号所带的属性。在词法分析的学习中，我们知道记号是由记号名和记号的属性值两部分组成的，文法中的终结符就是记号，他们有属性值，同样，非终结符也是可以有属性值的。Yacc维护一个栈来保存文法符号的“属性值”，这个栈与移进-归约分析中的文法符号栈是对应的：即，如果移进归约分析栈中某个位置存放文法符号X，则对应的Yacc“属性值”栈中就存放X的属性值。Yacc将这个属性值栈的栈内元素的类型定义为YYSTYPE（这是一个宏），默认状态下，YYSTYPE定义为int类型，你可以在文法说明文件第一部分定义段中重新定义YYSTYPE为其他类型，例如，用#defineYYSTYPEdouble将其定义为double类型。如果你想让属性值栈可以存放多种类型的属性值，例如整型和字符串型等（这在很多情况下是需要的，比如你希望标识符ID的属性是字符串而整型数NUM的属性是整型值），你最好将属性值栈元素的类型定义为一种union类型，此时，你可以用%union来定义它。例如，如下这样的定义会将Yacc属性值栈元素的类型定义为包含num和id两个域的联合体，其中num域的类型为int而id域的类型为char*。%union{intnum;char*id;}如果你在写文法说明文件时，需要用到一些终结符和非终结符的属性值，那么你可以先将这些属性值放入对应的属性值栈中，并在需要使用的时候从属性值栈中取出。不过，在你这么做之前，你首先需要定义这些终结符和非终结符的属性值的类型。对于终结符的类型，你可以这样定义：%tokennumTOKEN1%tokenidTOKEN2TOKEN3上述定义会将终结符TOKEN1定义为属性值栈num域所具有的类型（即int类型），而将TOKEN2和TOKEN3定义为id域所具有的类型（char*类型）。对于非终结符，可以这样用%type定义其属性值的类型，例如：%typeidsym1sym2%typenumsym3上述定义将非终结符sym1和sym2（非终结符一般用小写单词表示）定义为char*类型，而将sym3定义为int类型。2.第二部分规则段的写法：规则段实际上定义了文法的非终结符及产生式集合，以及当归约整个产生式时应执行的操作。假如产生式为exprexprplusterm|term，则在规则段应该写成：expr:exprPLUSterm{语义动作}|term{语义动作};其中，产生式左部的非终结符expr应写在冒号左边，冒号表示产生符号，产生式右部每个用|分隔的部分单独写一行并用|分隔，整组产生式写完后，结尾处应加分号;，分号表示同一左部的一组产生式结束。每一行产生式后面大括号括起的语义动作表示该条产生式归约时应该执行的操作，语义动作使用C语言的语法来写，他们将会被直接拷贝到yacc编译器生成的c语言源程序文件中。在语义动作中，可以引用存放在属性值栈中的文法符号的属性值，$$符号可引用产生式左部非终结符的属性值，而$i则可以引用产生式右部第i个文法符号的属性值，当然，前提是你必须为这些文法符号的属性定义了类型，而且在你使用这些属性值之前，已经将这些属性值放入了属性值栈对应的地方。例如：expr:exprPLUSterm{$$=$1+$3;}|term{$$=$1;};上述例子中，归约exprPLUSterm为expr时，将会做如下操作：从属性值栈中取出产生式右部expr的属性值（$1）和term的属性值（$3），将两者的和存入属性值栈中对应产生式左部的expr的属性值的位置（$$）。归约term为expr时，则将term的属性（$1）存入产生式左部expr的属性值（$$）中。注意，在这个例子中，PLUS是终结符，而expr和term都是非终结符（能出现在产生式左部的符号都已定义为非终结符）。由于用到了expr和term的属性值，因此必须先用%type对expr和term的属性值类型进行定义（除非属性值栈只能存放默认类型int的元素，并且expr和term的属性值类型都为int，这种情况下可以不必定义他们的属性值类型）。本例中$$=$1;这一语义动作实际上可以省略不写，因为将term归约为expr的过程在移进归约分析中实际上是将栈顶的term退栈，而将expr入栈，对应的属性值栈中的操作实际上是将term的属性值退栈，再将term的属性值作为expr的属性值入栈（因为term的属性值要赋给expr的属性值），最终的结果是term的属性值仍然留在属性值栈上原来的位置，只不过现在这个位置我们认为是expr的属性值。3.第三部分辅助函数段的写法：辅助函数段用C语言语法来写，辅助函数一般指在规则段中用到或者在语法分析器的其他部分用到的函数。这一部分一般会被直接拷贝到yacc编译器产生的c源文件中。一般来说，除规则段用到的函数外，辅助函数段一般包括如下一些例程：yylex()，yyerror()，main()。intyylex()是词法分析程序，它返回记号。语法分析驱动程序yyparse()将会调用yylex()获取记号。如果不使用lex生成这个函数，则必须在辅助函数段用C语言写这个程序。记号由记号名和属性值构成，记号名一般作为yylex的返回值（注意，记号名是由%token等定义的终结符名，这些终结符名在yacc内部会被宏定义成一些常数。），而属性值则由yacc内部定义的变量yylval来传递。yylval的类型与属性值栈元素的类型相同，即，默认状态下，yylval为int类型，若使用#defineYYSTYPEdouble将属性值栈元素定义为double类型，则yylval就是double类型，若用%union将属性值栈元素定义为联合类型，则yylval也是联合类型。注意，当yylval是联合类型时，对它的引用要注意。例如，若属性值栈定义为%union{intnum;char*id;}而yylex返回记号ID的属性值为”myid”（类型为char*）时，yylex在返回之前，应使用如下语句将属性值传递给语法分析器：yylval.id=“myid”;main是主程序，主程序的主要作用是调用yyparse()函数（至少应有一条调用yyparse()的语句）。intyyparse()是yacc生成的语法分析驱动函数，语法分析成功结束时，yyparse返回0，而发现错误时，则返回1，并且调用yyerror()函数输出错误信息。yyerror是错误报告例程。如果辅助函数部分不包含yyerror和main函数，也可以通过链接时将例程库中标准的yyerror和main链接进来，链接方法是在链接命令尾端加-ly参数。4.YACC中的注释：Yacc文法说明文件中，凡是可以使用C语法写的部分，都可以用C语言的注释/**/和//，其它部分的注释可以用/**/，但是注意，/*之前必须有先导空格，不能顶着行首来写。三．使用LEX定义词法分析器并把它和YACC写的语法分析器链接起来假设用yacc写的文法说明文件为filename.y，由于使用LEX生成yylex()，因此filename.y的辅助函数段不需要定义yylex()，只需在定义段加上函数声明intyylex();即可。用yacc编译器对filename.y进行编译，编译时带上参数-d，即在cygwin下使用如下命令：bison–dfilename.y此时编译器除生成filename.tab.c以外，还将生成名为filename.tab.h的头文件。该头文件中包含filename.y中定义的所有终结符的常量定义，属性值栈的类型定义，以及变量yylval的外部引用定义。假设用Lex写的词法分析规则文件为filename.l，则在filename.l的声明部分应包含头文件filename.tab.h，即，在filename.l声明部分应包含如下语句：#include“filename.tab.h”并且，filename.l文件中凡涉及返回记号名的部分，都返回filename.y中定义的终结符名；而用yylval返回记号属性值。用命令flexfilename.l编译filename.l得到lex.yy.c。lex.yy.c中包含了函数yylex()。用如下命令编译链接得到语法分析程序（其中方括号内的部分可省略）：gcc[–ooutfile]filename.tab.clex.yy.c[-lfl][-ly]-lfl是链接flex