编译原理实践--语法分析程序的自动生成工具yacc

《编译原理实践--语法分析程序的自动生成工具yacc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理实践--语法分析程序的自动生成工具YACCYACC简单的介绍YACC(YetAnotherCompiler-Compiler)是美国贝尔实验室开发的语法分析程序自动生成器.其输入是某个语言的语法规则，输出该语言的语法分析器。目前YACC生成的是一个LALR(1)分析器。常用版本：Berkeley大学的BYACC,GNU工程的BISONYACC的使用流程YACC源程序YACCY_tab.c(宏定义文件)C编译器Y_tab.exe字符串源程序Y_tab.exe分析结果YACC的输入文件称为YACC源文件，以.y为扩展名，输出文件有两个，一个是包含有语法分析函数yyparse()的C程序

2、，另一个是包含源文件中所有终结符编码的宏定义文件，扩展名为.h。这两个文件经过C编译器的编译就生成一个语法分析器，该语法分析器的输入是源程序经过词法分析的结果，输出可以是一棵语法树，或者是所生成的目标代码，也可以是关于输入串是否符合语法规则的信息。具体的输出形式可以在YACC源程序中自己定义。Y_tab.c(宏定义文件)YACC和LEX有直接的接口，由于YACC与LEX的特殊功能，这两个姐妹程序成为软件工程的重要工具，被称为“黄金组合”。很多程序设计语言编译程序的设计都使用了LEX和YACC，比如著名的GNUC语言编译器，PASCAL语言向C语言的转换工具p2c等，就是用FLEX和BISO

3、N实现的多数程序设计语言的语法分析都采用LALR(1)分析法，YACC也正是以LALR(1)文法为基础。它通过对输入的形式文法规则进行分析，产生LALR(1)分析表，输出以该分析表驱动的语法分析器C语言源程序。YACC源程序结构YACC源程序由三个部分组成，各部分以“%%”为分隔符。说明部分和程序部分可选，规则部分是必需的。[说明部分]%%规则部分[%%程序部分]YACC源程序结构—说明部分YACC源程序说明部分包括了YACC需要用来建立分析程序的有关记号、数据类型以及文法规则的信息。它还包括了必须在它的开始时直接进入输入文件的任何C代码（主要是其他源代码文件的#include指示）。说明

4、部分可以是空的。说明部分通常包含两部分内容：C语言代码部分Yacc说明部分YACC源程序结构—说明部分%{头文件表宏定义数据类型定义全局变量定义%}文法开始符号定义语义值类型定义终结符定义非终结符定义优先级和结合性定义YACC源程序结构—说明部分C语言代码部分：%{…%}之间的部分直接copy到输出文件中去Yacc说明部分：%startS指明S为文法开始符号，若未给出开始符定义，系统自动以第一条语法规则的左部符号作为开始符语义值类型定义语义值的数据类型定义就是确定语义栈的数据结构例1：单一的数据类型#defineYYSTYPEdouble例2:#union{SYMBOL*sym;ENODE

5、*node;}YYSTYPE引用时候的方式%tokenid%typeexpr以%token开始的行定义的是终结符的类型以%type开始的行定义是非终结符的类型3.终结符定义在yacc源程序语法规则部分出现的所有终结符（正文字符“+”，“-”等除外）等必须用%token定义，定义形式：单一数据类型：%token终结符1终结符2多数据类型：%token<类型>终结符1终结符2…优先级和结合性定义%left左结合%right右结合%nonassoc无结合性%prec<终结符>强制定义优先级YACC源程序—语法规则部分语法规则部分是整个YACC源程序的主体，它是由一组产生式及

6、相应的语义动作组成。规则部分包括修改的BNF格式的文法规则，以及将在识别出识别出相关的文法规则时被执行的C代码中的动作（即根据LALR（1）分析算法，在归约中使用）。文法规则中使用的元符号惯例如下：通常，竖线

7、被用作替换（也可以分别写出替换项），而用来分隔文法规则的左右两边的箭头符号-〉在YACC中用冒号表示，最后，必须用分号来结束每个文法规则。YACC源程序—语法规则部分对文法中的产生式在YACC程序中可表示成A：{语义动作1}{语义动作2}……{语义动作m};YACC源程序—语法规则部分YACC中的动作是由在每个文法规则中将其写作真正的C代码（在大括号中）来实现的。在书写动作时，可以使

8、用YACC伪变量。当识别一个文法规则时，规则中的每个符号都拥有一个值，除非它被参数改变了，该值将被认为是一个整型（稍后将会看到这种情况）。这些值由YACC保存在一个与分析栈保持平行的值栈（valuestack）中，每个在栈中的符号值都可以使用以$开始的伪变量来引用。$$代表刚才被识别出来的非终结符的值，也就是文法规则左边的符号。伪变量$1、$2、$3等代表了文法规则右边的每个连续的符号。YACC源程序—语法规则部分文法规