编译原理课程设计报告

编译原理课程设计报告

实验1：用Lex设计词法分析器1

实验目的：学会用lex设计一个词法分析器。

实验内容：使用lex为下述文法语言写一个词法分析器。 实验要求：

输入为用该语言所写的源程序文件；输出为记号序列，每个记号显示为二元组(记号名，记号属性值)的形式。输出可以在屏幕上，也可以输出到文件中。不要求建立符号表。

在cygwin下用flex和gcc工具将实验调试通过，并能通过例子parser0中testcases目录下的test1.p测试例的测试。

实验参考：exam1.l和exam2.l。

语言文法：

<程序>? PROGRAM <标识符> ; <分程序>

<分程序>? <变量说明> BEGIN <语句表> END. <变量说明> ? VAR <变量说明表>;

<变量说明表>?<变量表>: <类型> | <变量表>: <类型>; <变量说明表> <类型>? INTEGER | REAL

<变量表>? <变量> | <变量>, <变量表>

<语句表>? <语句> | <语句>; <语句表>

<语句>? <赋值语句> | <条件语句> | | <复合语句> <赋值语句>?<变量> := <算术表达式>

<条件语句>? IF <关系表达式> THEN <语句> ELSE <语句> ? WHILE <关系表达式> DO <语句> <复合语句> ? BEGIN <语句表> END

<算术表达式> ? <项> | <算术表达式> + <项> | <算术表达式> - <项> <项> ? <因式> | <项> * <因式> | <项> / <因式> <因式>? <变量> | <常数> | (<算术表达式>)

<关系表达式>? <算术表达式> <关系符> <算术表达式> <变量>? <标识符>

<标识符>? <标识符><字母> | <标识符><数字> | <字母> <常数>? <整数> | <浮点数> <整数>? <数字> | <数字> <整数> <浮点数>? .<整数> | <整数>.<整数> <关系符>? < | <= | = | > | >=| <>

<字母>? A | B | …| X | Y | Z | a | b | …| x | y | z <数字>?0|1|2|…|9

