3--CH04--语法分析-YACC

Yacc: 另一个编译器的编译器Stephen C. JohnsonBell LaboratoriesMurray Hill, New Jersey 07974翻译：寒蝉退士译者声明：译者对译文不做任何担保，译者对译文不拥有任何权利并且不负担任何责任和义务。

原文：/7thEdMan/vol2/yacc.bun摘要计算机程序的输入通常有某种结构；实际上，可以认为每个需要输入的计算机程序都定义了一门它所接受的“输入语言”。

输入语言可以像编程语言那么复杂，或者像一序列的数那么简单。

不幸的是，通常的输入设施是有限的、难于使用的，并经常疏于检查它们的输入的有效性。

Yacc 提供了一个通用工具来描述计算机程序的输入。

Yacc 用户规定它的输入的结构，连同在识别每个这种结构的时候调用的代码。

Yacc 把这样的规定转换成操作输入处理的一个子例程；用这个子例程处理用户应用中的多数控制流经常是方便和适当的。

Yacc 生成的输入子例程调用用户提供的一个例程来返回下一个基本输入项目(item)。

所以，用户可以以单个的输入字符的方式，或以更高层构造如名字和数的方式来规定它的输入。

通过用户提供的例程还可以处理惯用的特征如注释和(行)接续约定，这些东西典型的违反容易的文法规定。

Yacc 是用可移植的 C 语言写成的。

接受的规定类别是非常一般性的: 带有去歧义规则的 LALR(1) 文法。

除了用于 C、APL、Pascal、RATFOR 等编译器之外，Yacc 还用于非常规语言，包括一个照相排版机语言、一些桌面计算器语言、一个文档检索系统、和一个Fortran 调试系统。

July 31,1978目录0: 介绍∙1: 基本规定∙2: 动作∙3: 词法分析∙4: 解析器如何工作∙5: 歧义和冲突∙6: 优先级∙7: 错误处理∙8: Yacc 环境∙9: 对准备规定的提示o输入样式o左递归o词法搭配o保留字∙10: 高级主题o在动作中模拟错误和接受o访问外围规则中的值o支持任意的值类型∙11: 致谢∙引用∙附录 A: 简单的例子∙附录 B: Yacc 输入语法∙附录 C: 高级的例子∙附录 D: 支持但不鼓励的旧特征0: 介绍Yacc 提供了一个通用工具来在计算机程序的输入上施加结构。

yacc(Yet Another Compiler Compiler)，是一个经典的生成语法分析器的工具。

是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）。

yacc生成的编译器主要是用C语言写成的语法解析器（Parser），需要与词法解析器Lex一起使用，再把两部份产生出来的C程序一并编译。

yacc本来只在Unix系统上才有，但现时已普遍移植往Windows 及其他平台。

分析程序生成器(parser generator)是一个指定某个格式中的一种语言的语法作为它的输入，并为该种语言产生分析过程以作为它的输出的程序。

在历史上，分析程序生成器被称作编译-编译程序( compiler- compiler )，这是由于按照规律可将所有的编译步骤作为包含在分析程序中的动作来执行。

现在的观点是将分析程序仅考虑为编译处理的一个部分，所以这个术语也就有些过时了。

合并 LALR(1) 分析算法是一种常用的分析生成器，它被称作 Yacc( yet another compiler- compiler )。

给出 Yacc 的概貌来，将使用Yacc为 TINY 语言开发一个分析程序。

作为 Yacc 对说明文件中的 %token NUMBER 声明的对应。

Yacc 坚持定义所有的符号记号本身，而不是从别的地方引入一个定义。

但是却有可能通过在记号声明中的记号名之后书写一个值来指定将赋给记号的数字值。

yacc的输入是巴科斯范式（BNF）表达的语法规则以及语法规约的处理代码，Yacc输出的是基于表驱动的编译器，包含输入的语法规约的处理代码部分。

yacc是开发编译器的一个有用的工具,采用LALR(1)语法分析方法。

Yacc最初由AT&T的Steven C. Johnson为Unix操作系统开发，后来一些兼容的程序如Berkeley Yacc，GNU bison，MKS yacc和Abraxas yacc陆续出现。

使用Yacc生成语法分析程序1、创建空工程File菜单下选择New：弹出下面对话框：选择Win32 Console Application，同时在Project Name下输入工程名字：ParserByYacc点击Ok按钮，弹出下面对话框：不做任何选择，按照默认“An empty project”，直接点击Finish按钮，弹出下面对话框：直接点击OK按钮，工程创建完毕。

2、使用Yacc生成语法分析程序点击“开始”，在“开始”菜单中选择“运行”，如下图所示在弹出的对话框中敲入cmd，启动DOS窗口使用DOS命令切换到E:\ ParserByYacc将yacc.exe文件拷贝到ParserByYacc工程下：将编写好的TINY.Y文件拷贝到ParserByYacc工程下：运行yacc生成y.tab.c和y.tab.h文件：3、添加文件首先在windows环境下，把设计好的文件GLOBALS.H、MAIN.C、SCAN.C、SCAN.H、PARSE.H、UTIL.C 和UTIL.H拷贝到ParserByYacc工程下：如图所示，选中Project菜单，选择下面Add To Project子菜单下面的Files子菜单：点击后弹出对话框：选中的刚拷贝进来的文件和Yacc生成的文件，点击OK按钮：在左侧的工程文件列表中，可以清楚地看到这些文件：4、生成可执行文件编译生成可执行文件ParserByYacc.exe在本工程的debug目录下：为了验证本语法分析程序的运行结果，把样本程序SAMPLE.TNY拷贝到可执行程序所在的目录下：5、验证运行结果Windows环境下点击“开始”，选中其中的“运行(R)”弹出下面对话框，输入cmd命令：输入上图所示的类似命令，进入可执行程序所在目录。

在当前目录下输入命令：ParserByYacc sample.tny，然后回车，则得到相应的运行结果：。

yacc语法Yacc是一个Unix系统上的自动语法分析工具，它被广泛用于编译器的实现以及其他与语法分析相关的任务。

使用Yacc可以通过自定义语法规则、自动生成语法分析代码，从而减轻开发者的工作量。

本文将围绕Yacc语法展开讲解。

1. 定义语法规则Yacc语法的最基本的元素就是语法规则。

语法规则可以由终结符(nonterminals)和非终结符(terminals)组成。

具体来说，终结符就是由程序中定义的特定单词组成，而非终结符则是一个标识符，它表示一个语法符号的集合。

在Yacc中，语法规则通常被写成这样：`[nonterminal] : options {actions}`其中，`nonterminal`表示非终结符，`options`表示由终结符和非终结符组成的可选项，`actions`则表示在匹配到语法规则时所要执行的动作。

2. 处理符号在Yacc语法中，为了辨别终结符和非终结符，我们使用符号。

符号可以区分终结符和非终结符，并且它们可以用在语法规则和实际输入中。

在Yacc语法中，我们使用`%token`和`%type`命令来声明符号。

具体来说，`%token`命令用于声明终结符，例如：`%token PLUS`而`%type`命令则用于声明非终结符，例如：`%type <ast_node> expression`在这个例子中，我们使用`<ast_node>`指定非终结符的类型。

3. 定义树状结构在Yacc语法中，我们通常需要定义树状结构来帮助我们分析输入。

在Yacc语法中，树状结构被称为抽象语法树(Abstract Syntax Tree, AST)。

为了定义抽象语法树，我们需要使用`$$`符号，它表示正式生成的语法树的节点。

例如，在下面的语法规则中，我们使用`$$`来表示生成的AST节点：```statement : type identifier EQUALS expression { $$ =parse_statement($1, $2, $4); }```在这个例子中，我们通过调用`parse_statement()`函数来生成AST节点。

⽤于消除语法分析冲突的yacc⽂法变换模式⽤于消除语法分析冲突的YACC⽂法变换模式摘要：YACC是Unix/Linux上⼀个⽤来⽣成编译器的编译器（编译器代码⽣成器）。

