《编译原理实践11—语法分析程序的自动生成工具YACC.》由会员分享,可在线阅读,更多相关《编译原理实践11—语法分析程序的自动生成工具YACC.(24页珍藏版)》请在金锄头文库上搜索。
1、编译原理实践 -语法分析程序的自动生成工具YACC YACC简单的介绍 YACC(Yet Another Compiler- Compiler) 是美国贝尔实验室开发的 语法分析程序自动生成器 输入是某个语言的语法规则,输出是 该语言的语法分析器。 目前YACC生 成的是一个LALR(1)分析器 常用版本:Berkeley大学的BYACC, GNU工程的BISON YACC的使用流程 YACC源程序YACC Y_tab.c (宏定义文件) C编译器Y_tab.exe 字符串源程序 Y_tab.exe分析结果 YACC的输入文件称为YACC源文件,以.y为扩展名,输出文 件有两个,一个是包含有语
2、法分析函数yyparse()的C程序, 另一个是包含源文件中所有终结符编码的宏定义文件,扩展 名为.h。这两个文件经过C编译器的编译就生成一个语法分析 器,该语法分析器的输入是源程序经过词法分析的结果,输 出可以是一棵语法树,或者是所生成的目标代码,也可以是 关于输入串是否符合语法规则的信息。具体的输出形式可以 在YACC源程序中自己定义。 Y_tab.c (宏定义文件) YACC和LEX有直接的接口,由于YACC与LEX 的特殊功能,这两个姐妹程序成为软件工程的重 要工具,被称为“黄金组合”。 很多程序设计语言编译程序的设计都使用了 LEX和YACC,比如著名的GNU C语言编译器, PAS
3、CAL语言向C语言的转换工具p2c等,就是 用FLEX和BISON实现的 多数程序设计语言的语法分析都采用LALR(1) 分析法,YACC也正是以LALR(1)文法为基础。 它通过对输入的形式文法规则进行分析,产生 LALR(1)分析表,输出以该分析表驱动的语法分 析器C语言源程序。 YACC源程序结构 YACC源程序由三个部分组成,各部分以 “%”为分隔符。说明部分和程序部分可 选,规则部分是必需的。 说明部分 % 规则部分 % 程序部分 YACC源程序结构说明部分 YACC源程序说明部分定义语法规则中要用 的终结符号,语义动作中使用的数据类型、 变量、语义值的联合类型以及语法规则中运 算符
4、的优先级等。说明部分可以是空的。 说明部分通常包含两部分内容: C语言代码部分 Yacc说明部分 YACC源程序结构说明部分 % 头文件表 宏定义 数据类型定义 全局变量定义 % 文法开始符号定义 语义值类型定义 终结符定义 非终结符定义 优先级和结合性定义 1-头文件表 yacc直接把这部分定义抄到所生成的C语言程 序y.tab.c去的,所以要按C语言的语法规定来 写。头文件表是一系列C语言的#include语句 ,要从每行的第一列开始写,例如: % #include #include #include #include “header.h” % % 2-宏定义 这部分用C语言的 #defi
5、ne语句定义程序 中要用的宏 例如 % #define max(x,y)(xy)?x:y) % 3-数据类型定义 这部分定义语义动作中或程序段部分中要用到 的数据类型 例如 % typedef struct interval double lo,hi; INTERVAL; % 4-全局变量定义 外部变量(external variable)和yacc源程序中要用 到的全局变量都在这部分定义 例如 % . extern int nfg; douhle dreg 26; INTERVAL Vreg26; . % 5-语法开始符定义 上下文无关文法的开始符号是一个特殊的 非终结符,所有的推导都从这个
6、非终结符 开始 在yacc中,语法开始符定义语句是 % start 非终结符 如果没有上面的说明,yacc自动将语法 规则部分中第一条语法规则左部的非终结 符作为语法开始符 6-语义值类型定义 yycc生成的语法分析程序yyparse用的 是LR分析方法,它在作语法分析时除了 有一个状态栈外,还有一个语义值栈 语义值栈存放它所分析到的非终结符和终 结符的语义值,这些语义值有的是从词法 分析程序传回的,有的是在语义动作中赋 与的 如果没有对语义值的类型做定义,那么 yacc认为它是整型(int)的,即所有语 法符号如果赋与了语义值,则必须是整型 的,否则会出类型错 6-语义值类型定义 但是用户经
7、常会希望语义值的类型比较复杂, 如双精度浮点数,字符串或树结点的指针 这时就可以用语义值类型定义进行说明。因为 不同的语法符号的语义值类型可能不同,所以 语义值类型说明就是将语义值的类型定义为一 个联合(Union),这个联合包括所有可能用 到的类型(各自对应一个成员名) 为了使用户不必在存取语义值时每次都指出成 员名,在语义值类型定义部分还要求用户说明 每一个语法符号(终结符和非终结符)的语义 值是哪一个联合成员类型 6-语义值类型定义 例: % union int ival double dval INTERVAL vval; 引用时候的方式 %token DREG VREG %token
8、 CONST %type dexp %type vexp 以%token开始的行定义的是终结符的类型 以%type开始的行定义是非终结符的类型 7-终结符定义 在yacc源程序语法规则部分出现的所有 终结符(正文字符“+”,“-”等除外)等必 须用%token定义,定义形式: 单一数据类型: %token 终结符1 终结符2 多数据类型: %token 终结符1 终结符2 8-终结符定义 优先级和结合性定义 %left 左结合 %right 右结合 %nonassoc 无结合性 %prec 强制定义优先级 YACC源程序语法规则部分 语法规则部分是整个YACC源程序的主体,它是由一组 产生式及
9、相应的语义动作组成。 规则部分包括修改的BNF格式的文法规则,以及将在识 别出识别出相关的文法规则时被执行的C代码中的动作 (即根据LALR(1)分析算法,在归约中使用)。 文法规则中使用的元符号惯例如下: 通常,竖线|被用作替换(也可以分别写出替换项),而 用来分隔文法规则的左右两边的箭头符号-在YACC中 用冒号表示,最后,必须用分号来结束每个文法规则。 YACC源程序语法规则部分 对文法中的产生式 在YACC程序中可表示成 A: 语义动作1 语义动作2 语义动作m ; YACC源程序语法规则部分 YACC中的动作是由在每个文法规则中将其写作真正的C 代码(在大括号中)来实现的。 在书写动
10、作时,可以使用YACC伪变量。当识别一个文 法规则时,规则中的每个符号都拥有一个值,除非它被 参数改变了。 这些值由YACC保存在一个与分析栈保持平行的值栈( value stack)中,每个在栈中的符号值都可以使用以$ 开始的伪变量来引用。 $代表刚才被识别出来的非终结符的值,也就是文法规 则左边的符号。伪变量$1、$2、$3等代表了文法规则右 边的每个连续的符号。 YACC源程序语法规则部分 例:文法规则和动作: exp:exp+term$=$1+$3; 含义是:当识别规则exp-exp+term时, 左边exp值为右边的exp的值与右边的term 的值之和,其中$代表规则左部符号exp的
11、 值,$1代表规则右部第一个符号exp的值、 $3表示规则右部第三个符号term的值。 YACC源程序程序部分组成 YACC源程序的程序部分包括: 主程序 main() 错误信息执行程序 yyerror(s) 词法分析程序yylex(),可以与LEX进行整合 用户在语义动作中用到的子程序 YACC约定: 传递词法分析程序token属性值的全程变量 名:yylval 生成的语法分析程序名为:yyparse(); 二义性文法的处理 YACC生成LALR(1)分析器,如果接受的文法 不是LALR(1)分析表就有冲突。YACC解决冲 突的默认规则为: 归约归约冲突:选择YACC源程序中排列 在前面的产生式进行归约; 移进归约冲突:移进动作优先于归约动 作。