(重庆理工大学计算机学院)编译原理课程设计报告

《编译原理》课程设计报告一、课程设计目的通过课程设计进一步理解高级语言在计算机中的执行过程，了解现代编译器的运作机制，加深对编译原理中重点算法和编译技术的理解，提高自己自学和理解的能力。

学会如何利用已有软件JFLex、Java_cup对词法分析器及语法分析器的构造。

二、设计概述本tiger语言编译器的编译过程涉及到编译五个阶段中的二个，即词法分析器、语法分析器。

其中语法分析后还完成了语法树的打印的构造以及类型检查。

词法分析器由JFLex编译正则式生成，词法分析器编译产生式生成，语法分析器由CUP生成。

结果通过GUI界面呈现在使用者面前。

编译程序需要在单词级别上来分析和翻译源程序，所以首先要识别出单词，而词法分析部分的任务是：从左至右扫描源程序的字符串，按照词法规则（正则文法规则）识别出一个个正确的单词，并转换成该单词相应的二元式（种别码、属性值）交给语法分析使用。

因此，词法分析是编译的基础。

执行词法分析的程序称为词法分析器。

语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。

三、设计过程(一)设计构思程序主要完成三大功能模块：词法分析器、语法分析器、GUI人机交互界面。

词法分析器由JFLex编译正则式生成，其中必须为外界提供一个获取记号流的接口，实验中定为java_cup.runtime.Symbol next_token。

语法分析器是建立在词法分析器上的，故必须包含词法分析器以便获得记号流，next_token为语法分析器提供TOKEN，语法分析器的对外接口是：java_cup.runtime.Symbol debug_parse()，同时返回语法树的根节点。

GUI 界面是提供人机交互的，它能够依次显示词法分析阶段分析得到的所有TOKEN 的信息，语法阶段生成的语法树，另外对于词法和语法阶段出现的错误在“错误提示”文本框中一一列举出来，提供用户改进代码的信息。

2011-2012学年第二学期《编译原理》课程设计报告学院：计算机科学与工程学院班级：学生姓名：学号：成绩：指导教师：时间：2012年5 月目录一、课程设计的目的 ---------------------------------------------------------------- - 1 -二、课堂实验及课程设计的内容 -------------------------------------------------- - 1 -2.1、课堂实验内容-------------------------------------------------------------- - 1 -2.2、课程设计内容-------------------------------------------------------------- - 1 -三、visual studio 2008 简介------------------------------------------------------- - 2 -四、问题分析及相关原理介绍 ----------------------------------------------------- - 3 -4.1、实验部分问题分析及相关原理介绍 ---------------------------------- - 3 -4.1.1、词法分析功能介绍及分析------------------------------------- - 3 -4.1.2、语法分析功能介绍及分析------------------------------------- - 3 -4.1.3、语义分析功能介绍及分析------------------------------------- - 4 -4.2、课程设计部分问题分析及相关原理介绍 ---------------------------- - 5 -4.2.1、编译程序介绍 ----------------------------------------------------- - 5 -4.2.2、对所写编译程序的源语言的描述（C语言） -------------- - 6 -4.2.3、各部分的功能介绍及分析 -------------------------------------- - 7 -4.3、关键算法：单词的识别-------------------------------------------------- - 8 -4.3.1、算法思想介绍 ----------------------------------------------------- - 8 -4.3.2、算法功能及分析 -------------------------------------------------- - 8 -五、设计思路及关键问题的解决方法 ------------------------------------------ - 10 -5.1、编译系统------------------------------------------------------------------ - 10 -5.1.1、设计思路 --------------------------------------------------------- - 10 -5.2、词法分析器总控算法--------------------------------------------------- - 12 -5.2.1、设计思路 --------------------------------------------------------- - 12 -5.2.2、关键问题及其解决方法 --------------------------------------- - 13 -六、结果及测试分析-------------------------------------------------------------- - 14 -6.1、软件运行环境及限制--------------------------------------------------- - 14 -6.2、测试数据说明------------------------------------------------------------ - 14 -6.3、运行结果及功能说明--------------------------------------------------- - 16 -6.4、测试及分析说明--------------------------------------------------------- - 16 -七、总结及心得体会 --------------------------------------------------------------- - 17 -7.1、设计过程------------------------------------------------------------------ - 17 -7.2、困难与收获 ------------------------------------------------------------- - 17 -八、参考文献 ------------------------------------------------------------------------ - 18 -一、课程设计的目的通过设计、编写和调试词法分析程序（又称扫描器），了解扫描器的组成结构，不同种类单词的识别方法，加深了对词法分析作用的理解。

编译原理课程设计报告课题名称：编译原理课程设计C-语言词法与语法分析器的实现提交文档学生姓名：提交文档学生学号：同组成员名单：指导教师姓名：指导教师评阅成绩：指导教师评阅意见：..提交报告时间：年月日C-词法与语法分析器的实现1.课程设计目标（1）题目实用性C-语言拥有一个完整语言的基本属性，通过编写C-语言的词法分析和语法分析，对于理解编译原理的相关理论和知识有很大的作用。

通过编写C-语言词法和语法分析程序，能够对编译原理的相关知识：正则表达式、有限自动机、语法分析等有一个比较清晰的了解和掌握。

（2）C-语言的词法说明①语言的关键字：else if int return void while所有的关键字都是保留字，并且必须是小写。

②专用符号：+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */③其他标记是ID和NUM，通过下列正则表达式定义：ID = letter letter*NUM = digit digit*letter = a|..|z|A|..|Zdigit = 0|..|9注：ID表示标识符，NUM表示数字，letter表示一个字母，digit表示一个数字。

小写和大写字母是有区别的。

④空格由空白、换行符和制表符组成。

空格通常被忽略。

⑤注释用通常的c语言符号/ * . . . * /围起来。

注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。

注释不能嵌套。

（3）程序设计目标能够对一个程序正确的进行词法及语法分析。

2.分析与设计（1）设计思想a.词法分析词法分析的实现主要利用有穷自动机理论。

有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。

通过有穷自动机理论能够容易的设计出词法分析器。

b.语法分析语法分析采用递归下降分析。

递归下降法是语法分析中最易懂的一种方法。

它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。

编译原理课程设计报告一、目的与要求目的：在分析理解一个教学型编译程序（如PL/0）的基础上，对其词法分析程序、语法分析程序和语义处理程序进行部分修改扩充。

达到进一步了解程序编译过程的基本原理和基本实现方法的目的。

要求：对PL/0作以下修改扩充：基本内容（成绩范围：“中”、“及格”或“不及格”）（1）扩充赋值运算：+= 和-=（2）扩充语句REPEAT<语句序列>UNTIL <条件>其中，<条件>是循环条件，即条件不成立时，重复执行循环体的< 语句序列>；条件成立时，循环结束。

选做内容（成绩评定范围扩大到：“优”和“良”）（1）增加运算：++ 和--。

（2）增加类型：①字符类型；②实数类型。

（3）扩充函数：①有返回值和返回语句；②有参数函数。

（4）增加一维数组类型（可增加指令）。

（5）其他典型语言设施。

二、实验环境与工具（1）计算机及操作系统：PC机，WindowsXP（2）程序设计语言：C（3）教学型编译程序：PL/0三、设计方案（1）概述：源、目标语言，实现工具(平台)，运行平台源语言: PL/0目标语言: 目标代码（生成的文件后缀为*.COD）实现平台: VC++ 6.0运行平台: WindowsXP（2）结构设计说明：各功能模块描述Error（）出错处理，打印出错位置和错误编码GetCh（）漏掉空格，读取一个字符GetSym（）词法分析，读取一个单词GEN（）目标代码生成过程，本过程用于把生成的目标代码写入目标代码数组，供后面的解释器解释执行TEST（）测试当前单词是否合法过程testENTER（）登陆符号表过程enterPOSITION() 在符号表中查找指定符号所在位置的函数position，如果找不到就返回0V ARDECLARATION（）变量声明LISTCODE（）列出目标代码清单；FACTOR（）因子处理过程factorTERM（）项处理过程term；EXPRESSION（）表达式处理过程CONDITION（）条件处理过程STATEMENT（）语句处理过程BLOCK（）语法分析过程BASE（）: 通过静态链求出数据区基地址的函数，INTERPRET （）：对目标代码解释运行过程（3）主要成分描述①符号表struct tablestruct{char name[al]; /* 名字*/enum object kind; /* 类型：const ，var ，procedure*/int val; /* 数值，仅const 使用*/int level; /* 所处层，仅const 不使用*/int adr; /* 地址，仅const 不使用*/Int size; /* 需要分配的数据区空间*/};struct tablestruct table[txmax]; /* 名字表*/②运行时存储组织和管理由于编译时目标程序运行的数据空间大小已经规定，所以存储组织属于静态存储。

一、 课程设计的目的通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。

同时通过某种可视化编程语言的应用，具备初步的Windows 环境下的编程思想。

通过设计、编写和调试词法分析程序，了解扫描器的组成结构，不同种类单词的识别方法，掌握由单词的词法规则出发，画出识别单词的状态转换图，然后再用程序实现的扫描器的设计方法。

通过本实验，加深对词法分析作用的理解，掌握词法分析方法并编程实现一个词法分析器！ 二、 课程设计的内容及要求读入源程序文件，进行词法分析，输出单词符号。

了解扫描器的组成结构，不同种类单词的识别方法，掌握由单词的词法规则出发，画出识别单词的状态转换图，然后再用程序实现的扫描器的设计方法。

三、 实现原理1. 词法分析的作用就是从左到右扫描源程序，拼成单词，转换成统一的内部表示（token ），送给语法分析器。

主要包括如下几个方面的内容：2. 组织源程序的输入；3. 按规则拼单词，并转换成二元形式；4. 滤掉空白符，跳过注释、换行符及一些无用符号(如字符常数的引号)5. 进行行列计数，用于指出出错的行列号，并复制出错部分；6. 列表打印源程序；7. 发现并定位词法错误； 8. 生成符号表。

四、 算法实现与流程图源程序单和错误信息五、测试数据{ Sample program}read x;if x<0 then {don’t compute if x<=0}fact:=1;repeatfact:=fact*x;x:=x-1;until x=0;write fact;end六、结果输出及分析七、软件运行环境及限制Microsoft Visual Studio 2005八、心得体会通过学习和实验课上的词法分析程序的设计，更加明白了词法分析的重要性和其作用：识别出一个一个的单词符号,加深对词法分析作用的理解。

《编译原理》课程设计报告题目：LALR(1)分析器2011年6月一．设计目的1．巩固对语法分析的基本功能和原理的认识。

2．通过对语法分析表的自动生成加深语法分析表的认识。

3．理解并处理语法分析中的异常和错误。

4．熟练掌握LALR(1)语法分析过程。

二．设计内容本次课程设计是设计一个LALR(1)语法分析器。

LALR(1)是LR(1)的一种改进。

为了克服LR(1)中分析表的构造对某些同心集的分裂可能对状态数目引起剧烈的增长，从而导致存储容量的急剧增加，采用对LR(1)项目集规范族合并同心集的方法，若合并同心集后不产生新的冲突，则为LALR(1)项目集。

本次课程设计的主要内容有首先生成LR(1)项目族；再合并同心集；然后生成LALR(1)项目族，求出LALR(1)的分析表；最后能判断一个字符串是否是该文法的串，若是则生成该字符串的树。

