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工程六、设计思路及过程设计流程：词法分析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定义的文法中将<iValue>与INTEGER，<sIndex>与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 <stdlib.h>#include "node.h"#include "myparser.h"void yyerror(char *);%}%%"/*"([^\*]|(\*)*[^\*/])*(\*)*"*/" ;"while" {return WHILE;}"if" {return IF;}"else" {return ELSE;}"print" {return PRINT;}"false" {yylval.iValue = 0;return INTEGER;}"true" {yylval.iValue = 1;return INTEGER;}[a-z] {yylval.sIndex = *yytext - 'a';return VARIABLE;}[0-9]+ {yylval.iValue = atoi(yytext);return INTEGER;}[-()<>=+*/%;{}.] {return *yytext;}">=" {return GE;}"<=" {return LE;}"==" {return EQ;}"!=" {return NE;}"<>" {return NE;}"&&" {return AND;}"||" {return OR;}"!" {return NOT;}[ \t\n]+ ; /* 去除空格，回车*/. printf("unknow symbol:[%s]\n",yytext);%%int yywrap(void){return 1;}myparser.y文件如下：%{#include <stdio.h>#include <stdlib.h>#include <stdarg.h>#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 <iValue> VARIABLE%token <sIndex> INTEGER%token WHILE IF PRINT%nonassoc IFX%nonassoc ELSE%left AND OR GE LE EQ NE '>' '<'%right NOT%left '+' '-'%left '*' '/' '%'%nonassoc UMINUS%type <nPtr> 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->op.num = num;va_start(valist, num);for (i = 0; i < num; i++)p->op.node[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->op.num; i++)freeNode(p->op.node[i]);}free (p);}void yyerror(char *s){fprintf(stdout, "%s\n", 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];七、运行结果及测试程序。