编译原理实验报告1

更新时间：2024-06-11 03:43:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

03091337 李璐 03091339 宗婷婷

一、上机题目：实现一个简单语言（CPL）的编译器（解释器）二、功能要求：接收以CPL编写的程序，对其进行词法分析、语法分

析、语法制导翻译等，然后能够正确的执行程序。

三、试验目的

1. 加深编译原理基础知识的理解：词法分析、语法分析、语法制导

翻译等

2. 加深相关基础知识的理解：数据结构、操作系统等 3. 提高编程能力

4. 锻炼独立思考和解决问题的能力

四、题目说明

1. 数据类型：整型变量（常量），布尔变量（常量）

取值范围{?, -2, -1, 0, 1, 2, ?}, {true, false}

2、运算表达式：简单的代数运算，布尔运算

3、程序语句：赋值表达式，顺序语句，if-else语句，while语句

五、环境配置

1. 安装Parser Generator、Visual C++；

2. 分别配置Parser Generator、Visual C++； 3. 使用Parser Generator创建一个工程

编写l文件mylexer.l；

编译mylexer.l，生成mylexer.h与mylexer.c；

4. 使用VC++创建Win32 Console Application工程并

配置该项目；加入mylexer.h与mylexer.c，编译工程；执行标识符数字识别器；

注意：每次修改l文件后，需要重新编译l文件，再重新编译VC工程

六、设计思路及过程

设计流程：

YACC预定义文法

BNF递归文法

扩展实现函数

? 词法分析

LEX的此法分析部分主要利用有限状态机进行单词的识别，在分析该部分之前，首先应该对YACC的预定义文法进行解释。在YACC中用%union扩充了yystype的内容，使其可以处理char型，int型，node型，其中Node即为定义的树形结点，其定义如下： typedef enum { TYPE_CONTENT, TYPE_INDEX, TYPE_OP } NodeEnum;

/* 操作符 */ typedef struct {

int name; /* 操作符名称 */ int num; /* 操作元个数 */

struct NodeTag * node[1]; /* 操作元地址可扩展 */ } OpNode;

typedef struct NodeTag {

NodeEnum type; /* 树结点类型 */ /* Union 必须是最后一个成员 */ union {

int content; /* 内容 */ int index; /* 索引 */

OpNode op; /* 操作符对象 */ };

} Node;

extern int Var[26];

结点可以是三种类型(CONTENT,INDEX,OP)。结点如果是操作符对象(OpNode)的话，结点可继续递归结点。操作符结点包括了名称，个数和子结点三个要素，其中子结点可以为多个。

在YACC定义的文法中将与INTEGER，与VARIABLE绑定，表示对lex返回的值自动进行类型转换。 ? YACC的语法分析和语义制导

在YACC中首先定义了与函数相关的文法和与运算相关的文法，其中函数定义的文法中可以处理if-else,if,while,print,x=exp;类型，在与运算相关的文法中可以处理+，-，*，/,>,<,>=,<=,!==,&&,||运算。在语义制导翻译部分主要目的是在内存建立一颗语法树来实现刚才所说的函数。扩展了set_index,set_value两个赋值语句，其操作实质是在内存空间分配index和value的两种树结点。opr这个扩展函数很重要，而且使用了动态参数，主要考虑操作符的操作元个数是可变的，这个也与头文件“struct NodeTag * node[1];”的定义思想一致。opr主要在内存空间中分配操作符相关的树结点。Set_index,set_value,opr从概念上是完全一致的，目的就是在内存中构造一颗可以递归的语法树。

程序代码

mylexer.l文件如下：

#include #include \#include \void yyerror(char *);

\; \ {return WHILE;} \ \

{return IF;} {return ELSE;}

{return PRINT;} {yylval.iValue = 0;

return INTEGER; \ return INTEGER; }

[a-z] {yylval.sIndex = *yytext - 'a'; return VARIABLE; }

[0-9]+

{yylval.iValue = atoi(yytext); {yylval.iValue = 1;

return INTEGER; }

[-()<>=+*/%;{}.]

\\\\ \\\\

{return *yytext;}

{return GE;} {return LE;} {return EQ;} {return NE;} {return NE;} {return AND;} {return OR;} {return NOT;}

[ \\t\\n]+ ; /* 去除空格，回车 */ .

printf(\

int yywrap(void) { return 1; }

myparser.y文件如下：

#include #include #include #include \

/* 属性操作类型 */

Node *opr(int name, int num, ...);

Node *set_index(int value); Node *set_content(int value);

void freeNode(Node *p); int exeNode(Node *p); int yylexeNode(void); void yyerror(char *s);

int Var[26]; /* 变量数组 */ %}

%union { int iValue; /* 变量值 */ char sIndex; /* 变量数组索引 */ Node *nPtr; /* 结点地址 */ }

%token VARIABLE %token INTEGER %token WHILE IF PRINT %nonassoc IFX %nonassoc ELSE

%left AND OR GE LE EQ NE '>' '<' %right NOT %left '+' '-' %left '*' '/' '%' %nonassoc UMINUS

%type stmt expr stmt_list %%

program: function

{ exit(0); }

; function: function stmt

{ exeNode($2); freeNode($2); }

| ;

/* NULL */

stmt:

';' | expr ';'

{ $$ = opr(';', 2, NULL, NULL); } { $$ = $1; }

{ $$ = opr(PRINT, 1, $2); }

{ $$ = opr('=', 2, set_index($1), $3); }

| PRINT expr ';' | VARIABLE '=' expr ';'

| WHILE '(' expr ')' stmt { $$ = opr(WHILE, 2, $3, $5); } | IF '(' expr ')' stmt %prec IFX { $$ = opr(IF, 2, $3, $5); } | IF '(' expr ')' stmt ELSE stmt %prec ELSE | '{' stmt_list '}' ;

{ $$ = $1; }

{ $$ = opr(';', 2, $2, $1); }

{ $$ = $2; }

{ $$ = opr(IF, 3, $3, $5, $7); }

stmt_list:

stmt

| stmt_list stmt ;

INTEGER | VARIABLE

expr: %%

{ $$ = set_content($1); } { $$ = set_index($1); }

{ $$ = opr('+', 2, $1, $3); } { $$ = opr('-', 2, $1, $3); } { $$ = opr('*', 2, $1, $3); } { $$ = opr('/', 2, $1, $3); } { $$ = opr('%', 2, $1, $3); } { $$ = opr('<', 2, $1, $3); } { $$ = opr('>', 2, $1, $3); } { $$ = opr(GE, 2, $1, $3); } { $$ = opr(LE, 2, $1, $3); } { $$ = opr(NE, 2, $1, $3); } { $$ = opr(EQ, 2, $1, $3); } { $$ = opr(AND, 2, $1, $3); } { $$ = opr(OR, 2, $1, $3); } { $$ = opr(NOT, 1, $2); } { $$ = opr(UMINUS, 1, $2); } { $$ = $2; }

| NOT expr | '-' expr %prec UMINUS | '(' expr ')' ;

#define SIZE_OF_NODE ((char *)&p->content - (char *)p)

Node *set_content(int value) {

Node *p;

size_t sizeNode;

/* 分配结点空间 */

sizeNode = SIZE_OF_NODE + sizeof(int); if ((p = malloc(sizeNode)) == NULL) yyerror(\ }

Node *set_index(int value) {

Node *p;

size_t sizeNode;

/* 分配结点空间 */

sizeNode = SIZE_OF_NODE + sizeof(int); if ((p = malloc(sizeNode)) == NULL) /* 复制内容 */