具体实现过程及相关主要实现类如下：类：LR0功能：LR0核心项目集构造输入：产生式的数字化表示输出：LR0核心项目集实现思想：LR0核心项目集构造算法程序如下：public class LR0{ArrayList<ArrayList<int[]>> core;ArrayList<ArrayList<int[]>> Ary_c;ArrayList <int []> producer;private int [] copy(int []a ){int val[]=new int[a.length];for(int i=0;i<a.length;i++)val[i]=a[i];return val;}private ArrayList<int []> copy(ArrayList<int []>a){ArrayList <int []>val=new ArrayList <int []>();for(int i=0;i<a.size();i++){val.add(copy(a.get(i)));}return val;}public boolean isEqual(int []a,int b[]){if(a.length!=b.length)return false;for(int i=0;i<a.length;i++)if(a[i]!=b[i])return false;return true;}public boolean isEqual(ArrayList <int[]>a,ArrayList<int[]>b) {if(a.size()!=b.size())return false;for(int i=0;i<a.size();i++)if(!isEqual(a.get(i),b.get(i)))return false;return true;}public int indexof(ArrayList <int[]>a,int []b){int index;int s1[];for(index=0;index<a.size();index++){s1=a.get(index);if(isEqual(s1,b)==true)return index;}return -1;}public int indexof(ArrayList <ArrayList <int[]>>a,ArrayList <int[]>b){int index;ArrayList <int[]>s1;for(index=0;index<a.size();index++){s1=a.get(index);if(isEqual(s1,b)==true)return index;}return -1;}public int []getStartWith(int i){int count=i;ArrayList<Integer> temp=new ArrayList<Integer>(3);while(count<producer.size()){if(producer.get(count)[0]==i)temp.add(count);elseif(producer.get(count)[0]>i)break;count++;}int val[]=new int[temp.size()];for(count=0;count<temp.size();count++)val[count]=temp.get(count);return val;}public void closuer_innal(int item[],ArrayList <Integer>pos) {if(item.length==2)return ;int i;int p[];for(i=0;i<item.length&&item[i]!=-1;i++);if(item.length-1==i)return ;if(item[i+1]<1000){p=getStartWith(item[i+1]);for(i=0;i<p.length;i++)if(pos.indexOf(p[i])==-1){pos.add(p[i]);closuer_innal(producer.get(p[i]),pos);}}return ;}public ArrayList<int []> closure(int []a) //求闭包{ArrayList <int []>val=new ArrayList<int []>();ArrayList <Integer>pos=new ArrayList<Integer>();closuer_innal(a,pos);for(int i=0;i<pos.size();i++){val.add(copy(producer.get(pos.get(i))));}return val;}public ArrayList <int []>Goto(ArrayList<int[]>a,int x){int index1=0,index2=0,index3,bl,index=0;int s1[],s2[];ArrayList<int []> temp1 = new ArrayList <int[]>(); //临时ArrayList<int []> temp2 = new ArrayList <int[]>();temp1=copy(a);s1=temp1.get(index1);if(s1==null)return null;while(s1[index2]!=-1){index2++;}if(s1.length==index2)return null;index2++;for(index3=0;index3<temp1.size();index3++){s1=copy(temp1.get(index3));if(s1.length<index2+1) ///防止Array溢出continue;if(s1[index2]==x&&indexof(temp2,s1)<0){bl=s1[index2-1];s1[index2-1]=s1[index2];s1[index2]=bl; //-1往后移位temp2.add(copy(s1));}}bl=temp2.size();for(index=0;index<bl;index++) ///求goto函数中的返回值的closure集{s1=copy(temp2.get(index));temp1=closure(s1);for(index1=0;index1<temp1.size();index1++){s2=temp1.get(index1);if(indexof(temp2,s2)<0){temp2.add(s2);}}}return temp2;}public LR0(ArrayList <int []>p){core =new ArrayList<ArrayList<int[]>>();Ary_c=new ArrayList<ArrayList<int[]>>();producer=p;}public void total(){ArrayList <int []>cur=new ArrayList<int []>();cur.add(producer.get(0));core.add(cur);int i=0;while(i<core.size()){cur=core.get(i);LR0Split(cur);i++;}update();}public void LR0Split(ArrayList<int[]>cur){ArrayList <int []>handle=copy(cur);ArrayList <int []>tempal;int []temp;int []prod;int start;ArrayList <int[]>result=new ArrayList<int[]>();ArrayList <int []>val=new ArrayList<int[]>();int j;for(int i=0;i<cur.size();i++){tempal=closure(cur.get(i));for(j=0;j<tempal.size();j++)if(indexof(handle,tempal.get(j))==-1)handle.add(tempal.get(j));}while(!handle.isEmpty()){prod=(int[]) handle.get(0);start=getStart(prod); //返回-1之后的数,没有返回-1if(start==-1){handle.remove(0);continue;}result=getStartWith(start,handle); //返回handle 中所有-1之后是start的产生式,并删除repair(result); //将result中产生式-1以后的数与-1调换/*returnval=new ArrayList<int []>();for(int i=0;i<result.size();i++){temp=(int[]) result.get(i);val=closure(temp);if(indexof(returnval,temp)<0);returnval.add(temp);for(int j=0;j<val.size();j++){if(indexof(returnval,val.get(j))<0);returnval.add(val.get(j));}}*/if(indexof(core,result)<0)core.add(result);}}public int getStart(int[] prod) //返回-1之后的数,没有返回-1{int i=0;while(prod[i]!=-1&&i<prod.length)i++;if(prod.length-1<=i)return -1;elsereturn prod[i+1];}public ArrayList<int []> getStartWith(int start, ArrayList<int []>handle){ArrayList <int []> val=new ArrayList<int []>() ;int i;for(i=0;i<handle.size();i++){if(isStartWith(start,handle.get(i))){val.add(handle.get(i));handle.remove(i);i--;}}return val;} //返回handle中所有-1之后是start的产生式,并删除public boolean isStartWith(int start,int [] prod) //产生式-1之后是否为start,是返回1，否则返回0；{boolean state=false;if(getStart(prod)==start)state=true;return state;}public void repair(ArrayList <int[]>prod) //将result 中产生式-1以后的数与-1调换{int num;int i,j=0;for(i=0;i<prod.size();i++){j=0;while(prod.get(i)[++j]!=-1);if(prod.get(i).length==j+1) //遇到空字符的动作continue;num=prod.get(i)[j];prod.get(i)[j]=prod.get(i)[j+1];prod.get(i)[j+1]=num;}}public void update(){ArrayList <int[]> Ary_n=new ArrayList<int[]>();ArrayList <int[]> Ary_r;int index;int prod[];for(int i=0;i<core.size();i++){Ary_n=core.get(i);Ary_r=new ArrayList<int[]>();for(index=0;index<Ary_n.size();index++){prod=(int[]) Ary_n.get(index);if(prod[0]==0||prod[1]!=-1)Ary_r.add(prod);}if(indexof(Ary_c,Ary_r)<0)Ary_c.add(Ary_r);}System.out.println();}}类：Phrase功能：为每个项目配备向前搜索符输入：LR0核心项目集输出：LALR(1)核心项目集实现思想：LALR(1)的造核算法public void sponsor(){Queue hq;int i,j;// 核心项目lnodeLinkNode lnode;QNode qnode;// 核心项目的产生式int p[];// -2是一个特殊的标志符，也就是传播符串的标志；int s[]={-2};calFirst =new CalFirst(producer);hq=new Queue();// 开始符号的特殊处理VT.add("#");I[0].search=new int[1];I[0].search[0]=VT.indexOf("#")+1000;qnode=new QNode(0,0);hq.enq(qnode);for(i=0;i<I.length;i++){lnode=I[i];while(lnode!=null){//if(lnode.search[0]==nu)item.clear();sstr.clear();// 有自生搜索符closuer_self(lnode.prod,s);if(item.size()>0){for(j=0;j<item.size();j++){qnode=update(item.get(j),sstr.get(j),hq);//修改自生搜索符,并入队// if(qnode!=null)//hq.enq(qnode);}}lnode=lnode.next;}}while(!hq.isEmpty()){qnode=hq.deq();lnode=getLinkNode(I[qnode.state],qnode.item);//qnode.i状态中的第j个项目p=lnode.prod;item.clear();sstr.clear();// 传播传播搜索符closuer_spread(p,lnode.search);if(item.size()>0){for(j=0;j<item.size();j++){qnode=update(item.get(j),lnode.search,hq);//修改传播搜索符\并入队//if(qnode!=null)// hq.enq(qnode);}}// 对每一个状态集都进行如此处理}}// 求出项目p的闭包中所有核心项目的自生搜索符private int [] copy(int []a ){int val[]=new int[a.length];for(int i=0;i<a.length;i++)val[i]=a[i];return val;}public boolean closuer_self(int p[],int []s){int i;int left=-1;//产生式左部int temp;int []genrate;int []pos;int []new_s;//ArrayList <Integer>pos=new ArrayList<Integer>();// 找到-1(.)之后的第一个符号for(i=1;i<p.length&&p[i]!=-1;i++);i++;// p为移进项目if(i<p.length)left=p[i];// p为归约项目elsereturn false;// p的闭包为其本身if(left>=1000)return false;// example:// 0 1 -1 1 1003 2// left = 1// s' = first(1003,2,s);i++;// 项目p中left之后的符号串加上s的first集就是left -1 XXX的搜索符集new_S new_s=first(p,i,s);pos=getStartWith(left);// closuer(p,pos);for(i=0;i<pos.length;i++){genrate=producer.get(pos[i]);// 递归向下求解,暂时定为自生一次即截止，向下传播通过genarate的自生求解if(genrate.length==2)continue;if(!(left==p[0]))closuer_self(genrate,s);elseif(!isEqual(genrate,p))closuer_self(genrate,s);// 搜索符集是自生的if(new_s[0]!=-2){genrate=copy(genrate);temp=genrate[1];genrate[1]=genrate[2];genrate[2]=temp;item.add(genrate);sstr.add(new_s);}}return true;}public void closuer(int item[],ArrayList <Integer>pos) {if(item.length==2)return ;int i;int p[];for(i=0;i<item.length&&item[i]!=-1;i++);if(item[i+1]<1000){p=getStartWith(item[i+1]);for(i=0;i<p.length;i++)if(pos.indexOf(p[i])==-1){pos.add(p[i]);closuer(producer.get(p[i]),pos);}}return ;}// 返回项目p所能传播到的所有项目public boolean closuer_spread(int p[],int s[]){int i;int left=-1;//产生式左部符号int []genrate;// int []pos;int []new_s;int temp;ArrayList <Integer>pos=new ArrayList<Integer>();// 找到-1(.)之后的第一个符号for(i=1;i<p.length&&p[i]!=-1;i++);i++;// p为移进项目if(i<p.length)left=p[i];// p为归约项目elsereturn false;//以下是重点genrate=copy(p);genrate[i]=-1;genrate[i-1]=left;item.add(genrate);sstr.add(s);// p的闭包为其本身(-1之后的第一个符号为终结符)if(left>=1000)return false;// example:// 0 1 -1 1 1003 2// left = 1// s' = first(1003,2,s);i++;// 项目p中left之后的符号串加上s的first集就是left -1 XXX的搜索符集new_S int []tempArr=new int[1];tempArr[0]=-2;new_s=first(p,i,tempArr);tempArr=null;// 获得所有以left退出的项目//pos=getStartWith(left);this.closuer(p, pos);for(i=0;i<pos.size();i++){genrate=producer.get(pos.get(i));// 搜索符集是传播的if(new_s[0]==-2&&genrate.length!=2){// 递归向下求解,暂时定为传播一次即截止，向下传播通过genarate的传播/* if(!(left==p[0]))closuer_spread(genrate,s);elseif(!isEqual(genrate,p))closuer_spread(genrate,s);*/genrate=copy(genrate);temp=genrate[1];genrate[1]=genrate[2];genrate[2]=temp;item.add(genrate);sstr.add(s);}}return true;}// 返回所有以i产生的产生式的位置（>=1个），并在第一个位置之后添加-1// 本函数是建立在producer中的产生式的左部按升序基础上的，不可随意使用public int []getStartWith(int i){int count=i;ArrayList<Integer> temp=new ArrayList<Integer>(3);while(count<producer.size()){if(producer.get(count)[0]==i)temp.add(count);elseif(producer.get(count)[0]>i)break;count++;}int val[]=new int[temp.size()];for(count=0;count<temp.size();count++)val[count]=temp.get(count);return val;}public int[] first(int []prod,int i,int search[]){if(i==prod.length)return search;//calFirst.a.clear();//calFirst.firstv(prod, i, search);return calFirst.first(prod, i, search);}private int[]arrCon(int[]a,int b[]){boolean isChange=false;ArrayList <Integer>temp=new ArrayList<Integer>();int i;if(a!=null){for(i=0;i<a.length;i++)temp.add(a[i]);}for(i=0;i<b.length;i++)//有所更新{if(temp.indexOf(b[i])==-1){temp.add(b[i]);isChange=true;}}a=new int[temp.size()];for(i=0;i<a.length;i++){a[i]=temp.get(i);}if(isChange)return a;elsereturn null;}public QNode update(int []prod,int []search,Queue hq) {//返回修改的项目是第几个状态集合中的(QNode.state)的第几个项目(QNode.item)(从0记数)LinkNode p;int a[];int item;int i=0;while(i<I.length){item=0;p=I[i];while(p!=null){if(isEqual(p.prod,prod)){a =arrCon(p.search,search);//null表示没有做任何修改if(a!=null){p.search =a;hq.enq( new QNode(i,item));return null;//此处是一个危险点,必须保证不能有一个项目在多个状态中出现,否则,会出现严重的错误}}item++;p=p.next;}i++;}return null;}public boolean isEqual(int []a,int []b){if(a.length !=b.length)return false;for(int i=0;i<a.length ;i++)if(a[i]!=b[i])return false;return true;}}类：Analyze功能：整个分析程序的总控程序输入：编译目标文件、输出文件路径输出：语法分析树、三地址代码、错误信息实现思想：LR分析器工作原理class Analyze{private ArrayList<int [] > producer =new ArrayList<int []>();private ArrayList<String > VT=new ArrayList<String>();private ArrayList<String > VN=new ArrayList<String>();// private LinkNode []I;// 移进均为小于1000的,归约为大于1000的,并且接受状态的内容为-1,空状态用-2表示private int[][]Action;private int[][]Goto;//Gotoprivate String []prods;private ArrayList<String>lalr;DefaultMutableTreeNode root=null;public ArrayList <String >errorInfo=new ArrayList<String>();public ArrayList <Integer>errorLine=new ArrayList<Integer>();public void analyze(String filePath,File outFile){FileInputStream f = null;try {f = new FileInputStream(filePath);} catch (FileNotFoundException e) {e.printStackTrace();}//打开词法分析流：DataInputStream input = new DataInputStream(f);//lex为词法分析器TinyCLexer lex=new TinyCLexer(input);try {Stack<Integer> stateStack =new Stack<Integer>();//状态栈Stack<Integer> tokenStack = new Stack<Integer>();//符号栈的内容为：非终结符与VN中相对应，终结符-1000后与VT中相对应int state;int temp;int []prod;int i;int action;TokenNode data;Token token=null;Token oldtoken=null;int tokentype;int end=VT.indexOf("#")+1000;//#入栈Tree tree=new Tree();Syntax syn=new Syntax(tree,new FileWriter(outFile));stateStack.push(0);//状态0保证是开始状态tokenStack.push(end);errorInfo.clear();errorLine.clear();token=lex.nextToken();//获得下一个面临的词法符while(true){state=stateStack.peek();//获得栈顶状态if(token.getType()>=100)//无意义的跳过continue;if(token.getText()==null){token.setType(VT.indexOf("#"));}//token.getType()就是面临的输入符号（一定是终结符）,它与VT中相对应action=Action[state][token.getType()];if(action==-1){prod=producer.get(0);stateStack.pop();if(prod[2]!=tokenStack.pop()){JOptionPane.showMessageDialog(null, "编译程序遇到不能处理的错误！\n分析被中止", "提示",RMATION_MESSAGE,new ImageIcon("images\\error.png"));return ;}tree.Reduce(prod.length-2, VN.get(prod[0]));syn.SyntaxAnalyze(0);root= tree.getRoot();JOptionPane.showMessageDialog(null, "编译程序完成编译！", "提示",RMATION_MESSAGE,new ImageIcon("images\\right.png"));return ;}if(Action[state][token.getType()]<1000)//移进，转移到其中内容的状态{tokentype=token.getType();if(Action[state][tokentype]==-2){errorLine.add(oldtoken.getLine());tokentype=getShift(state,tokentype);errorInfo.add("错误:行("+token.getLine()+"\t)列("+token.getColumn()+")未知语法错误[shift]!");if(tokentype==-2){JOptionPane.showMessageDialog(null, "编译程序遇到不能处理的错误！\n分析被中止", "提示",RMATION_MESSAGE,new ImageIcon("images\\error.png"));return ;}}//出错处理;stateStack.push(Action[state][tokentype]);tokenStack.push(1000+tokentype);data=new TokenNode(token.getText(),tokentype);//把token信息保存起来，备用tree.Shift(data);//移进相关信息进栈}else{//归约，用Action[state][token.getType()]的产生式归约,用第Action[state][token.getType()]条产生式//DefaultTreeModeltemp=Action[state][token.getType()]-1000;prod=producer.get(temp);for(i=prod.length-1;i>1;i--)//产生式的右部的逆序为出栈顺序{stateStack.pop();if(prod[i]!=tokenStack.pop()){JOptionPane.showMessageDialog(null, "编译程序遇到不能处理的错误！\n分析被中止", "提示",RMATION_MESSAGE,new ImageIcon("images\\error.png"));return ;}}tree.Reduce(prod.length-2, VN.get(prod[0]));if(!syn.SyntaxAnalyze(temp)){errorInfo.add("错误：行("+oldtoken.getLine()+")列("+oldtoken.getColumn()+")"+ErrorTable.getErrorMsg(syn.getErrorTy pe()));errorLine.add(oldtoken.getLine());}//出栈完毕tokenStack.push(prod[0]);//产生式左部入符号栈if(Goto[stateStack.peek()][prod[0]]==-2){errorInfo.add("错误:行("+oldtoken.getLine()+")列("+oldtoken.getColumn()+")未知语法错误[reduce]!");errorLine.add(oldtoken.getLine());continue;}stateStack.push(Goto[stateStack.peek()][prod[0]]);//根据Goto表判断状态栈的内容continue;}//只有规约的时候不需要读入,其与都要oldtoken=token;token=lex.nextToken();//获得下一个面临的词法符}} catch (Exception e) {//此处有可能是出错的状态异常，如Action[temp][-2]会出现ArrayIndexOutBounds异常//，则说明语法检查中出错了，需要有相应的出错处理JOptionPane.showMessageDialog(null, "编译程序遇到不能处理的错误！\n分析被中止", "提示",RMATION_MESSAGE,new ImageIcon("images\\error.png"));return ;}}private int getShift(int state,int type){int i,j;i=j=type;while(i>=0&&j<VT.size()){if(Action[state][i]>-2&&Action[state][i]<1000)return i;if(Action[state][j]>-2&&Action[state][j]<1000)return j;i--;j++;}return -2;}public void setAction(int a[][]){Action=a;}public int[][] getAction(){return Action;}public void setGoto(int g[][]){Goto=g;}public int[][]getGoto(){return Goto;}public void setVT(ArrayList <String >vt) {VT=vt;}public ArrayList <String>getVT(){return VT;}public void setVN(ArrayList<String >vn){VN=vn;}public ArrayList <String> getVN(){return VN;}public void setProd(ArrayList<int[]>p){producer=p;}public void setLalr(ArrayList <String >l) {lalr=l;}public ArrayList<String> getLalr(){return lalr;}public ArrayList<int []> getProd(){return producer;}public void conProds(){prods=new String[producer.size()];int []prod;int temp;int j;for(int i=0;i<producer.size();i++){prod=producer.get(i);prods[i]="";for(j=0;j<prod.length;j++){temp=prod[j];if(temp==-1)prods[i]+="->";else{if(temp<1000)prods[i]+=VN.get(temp);elseprods[i]+=VT.get(temp-1000);}}}}public String[]getProds(){return prods;}}class LinkNode{int [] prod;int [] search;LinkNode next;public LinkNode(){prod=null;search=null;next=null;}}class Tree{DefaultMutableTreeNode root;Stack <TreeNode> stack;public Tree(){stack=new Stack<TreeNode>();}// 规约,建立一个跟接点并添家响应的孩子public void Reduce(int i,String name){TreeNode temp=new TreeNode(name);Stack <TreeNode> ts=new Stack<TreeNode>();for(;i>0;i--){ts.push(stack.pop());}while(!ts.isEmpty())temp.add(ts.pop());// 当前语法树的跟接点,名字是产生式的左部的名字,接点信息暂时为空，在语义分析的时候添加数据接点root=temp;stack.push(temp);}//移进，一定是遇到了终结符，所以数据接点直接为词法分析产生的结果public void Shift(TokenNode data){TreeNode temp=new TreeNode();temp.setNode(data);stack.push(temp);}public TreeNode getRoot(){return (TreeNode)root;}}/**************************************************************** *********************************///符号表的结构class TokenTable{TokenTable head=null;//父表ArrayList <TokenTable> child=new ArrayList<TokenTable>(1);//子表String tableName;int params=-1;//参数个数，参数在child 0到params-1位置ArrayList <String>name=new ArrayList<String>();ArrayList <Integer>type=new ArrayList<Integer>();ArrayList <Integer>offset=new ArrayList<Integer>();ArrayList <Integer>length=new ArrayList<Integer>();//保存变量长度，仅对数组变量有效，其他变量为1int returnType;public TokenTable(TokenTable head){this.head=head;}}/*************************************************************************************************///保存三地址代码的四元式数据结构class Code{String op;String arg1;String arg2;String result;public Code(){}public Code(String o,String a1,String a2,String res){op=o;arg1=a1;arg2=a2;result=res;}public String print(){returnop+"\t"+arg1+"\t"+arg2+"\t"+result+(char)(13)+( char)(10);}}class Label//label 是一段代码的标签{private int beginIndex=0;private ArrayList <Code>codes=new ArrayList<Code>();private ArrayList <Integer>next=new ArrayList<Integer>();//label 的出口public Label(){}public int getBeginIndex(){return beginIndex;}public void setBeginIndex(int newIndex){if(newIndex==beginIndex)return ;int i=0;char ch;for(i=0;i<codes.size();i++){ch=codes.get(i).result.charAt(0);if(ch>='0'&&ch<='9'){codes.get(i).result=Integer.toString(Integer.parseInt(codes.ge t(i).result)+newIndex-beginIndex);}}}public void setNext(int index){int i;for(i=0;i<next.size();i++){codes.get(next.get(i)).result=Integer.toString(index);}}/*** 增加一条三地址代码* @param code*/public void addCode(Code code){codes.add(code);}/*** 增加一个出口* @param i*/public void addNext(int i){next.add(i);}/*** 将label用最小空间存储**/public void trimtoSize(){codes.trimToSize();next.trimToSize();}/*** 将label中的codes加入当前的中* @param label*/public void addLabel(Label label){if(label==null)return ;label.setBeginIndex(codes.size());//label中的beginIndex整体后移for(int i=0;i<label.codes.size();i++)codes.add(label.codes.get(i));label.setNext(codes.size());//label中的出口为codes的下一句}/*** 获得此标签中一共有多少行代码* @return*/public int getCodesSize(){return codes.size();}/*** 输出*/public void print(FileWriter cout,String fun){setNext(codes.size());// Code code =new Code("HALT","_","_","_");// addCode(code);try {String str;str=""+(char)(13)+( char)(10)+(char)(13)+( char)(10)+"\t"+fun+ (char)(13)+( char)(10);cout.write(str.toCharArray());for(int i=0;i<codes.size();i++){str=("\t"+i+":\t");cout.write(str.toCharArray());str=codes.get(i).print();cout.write(str.toCharArray());}cout.flush();} catch (Exception e){JOptionPane.showMessageDialog(null, "输出文件遇到写入的错误！\n请重新编译", "提示",RMATION_MESSAGE,new ImageIcon("images\\error.png"));return ;}}public Code getCode(int index0){return codes.get(index0);}}三．测试结果与分析本次设计采用的例文法如下:S’→SS →EE →E+TE →TT →(E)T →a分析得到它的状态图如下：由于界面实在不会做，因此运行程序得到的实际结果如下：项目族：状态转换表：分析表如下：输入字符串a+（a+a）得到语法树如下：四．心得与体会本次课程设计并非像老师所说的那么简单容易完成。

编译原理课程设计报告一、分析通过设计，编制，调试一个语法及语义分析程序，加深对语法及语义分析原理的理解。

IF 〈布尔表达式〉THEN 〈赋值语句〉ELSE 〈赋值语句〉其中（1）、可以选择递归下降法、LL（1）、算符优先分析法、LR法完成以上任务，中间代码选用四元式。

（2）、写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。

（3）、编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。

二、算法设计程序要求有三部分组成，即词法分析、语法分析、以及语义分析。

其中词法分析部分要求完成对输入程序的关键字、标识符、常数、运算符进行识别；并分析词法分析的结果，检查程序输入的关键字是否为符合设计文法的关键字，检查标志符是否是合法标志符，识别运算符的种类。

语法分析部分主要是以算符优先文法的设计思想和步骤完成对词法分析结果的的语法分析工作，判断输入的程序是否符合设计的IF-THEN-ELSE文法。

在语法分析通过的基础上进行语义分析，其主要任务是完成对语法分析后的程序的语义分析，根据语法制导翻译去翻译输入的程序，从而得到程序的中间代码表示形式——四元式。

词法分析、语法分析和语义分析的流程图如下：（1）词法分析A 词法分析器的功能和输出形式输入：所给文法的源程序字符串输出：二元组（单词种别,单词符号的属性值）构成的序列B. 待分析的简单语言的词法因为是模拟简单编译器, 所以就以C语言的小型子集作为模拟编译器的词法.模拟程序语言的单词符号可分为下列五种;关键字: { (相当于Pascal语言中的begin) , if ,else , while , }(相当于Pascal语言中的end ) 所有的关键字都是小写字母.运算符: + , - , * , / , = , < , <= , == , > , >= ,<> , && ,|| , !界符: 逗号,分号,左圆括号, 右圆括号, #常数: 在这里只涉及到int型常量其他单词是标识符（ID）和整形常数（NUM），通过以下正规式定义：ID = letter（letter|digit）*NUM = digit digit *空格由空白，制表符和换行符组成，空格一般用来分隔ID，NUM，运算符，界符和关键字，词法分析阶段通常会被过滤掉。

编译原理课程设计报告实验名称编译原理课程设计班级学号姓名指导教师实验成绩2013 年06月一、实验目的➢通过设计、编写和调试，将正规式转换为不确定的有穷自动机，再将不确定的有穷自动机转换为与之等价的确定的有穷自动机，最后再将确定有穷自动机进行简化。

➢通过设计、编写和调试构造LR(0)项目集规范簇和LR分析表、对给定的符号串进行LR分析的程序，了解构造LR(0)分析表的步骤，对文法的要求，能够从文法G出发生成LR(0)分析表，并对给定的符号串进行分析。

二、实验内容➢正规式——>NFA——>DFA——>MFA1.正规式转化为不确定的有穷自动机（1）目的与要求通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序，使学生了解Thompson算法，掌握转换过程中的相关概念和方法，NFA的表现形式可以是表格或图形。

（2）问题描述任意给定一个正规式r（包括连接、或、闭包运算），根据Thompson算法设计一个程序，生成与该正规式等价的NFA N。

（3）算法描述对于Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)=L(R)。

步骤1：首先构造基本符号的有穷自动机。

步骤2：其次构造连接、或和闭包运算的有穷自动机。

（4）基本要求算法实现的基本要求是：(1) 输入一个正规式r；(2) 输出与正规式r等价的NFA。

（5）测试数据输入正规式：(a|b)*(aa|bb)(a|b)*得到与之等价的NFA N（6）输出结果2.不确定的有穷自动机的确定化（1）目的与要求通过设计、编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。

DFA的表现形式可以是表格或图形。

（2）问题描述任意给定一个不确定的有穷自动机N，根据算法设计一个程序，将该NFA N变换为与之等价的DFA D。

（3）算法描述用子集法将NFA转换成接受同样语言的DFA。

目录一．课程设计目的┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅2 二．课程设计题目描述和要求┅┅┅┅┅┅┅┅┅┅┅┅┅┅21、算术表达式的描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅ 22、课程设计要求描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅23、实现的功能描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅25、分析器的使用描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅3三．课程设计实现描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅31、实现平台┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅32、课程设计基本思路描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅33、指定向下与递归下降分析方法的基本原理描述┅┅┅┅┅┅44、程序运行的最后界面┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅ 55、演示分析┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅6 四．课程设计总结┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅7 五．实验中的代码描述┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅7 五．参考书目┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅19一、课程设计目的通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。

加深对文法分析器的知识的掌握，掌握计算机语言的语法分析的过程。

以及掌握计算机语言的语法分析程序设计与文法应用的实现方法。

能够熟练运用一种分析方法，自上而下或自下而上的方法分析一个给定的文法，我使用的是自上而下的分析方法。

以及通过思考以及动手制作分析器的过程来锻炼自己的编程能力和逻辑思维能力，体会计算机编译器的奥妙之处。

二、课程设计题目描述和要求1、算术表达式的文法的描述：〈无符号整数〉∷＝〈数字〉{〈数字〉}〈标识符〉∷＝〈字母〉{〈字母〉｜〈数字〉}〈表达式〉∷＝〈项〉{〈加法运算符〉〈项〉}〈项〉∷＝〈因子〉{〈乘法运算符〉〈因子〉}〈因子〉∷＝〈标志符〉｜〈无符号整数〉〈加法运算符〉∷＝＋｜－〈乘法运算符〉∷＝＊｜／〈字母〉∷＝ a | b | … | z〈数字〉∷＝ 0 | 1 | … | 92、课程设计的要求描述：1）在递归下降法、LL（1）、算符优先分析法或者LR法中选择其中一种方法完成以上任务，中间代码选用四元式。

实验1：用Lex设计词法分析器1实验目的：学会用lex设计一个词法分析器。

