语法分析程序的自动生 成工具YACC简介 西北工业大学计算机系 康慕宁 2001.2.第二版
语法分析程序的自动生 成工具 简介 西北工业大学计算机系 2001.2
LALR(1)分析器自动生成工具 YACC YACC(Yet Another Compiler- Compiler)是LALR(1)分析器的自动生成工 具,它的第一版于70年代初发表,是美国贝 尔实验室的软件产品(作者为S.C.Johnson) ◆YACC将一前后文无关文法转换为一LALR(1) 分析表,并提供使用该分析表进行语法分析的总 控程序yyparse()
自动生成工具— u YACC(Yet Another Compiler- Compiler)是 分析器的自动生成工 具,它的第一版于 年代初发表,是美国贝 尔实验室的软件产品(作者为 ) 将一前后文无关文法转换为一 分析表,并提供使用该分析表进行语法分析的总 控程序
使用YACC构造语法分析程序 ◆用户按一定规列则编写出“文信处理谠明 文件”,简称YSP(Yacc Specification)) 文件,文件的扩展名为“.y”。 ◆将YSP输入YACC中,YACC就会自动地构造 出相应的C语言形式的语法分析器 ◆该分析器主要包括由YACC提供的标准总 控程序和一个LALR(1)语法分析表
使用 u用户按一定规则编写出“ ” ,简称YSP(Yacc Specification) 文件,文件的扩展名为“ ” 。 u将YSP输入YACC中,YACC就会自动地构造 出相应的 形式的语法分析器 u该分析器主要包括由YACC提供的 和一个LALR(1)
YACC的工作机制 YSP文件 YACC 语法分析程序ytab.c =总控程序+分析表 y.tab.c C编译程序 0文件 YACC的使用格式为: yacc[选项] filename.y
YSP文件 YACC 语法分析程序ytab.c =总控程序+分析表 的使用格式为: yacc [ ] filename.y y.tab.c C编译程序 .o文件
YMcc命令的选项 -V 输出描述分析表及报告语法冲突的文件y.output -d 生成头文件y.tab.h,该文件中用#definei语句定义 YSP文件中的token((终结符) 指定y.tab.c中将不产生ine结构行.在程序完全进行 过debug后使用此选项可使程序简短些 -Qyn-Qy选项输出版本戳信息到y.tab.c文件中.使用户 能了解使用的是哪个yacc版本.Qn选项(缺省选项)不 输出此信息 在标准错误上输出yacc的版本信息 -W 生成可写的分析表缺省为只读
命令的选项 输出描述分析表及报告语法冲突的文件 生成头文件 ,该文件中用#define语句定义 文件中的 (终结符). 指定 中将不产生 结构行.在程序完全进行 过 后使用此选项可使程序简短些. 选项输出版本戳信息到 文件中.使用户 能了解使用的是哪个 版本. 选项(缺省选项)不 输出此信息. 在标准错误上输出 的版本信息. 生成可写的分析表,缺省为只读
gacc命令的选项 -t 编译实时debug代喝.实时debug代码总是被yacc生 成条件编译代码缺省时,这些代码不会被编译.是否被 编译取决于预处理常量YYDEBUG.若YYDEBUG具有 非零值,则debug代鸡被included.否则,not be included. 不含debug代喝的可执行代码的程序比含有debug代码 的程序小且速度较快 -b file_prefix用file_prefix替换输出文件的前缀y.例如, y.tab.c,y.output被相应地替换为file prefix,.tab.c和 file_prefix.output. -p sym_prefix用sym_prefix取代程序中所有以yy为前缀 的量如vyparseO,ylexO,yerror0,ywal,yychar, ydebug等
编译实时 .实时 总是被 生 成条件编译代码.缺省时,这些代码不会被编译. 是否被 编译取决于预处理常量 .若 具有 非零值,则 被 .否则, . 不含 的可执行代码的程序比含有 的程序小且速度较快. 用 替换输出文件的前缀y.例如, y.tab.c,y.output被相应地替换为 和 . 用 取代程序中所有以 为前缀 的量 .如 等
YSP文件的结钩 一个完整的YSP文件由说明、 我们以一个简单的台式计算 规则、程序三个部分组成, 器中的处理程序的自动生成 各部分之间以双百分号 为例,说明怎样编写YSP文件 “%%"隔开 ◆ 该计算器的功能为:读入一 [院明部分] 行算术表达式,然后计算并 %% 打印它的值 规则部 ◆算术表达式的文法如下: [%% Expr→Expr+Term Term 灌序邦女] Term Term Factor Factor 其中,用方括号括起来的说 Factor→(Expr)I digit 明部分和程序部分可以空缺, ◆其中,终结符digit是0-9中的 但规则都兮则是必需的 任何一个数字
文件的 u 一个完整的 文件由 三个部分组成, 各部分之间以 “ ”隔开 u u 其中,用方括号括起来的说 明部分和程序部分可以空缺, 但 则是必需的 u 我们以一个 中的处理程序的自动生成 为例,说明怎样编写 文件 u 该计算器的功能为:读入一 行算术表达式,然后计算并 打印它的值 u 算 术 表 达 式 的 文 法 如 下 : Expr → Expr + Term | Term Term → Term * Factor | Factor Factor → ( Expr ) | digit u 其中,终结符 是 中的 任何一个数字
YSP文件的例子 %{/*说明部分*/ /*Term=Term*Factor*/ yylval=c-'0'; #include I F a c to r return digit; #include /*Term=Factor*/; %} Factor:'(Expr ) return c; %token digit 300 {$$=$2;} } %%/*规则部分*/ /*Factor=Expr*/ void yyerrort(O/*出 Li n e:E x p r'\n digit 错处理程序*/ printf("%d\n",$1);}; /*Factor=digit*/; prinft("Syntax /*打印表达式值*/ %%/*程序部分*/ error\n");} Expr Expr '+Termint yylex(void void main() {$$=$1+$3;*词法分析程序*/ {yyparse();/*调 /*Expr=Expr+Term*/ int c=getchar(; 用语法分析程序*/ |Term /*读入一个字符*/ /*Expr=Term*/ if(isdigit(c)) Term:Term'*'Factor /*判别c是否为数字*/ {$$=$1*$3;}
YSP文件的例子 %{/*说明部分*/ %} %token digit 300 %% /*规则部分*/ L i n e : E x p r ' \ n ’ {printf("%d\n" ,$1);} ; /*打印表达式值*/ Expr :Expr '+' Term { $ $ = $ 1 + $ 3 ; } /*Expr=Expr+Term*/ |Term ; /*Expr=Term*/ Term:Term'*' Factor {$$=$1*$3;} /*Term=Term*Factor*/ | F a c t o r /*Term=Factor*/; Factor:'(' Expr ')' {$$=$2;} /*Factor=Expr*/ |digit /*Factor=digit*/ ; %%/*程序部分*/ int yylex(void ) {/*词法分析程序*/ int c=getchar(); /*读入一个字符*/ if(isdigit(c)) /*判别c是否为数字*/ { yylval=c-'0'; return digit; } return c; } void yyerror()/*出 错处理程序*/ { prinft("Syntax error\n");} void main() { yyparse();/*调 用语法分析程序*/ }
YSP说明部分的组成 ◆YSP文件中的镜明都分用于定义规则部分所使用的变量及语法符 号 1. 变量定义变量定义需要用一对特殊括号“%{”和“%}”括起 来,其内容包括规则部分中的语义处理动作以及程序部分所需使 用的有关文件(如C语言的有关头文件)的引用说明、数据结构的 定义、全局变量的定义以及函数原型的定义等等,这部分内容应 遵守C语言的规定 ◆2.开始符号定义文法的开始符号由说明符%start(请注意, YACC中的所有说明符均由%?引出)指明,例如: %ostart StartSymbol ◆3.词汇表定义在这部分,用户可以给出终结符号表、联合 (union)和类型(type)说明
的组成 中的 用于定义规则部分所使用的 u 1. 变量定义需要用一对特殊括号“%{”和“%}”括起 来,其内容包括规则部分中的语义处理动作以及程序部分所需使 用的有关文件(如C语言的有关头文件)的引用说明、数据结构的 定义、全局变量的定义以及函数原型的定义等等,这部分内容应 遵守 语言的规定 u 2. 文法的开始符号由说明符%start(请注意, 中的所有说明符均由‘%’引出)指明,例如: u 3. 在这部分,用户可以给出 表、联合 ( )和类型( )说明
YSP说明部分的组成(猿) ◆YACC要求所用到的所有文字形式的终结符都应明确加以说明; 对于未说明者,则均按非终结符处理。 ◆终结符说明由说明符%token或%term引出,其书写格式有两种。 ◆第一种书写格式为 %token Tname1 [Tname2...] 不同的终结符之间用空格分隔;在二行写不下时,可用 %token另起一行继续定义。 ◆ 第二种允许用户自行定义终结符的内部编码值,其格式为: %token Tname 其中,一般应为大于256的整数,表示该单词的 内部 当用户未给出终结符的内部码时,系统将按终结符的出现顺序, 依次为其定义内部码值:257,258
的组成( ) 要求所用到的所有文字形式的终结符都应明确加以说明; 对于未说明者,则均按非终结符处理。 u 终结符说明由说明符%token或%term引出,其书写格式有两种。 u 第 一 种 书 写 格 式 为 不同的终结符之间用空格分隔;在一行写不下时,可用 %token另起一行继续定义。 u 第二种 允许用户自行定义终结符的内部编码值,其格式为: 其中, 一般应为大于 的整数,表示该单词的 . u 当用户未给出 的 时,系统将按 的出现顺序, 依次为其定义内部码值: