当前位置: 首页 > >

编译方法实验2

发布时间:

编译方法实验2
人民大学信息学院 陈文萍

实验概述
? 实验内容:用bison工具生成一个PL/0语言 的语法分析程序,对PL/0源程序进行语法 分析,并输出归约时所用的语法规则。
? 实验环境:
? 语法分析器生成工具:bison ? 编程语言:C

YACC概述(1)
? YACC = Yet Another Compiler Compiler ? YACC是一个语法分析程序的自动产生系统
YACC源程序 源语言程序 YACC yyparse()函数

parser_tab.c文件
语法分析结果

? 词法分析程序与语法分析程序的关系
源语言程序 词法分析程序

yylex()

单词符号串

语法分析程序

语法分析结果

yyparse()

YACC概述(2)
? YACC的工作原理:
文法描述 语法分析程序

? YACC的处理能力:可以用LALR(1)文法 表示的上下文无关文法。

YACC源程序的格式
%{ 声明 %} 辅助定义 %% 语法规则 %% 用户子程序 (main函数必须要有) --可选 --可选 --必须有

--可选

声明
? 所有嵌在?%{”和?%}”之间的内容将被原 样拷贝到C语言文件中。 ? 在声明中,可以引入头文件、宏定义、以 及全局变量的定义等。
例如: %{ #include <stdio.h> #include “scanner.h”(必须包含这个头文件) %}

辅助定义
? 语法开始符号定义
%start %token %start line %token DREG VREG %token CONST 非终结符(开始符号,一般为‘program’) 终结符(一般从词法分析器得来)

? 终结符定义

? 优先级和结合性定义
%left (表示左结合符号) %right %prec

语法规则的写法
? 格式: 左部(非终结符):右部(文法符号串);

? 非终结符名称通常用小写字母,终结符名称通常用大 写字母。
? 右部为空表示左部的非终结符可以匹配空串。 ? 左部相同的语法规则应尽量合并。 ? 需要递归时,尽量使用左递归。
例如 StmtList :
| ;

/* empty */
StmtList Stmt //(左)递归定义

语义动作的写法
? 语义动作用{ }括起来,其中的语句 要符合C语言文法。 ? 语义动作出现在规则的尾部时, bison在归约前执行它。 ? 语义动作出现在规则的中间时, bison在识别出它前面的若干文法符 号后执行它。

语义动作的写法
例如: expr : LPAREN expr RPAREN { $$ = $2; } | expr PLUS expr { $$ = $1 + $2; } | expr TIMES expr { $$ = $1 * $2; }

文法符号的语义值
? 终结符的语义值由词法分析程序给出, 并保存在yylval中。 ? 非终结符的语义值在语义动作中获得。 ? 可以通过$伪变量访问语义值
? 左部非终结符的语义值为$$ ? 右部文法符号的语义值依次为$1,$2,…
例如 exp:
| ;

NUM { $$ = $1; }
exp '+' exp { $$ = $1 + $3; }

语法规则举例
%% Input : /* empty */ | input line ; Line : '\n? | exp '\n' { printf ("\t%.10g\n", $1); } ; exp : NUM { $$ = $1; } | exp PLUS exp { $$ = $1 + $3; } | exp MINUS exp { $$ = $1 - $3; } | exp TIMES exp { $$ = $1 * $3; } | exp SLASH exp { $$ = $1 / $3; }

;
%%

用户子程序
? 子程序用C语言书写,将被原样照抄到C 语言文件中。
? 如果子程序比较简单,可以全都写在YACC 源文件中。 ? 如果子程序比较复杂,可以分别写在几个文 件中。

YACC源程序实例
/* 用YACC实现的一个简单的计算器 */ %{ #include <stdio.h> #include <math.h> #define YYSTYPE double %}

/* 终结符 */
%token NUM /* 优先级和结合性 */ %left ?-? ?+? %left '*' '/? %left NEG //单目取反运算 %right ?^? //指数运算 //加减左结合

%% input : /* empty string */ | input line ; line : '\n' | exp '\n' { printf ("\t%.10g\n", $1); } | error ?\n? ;

exp

: NUM { $$ = $1; }
| exp ?+? exp { $$ = $1 + $3; }//return 的使用终结符
//必须已经在先前定义

| exp '-' exp { $$ = $1 - $3; }

| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { $$ = $1 / $3; } | '-' exp %prec NEG { $$ = -$2; } | exp '^' exp { $$ = pow ($1, $3); } | '(' exp ')' { $$ = $2; } ; %%

/* 用户子程序 */

main (){
yyparse (); } int yylex() { … } yyerror (char *s) { printf ("%s\n", s); } /********************************** //进行紧急中止 //只需要做出数的识别规则

Bison 在使用的时候 必须附加 –d 参数进 行头文件生成(否则 yylex工作不连接)

运行结果:
4 + 4.5 - (34/(8*3+-3)) 6.880952381 **********************************/




友情链接: