编译原理实验报告1

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 "node.h"

#include "myparser.h"

void yyerror(char *);

%}

%%

"/*"([^*]|(*)*[^*/])*(*)*"*/" ;

"while" {return WHILE;}

"if" {return IF;}

"else" {return ELSE;}

"print" {return PRINT;}

"false" { = 0;

return INTEGER;

}

"true" { = 1;

return INTEGER;

}

[a-z] { = *yytext - 'a';

return VARIABLE;

}

[0-9]+ { = atoi(yytext);

return INTEGER;

}

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

">=" {return GE;}

"<=" {return LE;}

"==" {return EQ;}

"!=" {return NE;}

"<>" {return NE;}

"&&" {return AND;}

"||" {return OR;}

"!" {return NOT;}

[ tn]+ ; /* 去除空格，回车 */

. printf("unknow symbol:[%s]n",yytext);

%%

int yywrap(void)

{

return 1;

}

myparser.y文件

如下：

%{

#include

#include

#include

#include "node.h"

/* 属性操作类型 */

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:

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

| expr ';' { $$ = $1; }

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

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

| 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 { $$ = opr(IF, 3, $3, $5, $7); }

| '{' stmt_list '}' { $$ = $2; }

;

stmt_list:

stmt { $$ = $1; }

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

;

expr:

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

| VARIABLE { $$ = set_index($1); }

| expr '+' expr { $$ = opr('+', 2, $1, $3); }

| expr '-' expr { $$ = opr('-', 2, $1, $3); }

| expr '*' expr { $$ = opr('*', 2, $1, $3); }

| expr '/' expr { $$ = opr('/', 2, $1, $3); }

| expr '%' expr { $$ = opr('%', 2, $1, $3); }

| expr '<' expr { $$ = opr('<', 2, $1, $3); }

| expr '>' expr { $$ = opr('>', 2, $1, $3); }

| expr GE expr { $$ = opr(GE, 2, $1, $3); }

| expr LE expr { $$ = opr(LE, 2, $1, $3); }

| expr NE expr { $$ = opr(NE, 2, $1, $3); }

| expr EQ expr { $$ = opr(EQ, 2, $1, $3); }

| expr AND expr { $$ = opr(AND, 2, $1, $3); }

| expr OR expr { $$ = opr(OR, 2, $1, $3); }

| NOT expr { $$ = opr(NOT, 1, $2); }

| '-' expr %prec UMINUS { $$ = opr(UMINUS, 1, $2); }

| '(' expr ')' { $$ = $2; }

;

%%

#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("out of memory");

/* 复制内容 */

p->type = TYPE_CONTENT;

p->content = value;

return p;

}

Node *set_index(int value)

{

Node *p;

size_t sizeNode;

/* 分配结点空间 */

sizeNode = SIZE_OF_NODE + sizeof(int);

if ((p = malloc(sizeNode)) == NULL)

yyerror("out of memory");

/* 复制内容 */

p->type = TYPE_INDEX;

p->index = value;

return p;

}

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

{

va_list valist;

Node *p;

size_t sizeNode;

int i;

/* 分配结点空间 */

sizeNode = SIZE_OF_NODE + sizeof(OpNode) + (num - 1) * sizeof(Node*);

if ((p = malloc(sizeNode)) == NULL)

yyerror("out of memory");

/* 复制内容 */

p->type = TYPE_OP;

p-> = name;

p-> = num;

va_start(valist, num);

for (i = 0; i < num; i++)

p->[i] = va_arg(valist, Node*);

va_end(valist);

return p;

}

void freeNode(Node *p)

{

int i;

if (!p) return;

if (p->type == TYPE_OP)

{

for (i = 0; i < p->; i++)

freeNode(p->[i]);

}

free (p);

}

void yyerror(char *s)

{

fprintf(stdout, "%sn", s);

}

int main(void)

{

yyparse();

return 0;

}

定义结点如下：

union tagYYSTYPE {

int iValue; /* 变量值 */

char sIndex; /* 变量数组索引 */

Node *nPtr; /* 结点地址 */

};

extern YYSTYPE YYNEAR yylval;

在本程序中，还有自定义的头文件node.h如下：

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];

七、 运行结果及测试程序