程序代码： %{

#include #define LT #define LE #define GT #define GE #define NE

1 2 3 4 5 6

#define EQ

#define PROGRAM #define END #define VAR

#define IF #define THEN

7 13

9 10 11

#define ELSE 12 #define WHILE 18 #define DO 19 #define ID 20 #define NUMBER 21 #define RELOP 22 #define NEWLINE 23 #define ERRORCHAR 24 %} delim ws letter digit id

[ \\t \\n] {delim}+ [A-Za-z]

[0-9] _|{letter}({letter}|{digit})*

number {digit}+(\\.{digit}+)?(E[+-]?{digit}+)?

int1 {digit}|{digit}{int1}*/ %s COMMENT %%

\ \

{BEGIN COMMENT;ECHO;} {BEGIN INITIAL;ECHO;}

.|\\n {ECHO;}

/* ECHO是一个宏，相当于 fprintf(yyout, \{ws} {;}

while {return (WHILE);} do {return (DO);}

PROGRAM

end VAR

{return (PROGRAM);}

{return (END);} {return (VAR);}

if {return (IF);} then else {id} {number} \

{return (THEN);} {return (ELSE);} {return (ID);}

{return (NUMBER);}

{return (RELOP);}

\ {return (RELOP);} \ {return (RELOP);} \ {return (RELOP);} \

{return (RELOP);}

\ {return (RELOP);}

\\

{return (RELOP);} {return (RELOP);}

\ {return (RELOP);} \ {return (RELOP);} \ {return (RELOP);} \ {return (RELOP);} \ {return (RELOP);} \ {return (RELOP);} . %%

int yywrap (){ return 1; }

void writeout(int c){ switch(c){

case ERRORCHAR: fprintf(yyout, \ case RELOP: fprintf(yyout, \, \\\ case WHILE: fprintf(yyout, \ case DO: fprintf(yyout, \

case NUMBER: fprintf(yyout, \ case ID: fprintf(yyout, \ case NEWLINE: fprintf(yyout, \

case PROGRAM: fprintf(yyout, \ case END: fprintf(yyout, \ case VAR: fprintf(yyout, \AR, \\\ case IF: fprintf(yyout, \, \\\ case THEN: fprintf(yyout, \ case ELSE: fprintf(yyout, \ default:break; }

{return ERRORCHAR;}

return;

}

int main (int argc, char ** argv){

int c,j=0; if (argc>=2){

if ((yyin = fopen(argv[1], \ printf(\ return 1; }

if (argc>=3){

yyout=fopen(argv[2], \ } }

while (c = yylex()){ writeout(c); j++; }

if(argc>=2){ fclose(yyin);

if (argc>=3) fclose(yyout); }

if (j%5 == 0) writeout(NEWLINE);

return 0; }

测试文件为Test1.p： PROGRAM test;

VAR i, j, k: INTEGER; f0: REAL; BEGIN i := 1; j := 1; k := 0; f0 := 3.2;

WHILE k<=100 DO BEGIN

IF j <20 THEN BEGIN j := i; k := k+1; f0 := f0*0.2 END

ELSE BEGIN j := k; k := k-2; f0 := f0/.2 END END END.

运行结果：

实验2：用Lex设计词法分析器2

实验目的：学会用lex设计一个词法分析器，并考虑其与后续语法分析器的链接问题。 实验内容：修改上次实验1的词法分析器，使其满足下列要求。 实验要求：

1. 要求每次调用词法分析函数yylex时，只返回一个记号(token)；

2. 为记号选择适当的属性值，并且每次词法分析函数返回记号前，都将记号的属性值存入全局变量yylval中。（yylval可以自己定义为全局变量）；

3. 记号属性值的选择：标识符的属性为标识符的名字字符串（例如，标识符name1的属性为字符串”name1”），整数的属性为整数值，浮点数的属性为浮点数值。其他记号属性值可自己选择。关键字可以省略属性。

4. 注意：由于属性值需要存入yylval中，并且记号属性值的类型比较多（可能为字符串、整数、浮点数等），因此yylval必须能同时存放各种类型的值（提示：将yylval设置为union类型）。 5. 在cygwin下用flex和gcc工具将实验调试通过，并能通过例子parser0中testcases目录下的test1.p测试例的测试。

实验3：熟悉Yacc的使用

实验目的：

熟悉语法分析器生成工具Yacc的使用，并学会在cygwin下使用bison工具编译Yacc文法说明文件。学习如何使用lex和yacc合作进行语法分析。 实验内容：

根据给出的calculator例子（calculator0,calculator1,calculator2,calculator3）完成下面题目：用lex和yacc写一个计算布尔表达式真值的计算器。

实验要求：

输入为一个布尔表达式，以换行结束。输出为这个布尔表达式的真值（true或false）。必须用二义文法实现。布尔表达式二义文法为：S –> S or S | S and S | not S | (S) | true | false，其中优先级or < and < not，or 和 and 左结合，not 右结合。用非二义文法

实现作为选作内容，非二义文法请参照表达式非二义文法自己写出来。

在cygwin下用flex，bison和gcc工具将实验调试通过，并写出测试例测试正确性。 实验参考：

calculator0-3这四个例子。 程序代码：

Cal.y文件： %{ int yylex();

#define YYSTYPE double /* 将Yacc栈定义为double类型 printf(\value of the expression is %lf.\\n\

%}

%token NUM LPAREN RPAREN ENTER %left OR %left AND %right NOT

%left PLUS MINUS %left TIMES DIVIDE %right UMINUS

%%

/* 这样写prog可以让分析器每次读入一行进行分析，下一行重新分析expr */ prog : prog exprp

| exprp ;

exprp : expr ENTER {printf(\表示 true；0 表示 false %lf.\\n\

;

expr : expr PLUS expr {$$ = $1 + $3;} | expr MINUS expr {$$ = $1 - $3;} | expr TIMES expr {$$ = $1 * $3;}

| expr DIVIDE expr {$$ = $1 / $3;} | LPAREN expr RPAREN {$$ = $2;} | MINUS expr {$$ = -$2;} | NUM {$$ = $1;}

;

%%

int main(){ yyparse(); return 0; }

Cal.l文件： %{

#include \#include int yywrap(void){ return 1; }

#define LT #define LE #define GT #define GE #define EQ #define NE

#define PROGRAM

#define END #define VAR

#define IF

#define THEN

#define ELSE

#define WHILE #define DO

| expr OR expr {$$=panduan($1*$1+$3*$3);} | expr AND expr {$$=panduan($1*$3);} | NOT expr {$$=panduan2($2);} 1 2 3 4 5 6 7 13 9 10

11

12

18 19

#define ID 20 #define RELOP 22

#define NEWLINE 23 #define ERRORCHAR 24 %} ws digit inum fnum letter id %%

[ \\t]+ [0-9]

{digit}+ {digit}*\\.{digit}+ [A-Za-z]

_|{letter}({letter}|{digit})*

{inum} {sscanf(yytext, \{fnum} {sscanf(yytext, \\ \ \ \ \

{return PLUS;} {return TIMES;} {return MINUS;} {return DIVIDE;} {return LPAREN;}

\ {return RPAREN;}

\ {return OR;} \ {return AND;} \ {return NOT;} \ \ \

{return LT;} {return LE;} {return GT;}

\ {return GE;}

\ {return EQ;} \ {return NQ;} \ {return FZ;}

{ws} \

{;}

{return ENTER;}

. {printf(\\ {BEGIN COMMENT;ECHO;} \while

{BEGIN INITIAL;ECHO;} {return (WHILE);}

do {return (DO);}

PROGRAM {return (PROGRAM);}

end {return (END);} VAR {return (VAR);} if {return (IF);} then {return (THEN);} else {id}

%%

int panduan(double a) {if(a!=0) a=1;return a; }

int panduan2(double a) {if(a==0) a=1; else if

(a!=0) a=0; return a;}

int shuchu(double a) {if(a==0)printf(\else if (a!=0) printf(\return 1;}

运行程序：

{return (ELSE);} {return (ID);}

实验4：用Yacc设计语法分析器1

实验目的：学习如何使用Yacc设计一个语法分析器，并与用lex写的词法分析器链接起来。

实验内容：使用yacc为课程设计实验1所给的语言写一个语法分析器（你可以重新设计该语言的文法，但不能改变语言）。其中，词法分析使用课程设计实验2中已完成的词法分析器（即，你需要将本实验的语法分析器和实验2的词法分析器链接起来）。

实验要求：

输入为实验1所给语言写的源程序文件；输出为屏幕显示语法分析是否成功。 在语法分析中不能出现任何的冲突（移进-归约或归约-归约冲突），或者虽然有冲突，但是你能够说清楚冲突是如何解决的。

在cygwin下用flex，bison和gcc工具将实验调试通过，并且你写的语法分析器至少应该能通过例子parser0中testcases目录下的test0.p和test1.p两个测试例的测试。

实验参考：

可以在例子parser0的基础上进行修改；如果你尚不能将实验2的词法分析器和本实验的语法分析器链接起来，可以暂时使用parser0给出的词法分析器（前提是你的语法分析器中终结符名的定义与parser0的相同）。

程序代码：

Cal.y %{ int yylex();

#define YYSTYPE double /* 将Yacc栈定义为double类型 printf(\value of the expression is %lf.\\n\

%}

%token NUM LPAREN RPAREN ENTER %left OR %left AND

%right NOT

%left PLUS MINUS %left TIMES DIVIDE END %right UMINUS BEGIN VAR %nonassoc PROGRAM %union { int inum; double fnum; char * id; }

%%

/* 这样写prog可以让分析器每次读入一行进行分析，下一行重新分析expr prog : prog exprp | exprp

;

exprp : expr ENTER {printf(\表示 true；0 表示 false %lf.\\n\ ; expr : expr PLUS expr {$$ = $1 + $3;}

| expr MINUS expr {$$ = $1 - $3;} | expr TIMES expr {$$ = $1 * $3;} | expr DIVIDE expr {$$ = $1 / $3;} | LPAREN expr RPAREN {$$ = $2;} | MINUS expr {$$ = -$2;} | NUM {$$ = $1;}

| expr OR expr {$$=panduan($1*$1+$3*$3);} | expr AND expr {$$=panduan($1*$3);} | NOT expr {$$=panduan2($2);}

;*/

prog : PROGRAM biaoshifu fenpro |fenpro

|biaoshifu ; biaoshifu:ID

;

fenpro :blsm BEGIN yjb END |blsm {printf(\ |yjb {printf(\ ;

blsm: VAR blsmb {printf(\AR\ |blsmb ;

blsmb:blb MH leixing |blb MH leixing blsmb |blb |leixing

;

leixing:INTEGER {printf(\ |REAL {printf(\ ; blb:bl{$$ = $1;} |bl DH blb ;

bl:NUM {$$ = $1;} ; yjb:yj

|yj yjb ; yj:fzyj |tjyj |whileyj |fhyj ;

fzyj:bl FZ bds {$$ = $3;} |bl |bds ;

bds:guanxi {$$ = $1;} |suanshu {$$ = $1;} ;

tjyj:IF guanxi THEN yj ELSE yj |guanxi |yj ;

whileyj:WHILE guanxi DO yj {printf(\ |guanxi{printf(\ |yj ;

fhyj:BEGIN yjb END{printf(\ |yjb {printf(\

;

suanshu:xiang

|suanshu PLUS suanshu {$$ = $1 + $3;} |suanshu MINUS xiang{$$ = $1 - $3;} ;

xiang:yinshi

|xiang*yinshi{$$ = $1 * $3;} |xinag/yinshi{$$ = $1 / $3;} ;

yinshi:bl{$$ = $1;}

|NUM{$$ = $1;}

|LPAREN suanshu RPAREN {$$ = $2;} ;

guanxi:suanshu LT suanshu {$$=bijiao1($$1,$$3);} |suanshu GT suanshu {$$=bijiao2($$1,$$3);} |suanshu LQ suanshu {$$=bijiao3($$1,$$3);} |suanshu GQ suanshu {$$=bijiao4($$1,$$3);}

|suanshu EQ suanshu {$$=bijiao5($$1,$$3);} |suanshu NQ suanshu {$$=bijiao6($$1,$$3);} ; %%

int main(){ yyparse();

return 0; } Cal.l

%{

#include \#include int yywrap(void){ return 1; }

#define LT #define LE #define GT #define GE #define EQ #define NE

#define IF #define THEN

11

#define ELSE 12

#define WHILE #define DO

#define ID 20

#define RELOP 22

#define NEWLINE 23 #define ERRORCHAR 24 %}

ws [ \\t]+ digit

[0-9]

1 2 3 4 5 6

10 18 19

inum {digit}+

fnum {digit}*\\.{digit}+ letter [A-Za-z] id _|{letter}({letter}|{digit})* %s COMMENT %%

{inum} {sscanf(yytext, \{fnum} {sscanf(yytext, \\ \ \ \ \

{return PLUS;} {return TIMES;} {return MINUS;} {return DIVIDE;} {return LPAREN;}

\ {return RPAREN;}

\ {return OR;} \ {return AND;} \ {return NOT;} \

{return LT;}

\ {return LE;} \ {return GT;} \ {return GE;}

\ {return EQ;} \ {return NQ;} \ {return FZ;} \ {return MH;} \ {return DH;} \ {teturn FH;} {ws} \

{;}

{return ENTER;}

. {printf(\\ {BEGIN COMMENT;ECHO;} \while do

{BEGIN INITIAL;ECHO;} {return (WHILE);}

{return (DO);}

{return (PROGRAM);}

PROGRAM

end

{return (END);}

VAR {return (VAR);} if {return (IF);} then {return (THEN);}

else {id} %%

{return (ELSE);}

{return (ID);}

int panduan(double a) {if(a!=0) a=1;return a; }

int panduan2(double a) {if(a==0) a=1; else if

(a!=0) a=0; return a;}

int shuchu(double a) {if(a==0)printf(\else if (a!=0) printf(\return 1;}

int bijiao1(double a,double b) {if(a

int bijiao2(double a,double b) {if(a>b)return 1; else return -1; }

int bijiao3(double a,double b) {if(a<=b)return 1; else return -1; }

int bijiao4(double a,double b) {if(a>=b)return 1; else return -1; }

int bijiao5(double a,double b) {if(a==b)return 1;

else return -1;

}

int bijiao6(double a,double b) {if(a!=b)return 1; else return -1; }

实验5：用Yacc设计语法分析器2

实验目的：学习如何使用Lex和Yacc设计一个语法分析器，并学习如何在语法分析的同时生成分析树。

实验内容：修改实验4，给产生式加上动作，动作为生成一棵语法分析树。这棵分析树的结构可以使用或参照例子parser1中ast.h文件中定义的分析树结构。

实验要求：

输入为实验1所给语言写的源程序文件；输出为一棵语法分析树，这棵语法分析树的表示方法可以是这样两种：1.将分析树的数据结构打印出来；2.按分析树的结构输出一个C语言源程序文件（即输入是所给语言的源程序文件，输出为语义相同的C语言源程序文件）。

在cygwin下用flex，bison和gcc工具将实验调试通过，并且你写的语法分析器至少应该能通过例子parser1中testcases目录下的test0.p和test1.p两个测试例。

实验参考：

可以参考例子parser1或在它的基础上进行修改；如果你尚不能将实验2的词法分析器和本实验的语法分析器链接起来，可以暂时使用parser1给出的词法分析器（前提是你的语法分析器中终结符名的定义与parser1的相同）。你也可以在自己的语法分析器中直接使用parser1已经提供的输出方式（打印分析树的数据结构），但前提是你必须使用parser1提供的分析树结构（ast.h）。

程序代码：

%{

#include

#include \该文件定义了抽象语法树（分析树）的数据结构 #include \

#define YYDEBUG 1

/* 允许跟踪错误，与Tbug功能相同 */

int yylex(void); /* function prototype */

/* 该函数显示错误信息s，显示时包含了错误发生的位置。*/ void yyerror(char *s) {

EM_error(EM_tokPos, \

}

/* 存放抽象语法树中 \程序\数据结构的变量 */

a_prog program = NULL;

%}

/* 定义属性值栈的类型，实验8需要修改此处 */ %union {

int ival; double fval; string sval;

a_exp exp; a_bexp bexp; a_stm_list stms; a_prog prog; a_dec_list decl; }

/* 定义各个终结符，以及他们的属性值的类型，实验8需要修改此处 */ %token ID /* id */

%token INT /*整型数*/ %token FLOAT /*浮点数*/

%token INTEGER REAL /*两种类型名：整型、实型*/

%token

COMMA COLON SEMICOLON LPAREN RPAREN PERIOD /* 符号 , : ; ( ) . */

PROGRAM BEGINN END VAR IF WHILE DO /* 关键字：PROGRAM BEGIN END VAR IF WHILE Do */

THEN ELSE /* 关键字：THEN ELSE */

ASSIGN EQ NEQ LT LE GT GE /* 符号 := = <> < <= > >= */ PLUS MINUS TIMES DIVIDE /* 符号 + = * / */ %start program

/* 定义各个非终结符的属性值类型，实验8需要修改此处 */ %type program

%type bianliangbiao declist vardec

%type fuhe xunhuan tiaojian fuzhi yuju stmts %type exp yinshi xiang suanshu %type guanxi %% program :

PROGRAM ID SEMICOLON vardec BEGINN stmts END PERIOD

{program = A_Prog(EM_tokPos, $2, $4, $6);} ;

vardec : VAR declist {$$ = $2;} ;

declist : bianliangbiao COLON INTEGER SEMICOLON {$$ = A_DecList(A_VarDec(EM_tokPos, $1, T_int), NULL);}

| bianliangbiao COLON INTEGER SEMICOLON declist {$$ = A_DecList(A_VarDec(EM_tokPos, $1, T_int), $5);}

| bianliangbiao COLON REAL SEMICOLON

{$$ = A_DecList(A_VarDec(EM_tokPos, $1, T_real), NULL);}

| bianliangbiao COLON REAL SEMICOLON declist {$$ = A_DecList(A_VarDec(EM_tokPos, $1, T_real), $5);} ;

bianliangbiao : ID {$$ = A_VarList(A_Id(EM_tokPos, $1), NULL);}

| ID COMMA bianliangbiao {$$ = A_VarList(A_Id(EM_tokPos, $1), $3);} ;

stmts : yuju {$$ = A_StmList($1,NULL);}

| yuju SEMICOLON stmts {$$ = A_StmList($1,$3);} ;

yuju : fuzhi {$$ = $1;} | tiaojian {$$ = $1;} | xunhuan {$$ = $1;} | fuhe {$$ = $1;} ;

fuzhi : ID ASSIGN suanshu {$$ = A_Assign(EM_tokPos, A_Id(EM_tokPos, $1), $3);} ;

tiaojian : IF guanxi THEN yuju ELSE yuju {$$ = A_If(EM_tokPos, $2, $4, $6);}

;

xunhuan : WHILE guanxi DO yuju {$$ = A_While(EM_tokPos, $2, $4);} ;

fuhe : BEGINN stmts END {$$ = A_Seq(EM_tokPos, $2);} ;

suanshu : xiang {$$ = $1;}

| suanshu PLUS xiang {$$ = A_OpExp(EM_tokPos, A_plusOp, $1, $3);} | suanshu MINUS xiang{$$ = A_OpExp(EM_tokPos, A_minusOp, $1, $3);} ;

xiang : yinshi {$$ = $1;}

| xiang TIMES yinshi {$$ = A_OpExp(EM_tokPos, A_timesOp, $1, $3);} | xiang DIVIDE yinshi {$$ = A_OpExp(EM_tokPos, A_divideOp, $1, $3);} ;

yinshi : ID {$$ =A_VarExp(EM_tokPos, $1);} | INT {$$ = A_IntExp(EM_tokPos, $1);} | FLOAT {$$ = A_RealExp(EM_tokPos, $1);} ;

/*EQ NEQ LT LE GT GE*/

guanxi : suanshu EQ suanshu{$$ = A_BExp(EM_tokPos, A_eqOp, $1, $3);} | suanshu NEQ suanshu{$$ = A_BExp(EM_tokPos, A_neqOp, $1,

$3);} | suanshu LT suanshu{$$ = A_BExp(EM_tokPos, A_ltOp, $1, $3);} | suanshu LE suanshu{$$ = A_BExp(EM_tokPos, A_leOp, $1, $3);} | suanshu GT suanshu{$$ = A_BExp(EM_tokPos, A_gtOp, $1, $3);} | suanshu GE suanshu{$$ = A_BExp(EM_tokPos, A_geOp, $1,

$3);} ; exp : INT {$$ = A_IntExp(EM_tokPos, $1);} | FLOAT {$$ = A_RealExp(EM_tokPos, $1);} ;

词法分析器用老师所给的lex.yy.c，并修改ast.c Ast.c文件：

#include \ /* make id node */

a_id A_Id(a_pos pos, string val){

a_id ret = checked_malloc(sizeof(*ret)); ret->pos = pos; ret->val = val; return ret; }

/* make exp node from integer */ a_exp A_IntExp(a_pos pos, int ival){ a_exp ret = checked_malloc(sizeof(*ret)); ret->kind = A_intExp; ret->pos = pos; ret->exp.ival = ival; return ret; }

/* make exp node from real */

本文来源：https://www.bwwdw.com/article/v9ph.html