YACC⽣成的编译器主要是⽤C语⾔写成的语法解析器（Parser），需要与词法解析器Lex⼀起使⽤，再把两部份产⽣出来的C程序⼀并编译。

YACC本来只在Unix系统上才有，但现时已普遍移植往Windows及其他平台。

本⽂分析了使⽤LAI R(1)分析程序⽣成系统YACC时经常遇到的语法分析冲突问题及消除语法。

分析冲突的策略，总结了⼀组⽂法变换模式，利⽤这些模式可以有效地解决语法分析冲突阉题。

关键词： YACC 语法分析冲突⽂法变换模式引⾔YACC(Yet Another Compiler Compiler)是美国贝尔实验室著名的编译程序⽣成系统，⽤于开发以字符流输⼊的，语法制导的软件，如计算机语⾔的编(翻)译程序、解释程序、程序理解和⽩盒测试⼯具、语法制导的编辑器等近年来许多利⽤YACC的开发⼯作均指出了消除语法分析冲突的困难性，如开发C／C++程序理解⼯具的前端_2 J、Fortran95⾄C++的翻译程序、测试及测试控制标记语⾔TTCN-3的语法分析程序L4 J、硬件描述语⾔VHDL的分析程序等．本⽂借鉴软件设计模式的研究⽅法，总结出7个⽤于消除语法分析冲突的⽂法变换模式．下⾯介绍⽂中⽤到的⼏个基本概念和有关约定．⼀、概念和约定在本⽂中，术语“YACC”代表采⽤u也R(1)分析⽅法的⼀⼤类语法分析程序⽣成系统，包括贝尔实验室的YACC[“、⾃由软件基⾦会(GNU)的BiSo⼀6 J 及它们的所有变体，⼄虬R(1)分析⽅法属于移进归约分析⽅法．所谓移进，是指分析栈中移⼈新的终结符号归约是指⽤⼀条产⽣式的左部符号替换若⼲个栈顶符号，出栈符号的数⽬取决于产⽣式右部的长度．⽂法的LALR(1)分析表记录了当分析器的状态为s，当前⾯临的输⼊符号为t时应该执⾏的分析动作如果分析表的⼀个⼈⼝中记录了两个不同的分析动作，则称该⽂法包含⼀个语法分析突．分析冲突有两种：移进⼀归约冲突和归约⼀归约冲突，⼀个⽂法是LALR(1)⽂法，当且仅当它的LAI R(1)分析表中不含语法分析冲突．“UR(1)⽂法属于⽆歧义的上下⽂⽆关⽂法⼦类．若⼀个⽂法是歧义的。

数据库的yacc解析全文共四篇示例，供读者参考第一篇示例：数据库的Yacc解析Yacc（Yet Another Compiler Compiler）是一个生成解析器的工具，用来根据用户定义的文法来生成解析器。

在数据库领域，Yacc也被广泛应用于解析SQL语句，将用户输入的SQL语句转换为内部数据结构以便数据库系统进行解析和执行。

数据库中的Yacc解析主要包括词法分析和语法分析两个阶段。

词法分析阶段负责将输入的字符串分解成单词（token），然后传递给语法分析器进行处理。

语法分析阶段根据事先定义的文法规则，将单词序列转换为语法树或语法图，以表示语句的结构和含义。

在数据库系统中，SQL是最常见的数据库查询语言，因此Yacc解析器通常用于解析SQL语句。

SQL语句通常由多个部分组成，包括SELECT子句、FROM子句、WHERE子句等，每个子句又包含多个关键字和表达式。

Yacc解析器的任务就是将输入的SQL语句转换为相应的语法树，以便数据库系统能够对其进行解释和执行。

Yacc解析器生成的语法树通常包含多个节点，每个节点代表一个语法结构或操作符。

通过遍历语法树，数据库系统可以逐层解析SQL 语句，并执行对应的数据库操作。

对于一个SELECT语句，语法树的根节点可能表示SELECT操作，而子节点则表示SELECT子句中的列名、表名、条件等。

数据库的Yacc解析在实际应用中扮演着至关重要的角色。

通过Yacc解析器，数据库系统能够高效地解析用户输入的SQL语句，确保其语法正确性，并将其转换为可执行的数据操作。

Yacc解析器还能够支持SQL语句的扩展和变种，为数据库系统提供更多的灵活性和功能。

为了实现一个高效的数据库Yacc解析器，需要设计一个合理的文法规则，并结合合适的语法分析技术。

常见的语法分析技术包括LL(k)分析、LR(k)分析、LL(1)分析、LR(1)分析等，每种技术都有其适用的场景和优缺点。

在实际应用中，需要根据具体的需求和场景选择适合的语法分析技术，以实现高效和准确的语法解析。

⽤Yacc实现语法分析器-4-编译原理⽤Yacc实现语法分析器⼀、实验⽬的掌握语法分析器的构造原理，掌握Yacc的编程⽅法。

⼆、实验内容⽤Yacc编写⼀个语法分析程序，使之与词法分析器结合，能够根据语⾔的上下⽂⽆关⽂法，识别输⼊的单词序列是否⽂法的句⼦。

program→blockblock→ { stmts }stmts→　stmt stmts | estmt→ id= expr ;| if ( bool ) stmt| if ( bool) stmt else stmt| while (bool) stmt| do stmt while (bool ) ;| break ;| blockbool →expr < expr| expr <= expr| expr > expr| expr >= expr| exprexpr→expr + term| expr - term| termterm→term * factor| term / factor| factorfactor→ ( expr ) | id| num　三、实验步骤及结果实验环境：unix实验结果：按归约的先后顺序显⽰每次归约时所使⽤的产⽣式。

部分代码：⽤于产⽣flex输⼊的代码View CodeTest.l:[a-zA-Z_][a-zA-Z_0-9]* {return ID;}[0-9]+\.[0-9]+ {return REAL;}[0-9]+ {return NUM;}"||" {return OR;}"&&" {return AND;}"|" {return'|';}"&" {return'&';}"<=" {return LE;}"<" { return'<';}">=" {return GE;}">" {return'>';}"!=" {return NE;}"=" { return'=';}"==" {return EQ;}"\+" {return'+';}"\-" {return'-';}"\*" {return'*';}"\/" {return'/';}"(" {return'(';}")" {return')';}";" {return';';}"{" {return'{';}"}" {return'}';}"[" {return'['; }"]" {return']';}Test.y:rel : expr '<' expr { printf("rel-->expr<expr\n"); }| expr LE expr { printf("rel-->expr<=expr\n"); }| expr GE expr { printf("rel-->expr>=expr\n"); }| expr '>' expr { printf("rel-->expr>expr\n"); }| expr { printf("rel-->expr\n"); };expr : expr '+' term { printf("expr-->expr+term\n"); }| expr '-' term { printf("expr-->expr-term\n"); }| term { printf("expr-->term\n"); };term : term '*' unary { printf("term-->term*unary\n"); }| term '/' unary { printf("term-->term/unary\n"); }| unary { printf("term-->unary\n"); };unary : '!' unary { printf("unary-->!unary\n"); }| '-' unary %prec UMINUS{ printf("unary-->-unary\n"); } | factor { printf("unary-->factor\n"); };factor : '('bool')' { printf("factor-->(bool)\n"); }| loc { printf("factor-->loc\n"); }| NUM { printf("factor-->num\n"); }| REAL { printf("factor-->real\n"); }| TRUE { printf("factor-->true\n"); }| FALSE { printf("factor-->false\n"); }Flex⽣成代码:View CodeTest.l:[a-zA-Z_][a-zA-Z_0-9]* {return ID;}[0-9]+\.[0-9]+ {return REAL;}[0-9]+ {return NUM;}"||" {return OR;}"&&" {return AND;}"|" {return'|';}"&" {return'&';}"<=" {return LE;}"<" { return'<';}">=" {return GE;}">" {return'>';}"!=" {return NE;}"=" { return'=';}"==" {return EQ;}"\+" {return'+';}"\-" {return'-';}"\*" {return'*';}"\/" {return'/';}"(" {return'(';}")" {return')';}";" {return';';}"{" {return'{';}"}" {return'}';}"[" {return'['; }"]" {return']';}Test.y:rel : expr '<' expr { printf("rel-->expr<expr\n"); } | expr LE expr { printf("rel-->expr<=expr\n"); }| expr GE expr { printf("rel-->expr>=expr\n"); } | expr '>' expr { printf("rel-->expr>expr\n"); }| expr { printf("rel-->expr\n"); };expr : expr '+' term { printf("expr-->expr+term\n"); } | expr '-' term { printf("expr-->expr-term\n"); }| term { printf("expr-->term\n"); };term : term '*' unary { printf("term-->term*unary\n"); }| term '/' unary { printf("term-->term/unary\n"); }| unary { printf("term-->unary\n"); };unary : '!' unary { printf("unary-->!unary\n"); }| '-' unary %prec UMINUS{ printf("unary-->-unary\n"); }| factor { printf("unary-->factor\n"); };factor : '('bool')' { printf("factor-->(bool)\n"); }| loc { printf("factor-->loc\n"); }| NUM { printf("factor-->num\n"); }| REAL { printf("factor-->real\n"); }| TRUE { printf("factor-->true\n"); }| FALSE { printf("factor-->false\n"); }Yacc⽣成部分代码：View Code#line 1334 "y.tab.c"yyvsp -= yylen;yyssp -= yylen;YY_STACK_PRINT (yyss, yyssp);*++yyvsp = yyval;/* Now `shift' the result of the reduction. Determine what statethat goes to, based on the state we popped back to and the rulenumber reduced by. */yyn = yyr1[yyn];yystate = yypgoto[yyn - YYNTOKENS] + *yyssp;if (0 <= yystate && yystate <= YYLAST && yycheck[yystate] == *yyssp) yystate = yytable[yystate];elseyystate = yydefgoto[yyn - YYNTOKENS];goto yynewstate;/*------------------------------------.| yyerrlab -- here on detecting error |`------------------------------------*/yyerrlab:/* If not already recovering from an error, report this error. */if (!yyerrstatus){++yynerrs;#if YYERROR_VERBOSEyyn = yypact[yystate];if (YYPACT_NINF < yyn && yyn < YYLAST){YYSIZE_T yysize = 0;int yytype = YYTRANSLATE (yychar);const char* yyprefix;char *yymsg;int yyx;/* Start YYX at -YYN if negative to avoid negative indexes inYYCHECK. */int yyxbegin = yyn < 0 ? -yyn : 0;/* Stay within bounds of both yycheck and yytname. */int yychecklim = YYLAST - yyn;int yyxend = yychecklim < YYNTOKENS ? yychecklim : YYNTOKENS;int yycount = 0;yyprefix = ", expecting ";for (yyx = yyxbegin; yyx < yyxend; ++yyx)if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR){yysize += yystrlen (yyprefix) + yystrlen (yytname [yyx]);yycount += 1;if (yycount == 5){yysize = 0;break;}}yysize += (sizeof ("syntax error, unexpected ")+ yystrlen (yytname[yytype]));yymsg = (char *) YYSTACK_ALLOC (yysize);if (yymsg != 0){char *yyp = yystpcpy (yymsg, "syntax error, unexpected ");yyp = yystpcpy (yyp, yytname[yytype]);if (yycount < 5){yyprefix = ", expecting ";for (yyx = yyxbegin; yyx < yyxend; ++yyx)if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR){yyp = yystpcpy (yyp, yyprefix);yyp = yystpcpy (yyp, yytname[yyx]);yyprefix = " or ";}}yyerror (yymsg);YYSTACK_FREE (yymsg);}elseyyerror ("syntax error; also virtual memory exhausted");}else例如，程序⽚断{i = 2;while (i <=100){sum = sum + i;i = i + 2;}}（注：原本是在windwos环境下编程，最后到unix环境下，发现速度快了，灵活性⾼了，同时⽅便了很多。

实验4 用Yacc工具构造语法分析器一、实验目的掌握移进-归约技术语法分析技术，利用语法分析器生成工具Yacc/Bison实现语法分析器的构造。

二、实验内容利用语法分析器生成工具Yacc/Bison编写一个语法分析程序，与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。

三、实验要求１．个人完成，提交实验报告。

２．实验报告中给出采用测试源代码片断，及其对应的最右推导过程（形式可以自行考虑，如依次给出推导使用的产生式）。

例如，程序片断四、实验步骤1、根据文法编写.y文件：%{#include<ctype.h>#include<stdio.h>#define YYSIYPE doublevoid yyerror(char *s){printf("%s\n",s);}%}%token NUM%token BASIC IF ELSE DO BREAK REAL TRUE FALSE ID LE INDEX%token WHILE AND OR EQ NE GE%left '+''-'%left '*''/'%right UMINUS%%program : block {printf("program->block\n");};block : '{'decls stmts'}' {printf("block->decls stmts\n");};decls : decls decl {printf("decls->decls decl\n");}| {printf("\decls->E\n");};decl : type ID ';' {printf("decl->type id\n");};type : type '[' NUM ']' {printf("type->type [num]\n");}| BASIC {printf("type->basic\n");};stmts : stmts stmt {printf("stmts->stmts stmt\n");}| {printf("stmts->E\n");};stmt : loc '=' bool ';' {printf("stmt->loc=bool\n");}|IF '(' bool ')' stmt {printf("stmt->if(bool) stmt\n");}|IF '(' bool ')' stmt ELSE stmt {printf("stmt->if(bool) stmt else stmt\n");}|WHILE '(' bool')' stmt {printf("stmt->while(bool) stmt\n");}|DO stmt WHILE '(' bool ')' ';' {printf("stmt->->do stmt while(bool)\n");}|BREAK ';' {printf("stmt->break\n");}| block {printf("stmt->block\n");};loc : loc '[' bool ']' {printf("loc->loc[bool]\n");}|ID {printf("loc->id\n");};bool : bool OR join {printf("bool->bool||join\n");}| join {printf("bool->join\n");};join : join AND equality {printf("join->join && equality\n");}| equality {printf("join->equality\n");};equality : equality EQ rel {printf("equality->equality==rel\n");}| equality NE rel {printf("equality->equality!=rel\n");}| rel {printf("equality->rel\n");};rel : expr '<' expr {printf("rel->expr<expr\n");}| expr LE expr {printf("rel->expr<=expr\n");}| expr '>' expr {printf("rel->expr>expr\n");}| expr GE expr {printf("rel->expr>=expr\n");}| expr {printf("rel->expr\n");};expr : expr '+' term {printf("expr->expt+term\n");}| expr '-' term {printf("expr->expr-term\n");}| term {printf("expr->term\n");};term : term '*' unary {printf("term->term*unary\n");}| term '/' unary {printf("term->term/unary\n");}| unary {printf("term->unary\n");};unary : '!' unary {printf("unary->!unary\n");}| '-' unary {printf("unary->-unary\n");}| factor {printf("unary->factor\n");};factor: '(' bool ')' {printf("factor->(bool)\n");}| loc {printf("factor->loc\n");}| NUM {printf("factor->num\n");}| REAL {printf("factor->real\n");}| TRUE {printf("factor->true\n");}| FALSE {printf("factor->false\n");};%%2、在.y文件中添加main()函数，以及一些外部函数的声明：#include "lex.yy.c"int yyparse();extern void BeginCompileOneFile( const char * filename );extern void EndCompileOneFile(void);void main(){char filename[200];printf("请输入源程序文件名：");scanf("%s:",filename);BeginCompileOneFile( filename );yyparse();EndCompileOneFile();}3、修改实验三的.l文件，删除main()函数：4、用flex.exe编译.l文件，生成lex.yy.c5、用bison.exe编译.y文件，生成my.tab.c6、在VC下建立工程，添加lex.yy.c和my.tab.c文件7、以文件读入方式进行测试，测试例子为：{i = 2;while (i <=100){sum = sum + i;i = i + 2;}}五、实验结果六、心得体会其实这个实验并不难，不过很容易出错。