编译原理实验报告

上机题目：实现一个简单语言（CPL）的编译器（解释器）功能要求：接收以CPL编写的程序，对其进行词法分析、语法分析、语法制导翻译等，然后能够正确的执行程序。试验目的加深编译原理基础知识的理解：词法分析、语法分析、语法制导翻译等加深相关基础知识的理解：数据结构、操作系统等提高编程能力锻炼独立思考和解决问题的能力题目说明数据类型：整型变量（常量），布尔变量（常量）取值范围{…,-2,-1,0,1,2,…},{true,false}2、运算表达式：简单的代数运算，布尔运算3、程序语句：赋值表达式，顺序语句，if-else语句，while语句环境配置安装ParserGenerator、VisualC++；分别配置ParserGenerator、VisualC++；使用ParserGenerator创建一个工程编写l文件mylexer.l；编译mylexer.l，生成mylexer.h与mylexer.c；使用VC++创建Win32ConsoleApplication工程并配置该项目； 加入mylexer.h与mylexer.c，编译工程；执行标识符数字识别器；注意：每次修改l文件后，需要重新编译l文件，再重新编译VC工程设计思路及过程设计流程：YACC预定义文法YACC预定义文法BNF递归文法BNF递归文法扩展实现函数扩展实现函数词法分析LEX的此法分析部分主要利用有限状态机进行单词的识别，在分析该部分之前，首先应该对YACC的预定义文法进行解释。在YACC中用%union扩充了yystype的内容，使其可以处理char型，int型，node型，其中Node即为定义的树形结点，其定义如下：typedefenum{TYPE_CONTENT,TYPE_INDEX,TYPE_OP}NodeEnum;/*操作符*/typedefstruct{intname;/*操作符名称*/intnum;/*操作元个数*/structNodeTag*node[1];/*操作元地址可扩展*/}OpNode;typedefstructNodeTag{NodeEnumtype;/*树结点类型*//*Union必须是最后一个成员*/union{intcontent;/*内容*/intindex;/*索引*/OpNodeop;/*操作符对象*/};}Node;externintVar[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这个扩展函数很重要，而且使用了动态参数，主要考虑操作符的操作元个数是可变的，这个也与头文件“structNodeTag*node[1];”的定义思想一致。opr主要在内存空间中分配操作符相关的树结点。Set_index,set_value,opr从概念上是完全一致的，目的就是在内存中构造一颗可以递归的语法树。程序代码mylexer.l文件如下：%{#include<stdlib.h>#include"node.h"#include"myparser.h"voidyyerror(char*);%}%%"/*"([^\*]|(\*)*[^\*/])*(\*)*"*/" ;"while" {returnWHILE;}"if" {returnIF;}"else" {returnELSE;}"print" {returnPRINT;}"false" {yylval.iValue=0;returnINTEGER;}"true" {yylval.iValue=1;returnINTEGER;}[a-z] {yylval.sIndex=*yytext-'a';returnVARIABLE;}[0-9]+ {yylval.iValue=atoi(yytext);returnINTEGER;}[-()<>=+*/%;{}.] {return*yytext;}">=" {returnGE;}"<=" {returnLE;}"==" {returnEQ;}"!=" {returnNE;}"<>" {returnNE;}"&&" {returnAND;}"||" {returnOR;}"!" {returnNOT;}[\t\n]+;/*去除空格，回车*/. printf("unknowsymbol:[%s]\n",yytext);%%intyywrap(void){return1;}myparser.y文件如下：%{#include<stdio.h>#include<stdlib.h>#include<stdarg.h>#include"node.h"/*属性操作类型*/Node*opr(intname,intnum,...);Node*set_index(intvalue);Node*set_content(intvalue);voidfreeNode(Node*p);intexeNode(Node*p);intyylexeNode(void);voidyyerror(char*s);intVar[26];/*变量数组*/%}%union{ intiValue;/*变量值*/ charsIndex;/*变量数组索引*/ Node*nPtr;/*结点地址*/}%token<iValue>VARIABLE%token<sIndex>INTEGER%tokenWHILEIFPRINT%nonassocIFX%nonassocELSE%leftANDORGELEEQNE'>''<'%rightNOT%left'+''-'%left'*''/''%'%nonassocUMINUS%type<nPtr>stmtexprstmt_list%%program: function {exit(0);} ;function: functionstmt {exeNode($2);freeNode($2);} | /*NULL*/ ;stmt: ';' {$$=opr(';',2,NULL,NULL);} |expr';' {$$=$1;} |PRINTexpr';' {$$=opr(PRINT,1,$2);} |VARIABLE'='expr';' {$$=opr('=',2,set_index($1),$3);} |WHILE'('expr')'stmt {$$=opr(WHILE,2,$3,$5);} |IF'('expr')'stmt%precIFX {$$=opr(IF,2,$3,$5);} |IF'('expr')'stmtELSEstmt%precELSE {$$=opr(IF,3,$3,$5,$7);} |'{'stmt_list'}' {$$=$2;} ;stmt_list: stmt {$$=$1;} |stmt_liststmt {$$=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);} |exprGEexpr {$$=opr(GE,2,$1,$3);} |exprLEexpr {$$=opr(LE,2,$1,$3);} |exprNEexpr {$$=opr(NE,2,$1,$3);} |exprEQexpr {$$=opr(EQ,2,$1,$3);} |exprANDexpr {$$=opr(AND,2,$1,$3);} |exprORexpr {$$=opr(OR,2,$1,$3);} |NOTexpr {$$=opr(NOT,1,$2);} |'-'expr%precUMINUS {$$=opr(UMINUS,1,$2);} |'('expr')' {$$=$2;} ;%%#defineSIZE_OF_NODE((char*)&p->content-(char*)p)Node*set_content(intvalue){ Node*p; size_tsizeNode; /*分配结点空间*/ sizeNode=SIZE_OF_NODE+sizeof(int); if((p=malloc(sizeNode))==NULL) yyerror("outofmemory"); /*复制内容*/ p->type=TYPE_CONTENT; p->content=value; returnp;}Node*set_index(intvalue){ Node*p; size_tsizeNode; /*分配结点空间*/ sizeNode=SIZE_OF_NODE+sizeof(int); if((p=malloc(sizeNode))==NULL) yyerror("outofmemory"); /*复制内容*/ p->type=TYPE_INDEX; p->index=value; returnp;}Node*opr(intname,intnum,...){ va_listvalist; Node*p; size_tsizeNode; inti; /*分配结点空间*/ sizeNode=SIZE_OF_NODE+sizeof(OpNode)+(num-1)*sizeof(Node*); if((p=malloc(sizeNode))==NULL) yyerror("outofmemory"); /*复制内容*/ 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); returnp;}voidfreeNode(Node*p){ inti; if(!p)return; if(p->type==TYPE_OP) { for(i=0;i<p->op.num;i++) freeNode(p->op.node[i]);