实验内容：使用lex为下述文法语言写一个词法分析器。

实验要求：输入为用该语言所写的源程序文件；输出为记号序列，每个记号显示为二元组(记号名，记号属性值)的形式。

输出可以在屏幕上，也可以输出到文件中。

不要求建立符号表。

在cygwin下用flex和gcc工具将实验调试通过，并能通过例子parser0中testcases 目录下的测试例的测试。

实验参考：和。

语言文法：<程序> PROGRAM <标识符> ; <分程序><分程序> <变量说明> BEGIN <语句表> END.<变量说明> VAR <变量说明表>;<变量说明表><变量表>: <类型> | <变量表>: <类型>; <变量说明表><类型> INTEGER | REAL<变量表> <变量> | <变量>, <变量表><语句表> <语句> | <语句>; <语句表><语句> <赋值语句> | <条件语句> | <WHILE语句> | <复合语句><赋值语句><变量> := <算术表达式><条件语句> IF <关系表达式> THEN <语句> ELSE <语句><WHILE语句> WHILE <关系表达式> DO <语句><复合语句> BEGIN <语句表> END<算术表达式> <项> | <算术表达式> + <项> | <算术表达式> - <项><项> <因式> | <项> * <因式> | <项> / <因式><因式> <变量> | <常数> | (<算术表达式>)<关系表达式> <算术表达式> <关系符> <算术表达式><变量> <标识符><标识符> <标识符><字母> | <标识符><数字> | <字母><常数> <整数> | <浮点数><整数> <数字> | <数字> <整数><浮点数> .<整数> | <整数>.<整数><关系符> < | <= | = | > | >=| <><字母> A | B | …| X | Y | Z | a | b | …| x | y | z<数字>0|1|2|…|9程序代码：%{#include <>#define LT 1#define LE 2#define GT 3#define GE 4#define EQ 5#define NE 6#define PROGRAM 7#define END 13#define VAR 9#define IF 10#define THEN 11#define ELSE 12#define WHILE 18#define DO 19#define ID 20#define NUMBER 21#define RELOP 22#define NEWLINE 23#define ERRORCHAR 24%}delim [ \t \n]ws {delim}+letter [A-Za-z]digit [0-9]id _|{letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+-]?{digit}+)?int1 {digit}|{digit}{int1}*/%s COMMENT%%<INITIAL>"/*" {BEGIN COMMENT;ECHO;} <COMMENT>"*/" {BEGIN INITIAL;ECHO;} <COMMENT>.|\n {ECHO;}/* ECHO是一个宏，相当于 fprintf(yyout, "%s", yytext)*/ <INITIAL>{ws} {;}<INITIAL>while {return (WHILE);}<INITIAL>do {return (DO);}<INITIAL>PROGRAM {return (PROGRAM);}<INITIAL>end {return (END);}<INITIAL>VAR {return (VAR);}<INITIAL>if {return (IF);}<INITIAL>then {return (THEN);}<INITIAL>else {return (ELSE);}<INITIAL>{id} {return (ID);}<INITIAL>{number} {return (NUMBER);}<INITIAL>"<" {return (RELOP);}<INITIAL>"<=" {return (RELOP);}<INITIAL>"=" {return (RELOP);}<INITIAL>"<>" {return (RELOP);}<INITIAL>">" {return (RELOP);}<INITIAL>">=" {return (RELOP);}<INITIAL>"+" {return (RELOP);}<INITIAL>"-" {return (RELOP);}<INITIAL>"*" {return (RELOP);}<INITIAL>"/" {return (RELOP);}<INITIAL>":=" {return (RELOP);}<INITIAL>";" {return (RELOP);}<INITIAL>"." {return (RELOP);}<INITIAL>"," {return (RELOP);}<INITIAL>. {return ERRORCHAR;}%%int yywrap (){return 1;}void writeout(int c){switch(c){case ERRORCHAR: fprintf(yyout, "(ERRORCHAR, \"%s\") ", yytext);break;case RELOP: fprintf(yyout, "(RELOP, \"%s\") ", yytext);break;case WHILE: fprintf(yyout, "(WHILE, \"%s\") ", yytext);break;case DO: fprintf(yyout, "(DO, \"%s\") ", yytext);break;case NUMBER: fprintf(yyout, "(NUM, \"%s\") ", yytext);break;case ID: fprintf(yyout, "(ID, \"%s\") ", yytext);break;case NEWLINE: fprintf(yyout, "\n");break;case PROGRAM: fprintf(yyout, "(PROGRAM, \"%s\") ", yytext);break;case END: fprintf(yyout, "(END, \"%s\") ", yytext);break;case VAR: fprintf(yyout, "(VAR, \"%s\") ", yytext);break;case IF: fprintf(yyout, "(IF, \"%s\") ", yytext);break;case THEN: fprintf(yyout, "(THEN, \"%s\") ", yytext);break;case ELSE: fprintf(yyout, "(ELSE, \"%s\") ", yytext);break;default:break;}return;}int main (int argc, char ** argv){int c,j=0;if (argc>=2){if ((yyin = fopen(argv[1], "r")) == NULL){printf("Can't open file %s\n", argv[1]);return 1;}if (argc>=3){yyout=fopen(argv[2], "w");}}while (c = yylex()){writeout(c);j++;if (j%5 == 0) writeout(NEWLINE);}if(argc>=2){fclose(yyin);if (argc>=3) fclose(yyout);}return 0;}测试文件为：PROGRAM test;VAR i, j, k: INTEGER;f0: REAL;BEGINi := 1;j := 1;k := 0;f0 := ;WHILE k<=100 DOBEGINIF j <20 THENBEGINj := i;k := k+1;f0 := f0*ENDELSEBEGINj := k;k := k-2;f0 := f0/.2ENDENDEND.运行结果：实验2：用Lex设计词法分析器2实验目的：学会用lex设计一个词法分析器，并考虑其与后续语法分析器的链接问题。

编译原理课程设计报告一、课程设计目的通过课程设计，可以进一步了解高级语言在计算机中的执行过程，了解现代编译器的运行机制，加深对编译原理中关键算法和编译技术的理解，提高自学和理解能力。

了解如何利用现有软件JFLex和Java_cup构造词法分析器和解析器。

二、设计概述这个tiger语言编译器的编译过程涉及到编译五个阶段中的两个，即词法分析器和语法分析器。

其中，解析后完成语法树打印的构建，以检查类型。

词法分析器由JFLex 编译器正则公式生成，词法分析器由编译器产生式生成，解析器由CUP生成。

结果通过GUI界面呈现给用户。

编译器需要对源程序进行单词级的分析和翻译，所以首先要做的就是识别单词，而词法分析的任务就是从左到右扫描源程序的字符串，根据词法规则(常规语法规则)识别出正确的单词，并转换成单词对应的二进制形式(类别码，属性值)进行语法分析。

所以词法分析是编译的基础。

执行词法分析的程序叫做词法分析器。

语法分析是编译器的核心部分。

它的主要任务是确定语法结构，检查语法错误，报告错误的性质和位置，并进行适当的纠错。

三、设计程序(一)设计构思该程序主要完成三个功能模块:词法分析器、语法分析器和GUI人机界面。

词法分析器由JFLex编译正则公式生成，其中必须为外界提供一个获取令牌流的接口。

实验中命名为Java _ cup . runtime . symbol next _ token。

解析器是建立在词法分析器上的，所以它必须包含词法分析器来获取令牌流。

next_token为解析器提供了令牌。

解析器的对外接口是:Java _ cup . runtime . symbol debug _ parse()，它返回语法树的根节点。

GUI 提供人机交互。

它可以顺序显示词法分析阶段获得的所有标记信息和语法阶段生成的语法树。

此外，词法和语法阶段的错误会在“错误提示”文本框中列出，为用户提供改进代码的信息。

流程图:鲍·阿布辛Print.java//打印出语法树……//Tiger 的抽象语法类数据包错误消息ErrorMsg.java//用于生成包含详细信息的错误消息为cupparser 打包Java _ cup.runtime//support包解析Grm.java//解析分析器MainInterface.java//图形用户界面Sym.java//令牌的十进制表示Yylex.java//莱克斯分析器包装语义Entry.java//用于值环境中的绑定Env.java//保存一个值、类型环境和一个错误打印机ExpTy.java//持有翻译和类型检查的结果FunEntry.java//用于函数绑定程序输入流 词法分析程序 GUI 界面句法分析程序 代币 语法树 标记流 错误的语法和类词汇错误Semant.java//主类型检查模块VarEntry.java//用于变量绑定包装符号Symbol.java//使字符串成为独特的符号对象Table.java//用示波器做环境包翻译包类型//描述tiger _ languagetypes(二)词法分析程序这部分工作主要是通过正则表达式的编写，熟悉使用JFLex正确编写正则表达式，并生成相应的词法分析器。

《编译原理》设计方案报告一、项目概述二、课程目标本课程的主要目标是使学生能够掌握编译器的设计与实现原理，理解编译过程中的各个环节，以及掌握常见的编译器构建工具和技术。

具体目标如下：1.理解编译器的基本原理和工作流程；2.掌握常见的编译器构建工具和技术；3.能够独立设计和实现简单的编译器；4.培养学生的系统设计和问题解决能力。

三、课程内容本课程的主要内容包括：1.编译器的概念和基本原理；2.词法分析器和语法分析器的设计与实现；3.语义分析和中间代码生成；4.优化和目标代码生成；5.编译器构建工具和技术。

四、教学方法本课程采用以学生为中心的教学方法，主要包括以下几种教学手段：1.模块化教学：将课程内容分为多个模块，每个模块进行独立的教学和实践；2.理论与实践相结合：通过理论课、实验课等形式，使学生能够将理论知识应用到实际中；3.项目驱动教学：引入编译器设计与实现的实际项目，让学生能够在实践中巩固所学的知识；4.小组合作学习：将学生分成小组，进行协作学习，增强学生的团队合作能力。

五、评价方式为了评价学生对课程内容的掌握程度，本课程采用以下评价方式：1.平时成绩：包括课堂表现、作业和实验成绩等；2.项目成果：针对编译器设计与实现的项目，评价学生的项目成果和实现质量；3.期末考试：以闭卷考试形式对学生的总体掌握情况进行评价。

六、项目进度安排本课程的项目进度安排如下：1.第1-2周：介绍编译器的概念和基本原理；2.第3-6周：词法分析器和语法分析器的设计与实现；3.第7-9周：语义分析和中间代码生成；4.第10-12周：优化和目标代码生成；5.第13-14周：编译器构建工具和技术；6.第15-16周：项目演示和总结。

七、教学资源支持为了支持本课程的教学，我们将提供以下教学资源：1.教材：选用经典的编译原理教材，如《编译原理》（龙书）等；2.课件：编写详细的课件，包括理论知识和实践案例；3.实验指导：编写实验指导书，引导学生进行编译器设计与实现的实践；4. 实验环境：提供编译器构建工具和开发环境，如Lex/Flex、Yacc/Bison等。

编译原理实验报告一、实验目的编译原理是计算机科学中的重要课程，旨在让学生了解编译器的基本工作原理以及相关技术。

本次实验旨在通过设计和实现一个简单的编译器，来进一步加深对编译原理的理解，并掌握实际应用的能力。

二、实验环境本次实验使用了Java编程语言及相关工具。

在开始实验前，我们需要安装Java JDK并配置好运行环境。

三、实验内容及步骤1. 词法分析词法分析是编译器的第一步，它将源代码分割成一系列词法单元。

我们首先实现一个词法分析器，它能够将输入的源代码按照语法规则进行切割，并识别出关键字、标识符、数字、运算符等。

2. 语法分析语法分析是编译器的第二步，它将词法分析得到的词法单元序列转化为语法树。

我们使用自顶向下的LL(1)语法分析算法，根据文法规则递归地构建语法树。

3. 语义分析语义分析是编译器的第三步，它对语法树进行检查和转换。

我们主要进行类型检查、语法错误检查等。

如果源代码存在语义错误，编译器应该能够提供相应的错误提示。

4. 代码生成代码生成是编译器的最后一步，它将经过词法分析、语法分析和语义分析的源代码翻译为目标代码。

在本次实验中，我们将目标代码生成为Java字节码。

5. 测试与优化完成以上步骤后，我们需要对编译器进行测试，并进行优化。

通过多个测试用例的执行，我们可以验证编译器的正确性和性能。

四、实验心得通过完成这个编译器的实验，我收获了很多。

首先，我对编译原理的知识有了更深入的理解。

在实验过程中，我深入学习了词法分析、语法分析、语义分析和代码生成等关键技术，对编译器的工作原理有了更系统的了解。

其次，我提高了编程能力。

实现一个完整的编译器需要处理复杂的数据结构和算法，这对我的编程能力是一个很好的挑战。

通过实验，我学会了合理地组织代码，优化算法，并注意到细节对程序性能的影响。

最后，我锻炼了解决问题的能力。

在实验过程中，我遇到了很多困难和挑战，但我不断地调试和改进代码，最终成功地实现了编译器。

武汉纺织大学编译原理课程设计实验报告学院：数学与计算机专业：计算机姓名：班级：学号：编译原理编译原理课设报告一、实验目的加强对编译程序的整体认识和了解，巩固《编译原理》课程所学知识。

通过本次课程设计掌握编译程序调试技巧和设计编译程序一般的原则，加深对词法分析、语法分析、语义分析等编译阶段及实用编译系统的认识。

使学生能将编译理论与实际应用结合起来，提高学生软件开发的能力。

二、实验内容1）仔细阅读PL/0编译程序文本（编译原理(第二版) 张素琴吕映芝蒋维杜戴桂兰主编清华大学出版社），并上机调试通过。

2）对PL/0语言进行下列扩充（1）扩充一维整型数组。

扩充var数组：VAR <数组标识名>（<下界>：<上界>）〈下界〉和〈上界〉可用常量标识名。

（2）扩充条件语句的功能使其为：IF<条件>THEN<语句>[ELSE<语句>]（3）增加repeat重复语句:REPEAT<语句>{;<语句>}UNTIL<条件>可根据自己具体情况从中选择2个以上题目进行扩充。

三、实验原理PL/0语言可以看成PASCAL语言的子集，它的编译程序是一个编译解释执行系统。

PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。

PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语言可在配备PASCAL语言的任何机器上实现。

其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。

用表格管理程序建立变量、常量和过程表示符的说明与引用之间的信息联系。

当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和输出运行结果。

一、实验目的本次实验旨在使学生通过编译原理的学习，了解编译程序的设计原理及实现技术，掌握编译程序的各个阶段，并能将所学知识应用于实际编程中。

二、实验内容1. 词法分析2. 语法分析3. 语义分析4. 中间代码生成5. 代码优化6. 目标代码生成三、实验步骤1. 词法分析（1）设计词法分析器，识别输入源代码中的各种词法单元；（2）使用C语言实现词法分析器，并进行测试。

2. 语法分析（1）根据文法规则设计语法分析器，识别输入源代码的语法结构；（2）使用C语言实现语法分析器，并进行测试。

3. 语义分析（1）设计语义分析器，检查语法分析后的语法树，确保语义正确；（2）使用C语言实现语义分析器，并进行测试。

4. 中间代码生成（1）设计中间代码生成器，将语义分析后的语法树转换为中间代码；（2）使用C语言实现中间代码生成器，并进行测试。

5. 代码优化（1）设计代码优化器，对中间代码进行优化，提高程序性能；（2）使用C语言实现代码优化器，并进行测试。

6. 目标代码生成（1）设计目标代码生成器，将优化后的中间代码转换为特定目标机的汇编语言；（2）使用C语言实现目标代码生成器，并进行测试。

四、实验结果与分析1. 词法分析实验结果：成功识别输入源代码中的各种词法单元，包括标识符、关键字、运算符、常量等。

2. 语法分析实验结果：成功识别输入源代码的语法结构，包括表达式、语句、程序等。

3. 语义分析实验结果：成功检查语法分析后的语法树，确保语义正确。

4. 中间代码生成实验结果：成功将语义分析后的语法树转换为中间代码，为后续优化和目标代码生成提供基础。

5. 代码优化实验结果：成功对中间代码进行优化，提高程序性能。

6. 目标代码生成实验结果：成功将优化后的中间代码转换为特定目标机的汇编语言，为程序在目标机上运行做准备。

五、实验心得1. 编译原理是一门理论与实践相结合的课程，通过本次实验，我对编译程序的设计原理及实现技术有了更深入的了解。

编译原理课程设计报告编译原理课程设计——简单编译器的设计与实现班级：组长：组员：指导教师：设计时间： 12月摘要....................................... 错误!未定义书签。

1.概述 ..................................... 错误!未定义书签。

2.课程设计任务及要求 ....................... 错误!未定义书签。

2.1 设计任务............................ 错误!未定义书签。

2.2 设计要求............................ 错误!未定义书签。

3.算法及数据结构 ........................... 错误!未定义书签。

3.1算法的总体思想（流程）............... 错误!未定义书签。

3.2词法分析模块......................... 错误!未定义书签。

3.2.1功能........................... 错误!未定义书签。

3.2.2数据结构 ....................... 错误!未定义书签。

3.2.3算法........................... 错误!未定义书签。

3.3语法分析（含语义分析和中间代码生成）模块错误!未定义书签。

3.3.1功能........................... 错误!未定义书签。

3.3.2数据结构 ....................... 错误!未定义书签。

3.3.3算法........................... 错误!未定义书签。

3.4中间代码优化模块..................... 错误!未定义书签。

3.4.1功能........................... 错误!未定义书签。

3.4.2数据结构 ....................... 错误!未定义书签。

编译原理》课程设计一、教学目标本课程旨在让学生了解编译原理的基本概念、方法和技巧，掌握源程序转换为目标程序的基本过程，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等。

通过本课程的学习，学生应能理解并应用编译原理的基本知识解决实际问题，培养分析问题和解决问题的能力。

具体的教学目标如下：1.知识目标：（1）了解编译原理的基本概念和任务。

（2）掌握源程序转换为目标程序的基本过程，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

（3）熟悉各种编译器设计和实现技术。

2.技能目标：（1）能够使用编译原理的基本方法分析并解决实际问题。

（2）具备编写简单编译器的能力。

3.情感态度价值观目标：（1）培养学生对编译原理的兴趣，认识到编译原理在计算机科学中的重要性。

（2）培养学生团队合作、创新和持续学习的精神。

二、教学内容本课程的教学内容主要包括以下几个部分：1.编译原理的基本概念和任务。

2.源程序转换为目标程序的基本过程，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

3.各种编译器设计和实现技术。

4.编译原理在实际应用中的案例分析。

5.编译原理相关的研究动态和发展趋势。

三、教学方法为了提高教学效果，本课程将采用多种教学方法，包括：1.讲授法：教师讲解编译原理的基本概念、方法和技巧，引导学生掌握知识要点。

2.讨论法：学生针对编译原理中的关键问题进行讨论，培养学生的思考和表达能力。

3.案例分析法：分析编译原理在实际应用中的案例，帮助学生更好地理解编译原理的应用价值。

4.实验法：安排学生进行编译器设计的实验，提高学生的实际操作能力和创新能力。

四、教学资源为了支持本课程的教学，我们将准备以下教学资源：1.教材：《编译原理》，为学生提供系统、全面的学习资料。

2.参考书：提供相关领域的经典著作和最新研究成果，供学生拓展阅读。

3.多媒体资料：制作课件、教学视频等，丰富教学手段，提高教学效果。

表达式计算器这是一款算术表达式计算器，用户通过输入算术表达式达到计算的目的，可代替目前普遍使用的计算器。

一、需求分析需求分析的目标是描述系统应做什么，并使得开发人员和用户就该描述达成共识。

需求分析的任务是找出系统的所有需求并加以描述，同时建立模型。

因此，开发任何一个合格的软件系统，都必须经过需求分析，这样才能使设计出来的软件满足用户的要求，并且解决目标系统“做什么”的问题。

下面是本人对所设计的表达式计算器进行的需求分析。

1、程序的设计要求和功能要求（1）设计要求：①用户从键盘输入算术表达式后，须以#号结束输入，然后按回车键进行计算。

②输入负数时，要用（0-正数）来表示。

③用户能重复多次的使用此计算器进行计算。

（2）功能要求：①能分析、计算任何包括加、减、乘、除、指数、对数、三角函数和括号的数学表达式。

②能得到正确的计算结果。

③能够对错误的计算表达式做出判断，并给出出错原因。

2、程序的各个模块功能描述（1）初始化运算符栈函数（initStackOPTR）：对运算符栈OPTR进行初始化工作。

（2）初始化操作数栈函数（initStackOPND）：对操作数栈OPND进行初始化工作。

（3）进运算符栈函数（pushOPTR）：把输入的运算符按要求压入运算符栈OPTR。

（4）进操作数栈函数（pushOPND）：把输入的操作数按要求压如操作数栈OPND。

（5）出运算符栈函数（popOPTR）：把栈顶的运算符按要求弹出运算符栈OPTR。

（6）出操作数栈函数（popOPND）：把栈顶的操作数按要求弹出运算符栈OPND。

（7）返回运算符栈的栈顶元素函数（getTopOPTR）：得到运算符栈OPTR的栈顶元素，但是并不改变栈本身。

（8）返回操作数栈的栈顶元素函数（getTopOPND）：得到运算符栈OPND的栈顶元素，但是并不改变栈本身。

（9）判断操作数栈是否为空函数（stackEmptyOPND）：若栈为空，函数返回值为1，若栈不为空，函数返回值为0。