编译原理课程设计报告

PAGEPAGE13《编译原理》课程设计报告姓名：学号：班级：专业：指导教师：时间：项目名称：贵州大学计算机科学与信息学院目录一．课程设计目的┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅2二．课程设计题目描述和要求┅┅┅┅┅┅┅┅┅┅┅┅┅┅21、选定的题目┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅22、课程设计要求描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅23、实现的功能描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅24、分析器的使用描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅3三．课程设计实现描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅41、实现平台┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅42、课程设计基本思路描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅43、LR分析器基本原理描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅54、代码描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅55、演示分析┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅11四．课程设计总结┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅11五．参考书目┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅11

一、课程设计目的课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。二、课程设计题目描述和要求2.1选定的题目：基本语句的语法分析程序设计2.2课程设计的要求描述：要求:每个同学在所给的题目（课程设计一、二、三）中自选一个实现。学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。设计时间：第18周1周。开发工具：Windows环境下使用TurboC；Windows环境下使用VisualC++。其它熟悉语言。2.3课程设计的内容描述：2.3.1设计题一：算术表达式的语法分析及语义分析程序设计。目的通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。设计内容及要求：算术表达式的文法：〈无符号整数〉∷＝〈数字〉{〈数字〉}〈标识符〉∷＝〈字母〉{〈字母〉｜〈数字〉}〈表达式〉∷＝〈项〉{〈加法运算符〉〈项〉}〈项〉∷＝〈因子〉{〈乘法运算符〉〈因子〉}〈因子〉∷＝〈标志符〉｜〈无符号整数〉〈加法运算符〉∷＝＋｜－〈乘法运算符〉∷＝＊｜／〈字母〉∷＝a|b|…|z〈数字〉∷＝0|1|…|9要求：在递归下降法、LL（1）、算符优先分析法或者LR法中选择其中一种方法完成以上任务，中间代码选用四元式。编制分析程序，设计若干用例，并上机测试。书写课程设计报告。2.3.2设计题二：布尔表达式的语法分析及语义分析程序设计。目的通过设计、编制、调试一个布尔表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。设计内容及要求布尔表达式的文法：〈无符号整数〉∷＝〈数字〉{〈数字〉}〈标识符〉∷＝〈字母〉{〈字母〉｜〈数字〉}〈表达式〉∷＝〈项〉{〈逻辑运算符〉〈项〉}〈项〉∷＝〈因子〉{〈关系运算符〉〈因子〉}〈因子〉∷＝〈标志符〉｜〈无符号整数〉〈逻辑运算符〉∷＝AND〈乘法运算符〉∷＝>｜>=|<|<=|==|!=〈字母〉∷＝a|b|…|z〈数字〉∷＝0|1|…|9要求：（1）在递归下降法、LL（1）、算符优先分析法或者LR法中选择其中一种方法完成以上任务，中间代码选用四元式。（2）编制分析程序，设计若干用例，并上机测试。（3）书写课程设计报告2.3.3设计题三：程序基本语句的语法分析程序设计。目的通过设计、编制、调试词法及语法分析程序，加深对词法及语法分析原理的理解。设计内容及要求基本语句：S→while(C)S;if(C)S1elseS2;id=E;{S}ε其中：（1）id为变量，变量名满足由字母、数字构成，并且由字母开头的字符串构成。（2）运算中的数全部是无符号整型数据；（3）表达式E中的运算符只有+和-；（4）关系运算表达式C中的运算符只涉及==（相等）和！=（不等）。并且在一个关系运算中只涉及其中的一个运算。要求：（1）在递归下降法、LL（1）或者LR法中选择其中一种方法完成以上任务。（2）编制分析程序，设计若干用例，并上机测试。（3）书写课程设计报告。2.3.4yacc语言的语法规则的简单描述：任何一个高级语言都需要有一个编译程序或解释程序，目的是将高级语言的源程序翻译成能被机器识别的目标程序,编译程序所要完成的工作通常划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等阶段,编译程序的编制是一个非常复杂的过程，为了减轻编译程序设计人员的工作量随着软件开发自动化技术的提高，出现了一些编译程序的构造工具。YACC就是一个语法分析程序的自动产生器可以处理用LALR(1)文法表示的上下文无关语言,YACC的全称是YetAnotherCompilerCompiler(另一种编译程序的编译程序)是1975年由Johnson开发的,它接受一个用BNF描述的上下文无关语言的语法规则自动生成LALR(1)分析器yyparse,YACC可与词法分析器LEX联合使用借助LEX完成词法分析的任务并在YACC源程序中调用yylex(),YACC的工作示意图如图1所示,YACC源程序可分为三个部分格式为说明部分%%语法规则部分%%程序段部分说明部分用来定义语法规则中要用的终结符号、语义动作中使用的数据类型、变量以及语法规则中运算符的优先级等语法规则部分用来定义所要处理的语言的语法规则以及相应的语义动作格式为:非终结符:替换规则{语义动作};其中替换规则是由终结符和非终结符组成的字符串语义动作用C语言来书写对于左部非终结符相同的语法规则可将它们集中在一起规则间用“|”分隔，最后一条规则之后才用分号“；”。程序段部分主要包括主程序main()、错误信息执行程序yyerror()、词法分析程序yylex()、用户在语义动作中用到的子程序等三、课程设计实现描述3.1实现平台Windous7Visualstudio20103.2课程设计的基本思路描述while循环语句的文法描述S®WdS(1)Wd®W(E)W®while。if的语句的文法描述S®CS(1)C®if(E)S®TpS(2)TP®CS(1)；else。我们用ParserGenerator的Project-->ParserWizard创建一个工程，如下图所示，注意红圈部分的设置：然后选择默认文件YACCandLexfile，模板如下：其余按默认完成即可：这时，我们可以看到ParserGenerator帮我们自动生成了一个myparser.y文件和mylexer.l文件，语法规则就可以在这两个文件里面添加了。添加的语法规则分别如下：myparser.y里添加的语法规则如下：%{#include"struct.h"#include<stdlib.h>#include<string.h>intnxq=100;intline=0;charstring[64];voidbackpatch(int,int);voidemit(char*,char*,char*,char*);char*newtemp();%}%union{ char*text; structwdattri*wdas; structeattri*eas; }%tokenWHILE%tokenIF%token<text>NUMBER%token<text>NAME%left'+''-'%left'*''/'%type<text>expr%type<wdas>s%type<wdas>wd%type<wdas>wf%type<eas>bexpr%type<wdas>w%type<wdas>assign%%s:wds {backpatch($2->chain,$1->quad);itoa($1->quad,string,10);emit("j","_","_",string);$$->chain=$1->quad;} |wfs{backpatch($2->chain,$1->quad);itoa($1->quad,string,10); emit("j","_","_",string);} |assign {$$=(structwdattri*)malloc(sizeof(structwdattri)); $$->chain=$1->chain;};w:WHILE {$$=(structwdattri*)malloc(sizeof(structwdattri)); $$->quad=nxq;} ;wd:w'('bexpr')' {backpatch($3->tc,nxq); $$=(structwdattri*)malloc(sizeof(structwdattri)); $$->chain=$3->fc;$$->quad=$1->quad;} ;wf:IF'('bexpr')'{backpatch($3->tc,nxq);$$=(structwdattri*)malloc(sizeof(structwdattri));$$->chain=$3->fc;};assign:NAME'='expr {emit("=",$3,"_",$1);$$->chain=nxq;} ;expr:expr'+'expr {$$=newtemp();emit("+",$1,$3,$$);}|expr'-'expr {$$=newtemp();emit("-",$1,$3,$$);}|expr'*'expr {$$=newtemp();emit("*",$1,$3,$$);}|expr'/'expr {$$=newtemp();emit("/",$1,$3,$$);}|NUMBER {$$=$1;}|NAME {$$=$1;} ;bexpr:expr'>'expr {$$=(structeattri*)malloc(sizeof(structeattri)); $$->tc=nxq; $$->fc=nxq+1;emit("j",$1,$3,"0");emit("j","_","_","0");} |expr'<'expr{emit("j",$1,$3,"0");emit("j","_","_","0");} |expr'='expr{emit("j",$1,$3,"0");emit("j","_","_","0");} ;%%voidbackpatch(intchain,intquad){ inti; charstring[64]; for(i=0;i<line+1;i++) if(code[i].no==chain) { itoa(quad,string,10); code[chain].res=strdup(string);}}voidemit(char*com1,char*com2,char*com3,char*com4){ code[line].no=nxq; code[line].op=strdup(com1); code[line].arg1=strdup(com2); code[line].arg2=strdup(com3); code[line].res=strdup(com4); line++; nxq++;}char*newtemp(){ staticintno=1; char*s; s=(char*)malloc(sizeof(char)*10); sprintf(s,"t%d",no); no++; returns;}main(){ inti; yyparse(); for(i=0;i<line;i++) printf("