编译原理课程设计报告-编译器设计.doc

1 问题的提出编译器设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。编译程序的输出结果包括词法分析后的二元式序列、变量名表、状态栈分析过程显示及四元式序列程序。整个编译程序分为三部分：词法分析部分、语法分析处理及四元式生成部分、输出显示部分。编译程序需要在单词级别上来分析和翻译源程序，所以首先要识别出单词，而词法分析部分的任务是：从左至右扫描源程序的字符串，按照词法规则（正则文法规则）识别出一个个正确的单词，并转换成该单词相应的二元式（种别码、属性值）交给语法分析使用。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器。语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。语法分析中主要以二元式作为输入部分，所以输出显示部分的任务是将二元式通过LR分析表对语法分析处理过程进行控制，使四元式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。11 词法分析器设计词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。程序语言的单词符号一般分为五种：关键字（保留字/基本字）if、while、begin；标识符：常量名、变量名；常数：34、56.78、true、a、；运算符：+、-、*、/、and、or、.、；界限符：， ； （ ） /*。词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。例如源程序为C语言。输入如下一段：main()int a=-5,b=4,j;if(a=b) j=a-b; else j=b-a;要求输出：（2，“main”）（5，“（”）（5，“）”）（5，”“）（1，”int”）（2，”a”）（4，”=”）（3，”-5”）（5，”,”）（2，”b”）（4，”=”）（3，”4”）（5，”,”）（2，”j”）（5，”;”）（1，”if”）（5，”（“）（2，”a”）（4，”=”）（2，”b”）（5，”）“）（2，”j”）（4，”=”）（2，”a”）（4，”-”）（2，”b”）（5，”;”）（1，”else”）（2，”j”）（4，”=”）（2，”b”）（4，”-”）（2，”a”）（5，”;”）（5，”“）012字母字母或数字其它识别标识符的转换图识别单词：掌握单词的构成规则很重要，而大多数程序设计语言的单词符号都可以用下列状态转换图来识别。012数字数字其它识别整数的转换图1.1.1 词法分析器的设计方法词法分析器的设计方法有如下四个步骤：1.写出该语言的词法规则。2.把词法规则转换为相应的状态转换图。3.把各转换图的初态连在一起，构成识别该语言的自动机。4.设计扫描器；把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。扫描器从初态出发，当识别一个单词后便进入终态，送出二元式。词法分析需要一个单词时，扫描器取单词的程序流程图如下：开始读标识符是字母查保留字表是否查到换成属性字结束是数字是特殊符号error取数换成属性字换成属性字换成属性字YNYYYNNN1.1.2 词法分析器的输出形式词法分析器输出的单词符号常常表示为二元式：（单词种别，单词符号的属性值）单词种别通常用整数编码。标识符一般统归为一种。常数按类型（整、实、布尔等）分种。关键字可视其全体为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的方法。至于界符一般也采用一符一种的分法。1.1.3 核心代码及其功能#include stdafx.h#include ctype.h#include string.h#include stdio.h /*定义一个全局变量，一个全局指针*/FILE *fp; /*fp是一个指向FILE类型结构的指针变量，可以使fp指向某一个文件 的结构变量，从而通过该结构体变量中的文件信息访问该文件*/int id; /*标志变量，用来标识各类型的ID*/*主函数*/void main() /*自定义函数的声明*/char cbuffer;char alphaprocess(char buffer); char digitprocess(char buffer); char otherprocess(char buffer); if (fp=fopen(example.c,r)=NULL) /*以只读方式打开文件example.c，NULL在 stdio.h文件中已被定义为0*/ printf(error); else cbuffer=fgetc(fp); /*文件不为空则从文件中取字符*/ while (cbuffer!=EOF) /*EOF文件结束标志*/ if(cbuffer= |cbuffer=n) /*掠过空格和回车符*/ cbuffer=fgetc(fp); id=4; else if(isalpha(cbuffer) cbuffer=alphaprocess(cbuffer); /*检查cbuffer是否为字母，是则调用alphaprocess()函数*/ else if (isdigit(cbuffer) cbuffer=digitprocess(cbuffer); /*检查cbuffer是否为数字09，是则调用digitprocess()函数*/ else cbuffer=otherprocess(cbuffer); /*非上述两者则调用otherprocess()函数*/ /*主函数结束*/*处理读取字符为字母的情况*/char alphaprocess(char buffer) int search(char searchchar,int wordtype); /*函数声明*/int atype; int i=-1;char alphatp20; /*字符数组存储从文件中读取的字符*/ while(isalpha(buffer)|(isdigit(buffer)|buffer=_|buffer=.) /*标识符的组成成分*/ alphatp+i=buffer; /*将当前读取的字符存如数组*/ buffer=fgetc(fp); /*读取下一个字符*/ alphatpi+1=0; /*字符串以0作为结束标志*/ atype=search(alphatp,1); /*调用函数，判断当前字符串是否为关键字*/ if(atype!=0) /*是关键字则输出该关键字，编号为1，并输出该关键字在关键字表中的位子*/ printf(%s, (1,%d)n,alphatp,atype); id=1; /*关键字的ID为1*/ else printf(%s ,2)n,alphatp); /*为标识符时，编号为2*/ id=2; /*标识符的ID为2*/ return(buffer); /*判断字符串是否为关键字*/int search(char searchchar,int wordtype)char *key32=auto,break,case,char,const,continue,default,do, double,else,enum,extern,float,for,goto,if,int,long, register,return,short,signed,sizeof,static,struct, volatile,while,switch,typedef,union,unsigned,void; /*设置数组指针存储c语言中的32个关键字*/ int i; int p; switch (wordtype) case 1:for (i=0;i=31;i+) if (strcmp(keyi,searchchar)=0) /*比较字符串，为关键字则定位该关键字的序号*/ p=i+1; break; else p=0;return(p); /*alphaprocess()函数结束*/*处理读取字符为数字时的情况*/char digitprocess(char buffer)int i=-1;char digittp20;while (isdigit(buffer)|buffer=.|buffer=e|buffer=E)/考虑数字为小数和指数时的情况 digittp+i=buffer; buffer=fgetc(fp); /*同上*/ digittpi+1=0;printf(%s ,3)n,digittp); /*输出该数字，编号为3*/id=3; /*设置ID为3*/return(buffer);/*digitprocess()函数结束*/*处理读出字符为其他字符的情况*/char otherprocess(char buffer) int n=0; char ch20; ch0=buffer; ch1=0;if(ch0=%|ch0=) buffer=fgetc(fp); ch1=buffer; ch2=0; printf(%s ,5)n,ch); id=4; buffer=fgetc(fp); return(buffer);if(ch0=&)buffer=fgetc(fp); if(buffer!=&) printf(%s ,5)n,ch); id=4; return(buffer); if(buffer=&) ch1=buffer; ch2=0; printf(%s ,4)n,ch); id=3; buffer=fgetc(fp); return(buffer); if(ch0=,|ch0=;|ch0=|ch0=|ch0=(|ch0=) printf(%s ,5)n,ch); buffer=fgetc(fp); id=4; return(buffer); if(ch0=*|ch0=/) printf(%s ,4)n,ch); buffer=fgetc(fp); id=4; return(buffer); if(ch0=|ch0=!|ch0=) buffer=fgetc(fp); if(buffer=) /*防止=,!=,=符号的分离*/ ch1=buffer; ch2=0; printf(%s ,4)n,ch); else printf(%s ,4)n,ch);id=4;return(buffer); buffer=fgetc(fp); id=4; return(buffer); if(ch0=+|ch0=-) if(id=4) /*如果+,-前ID为4的字符则可能为正负数或+,-，否则为加减号*/ for(int i=1;id&c0) e=c;printf(y1=%f,y2=%f,e=%d,c=%xn,y1,y2,e,c);运行结果如下: 12 语法分析器设计语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查 语法错误，报告错误的性质和位置，并进行适当的纠错工作.法分析的方法有多种多样，常用的方法有递归子程序方法、运算符优先数法、状态矩阵法、LL（K）方法和LR（K）方法。归纳起来，大体上可分为两大类，即自顶向下分析方法和自底向上分析方法. Syntax进行语法分析.对于语法分析，这里采用LR(1)分析法，判断程序是否满足规定的结构.构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。1.2.1 LR分析过程的设计思想及算法 1：LR-table.txt：存放分析表，其中正数表示移进，负数表示归约，100表示接受状态，0表示不操作。2：grammar.txt 存放文法开始符号3：lengh.txt 存放产生式右部字符长度4：inpur.txt 输入的程序语法规则定义的文法，如下： （0） Z-S（1） S-AB（2） A-CDE（3） C-void（4） D-main（5） E-()（6） B-F（7） F-GF（8） F-G（9） G-HIJ（10） H-int（11） I-KLM（12） K-character（13） L-=（14） M-num（15） J-; 根据上面文法画出的分层有限自动机并根据分层自动机构造的LR(1)分析表： voidmain()intchar=numSABCDEFGHIJKLM;#021831Ac2-33454-45676-57-281099-11025111315111212-61325141315-814-71516172016-1217191818-15-1519-9-920212221-132223242324-1425-111.2.2 程序核心代码和注释:public void analyzer() /*/循环读取grammar.txt/* /*此处代码略*/*/循环读取 lengh.txt/* /*此处代码略*/*/ 读入文件，进行语法分析/*string strReadFile;strReadFile=input.txt;myTextRead.myStreamReader=new StreamReader(strReadFile);string strBufferText;int wid =0;Console.WriteLine(分析读入程序（记号ID）：n);dostrBufferText =myTextRead.myStreamReader.ReadLine();if(strBufferText=null)break;foreach (String subString in strBufferText.Split()if(subString!=)int ll;if(subString!=null)ll= subString.Length; /每一个长度elsebreak;int a=ll+1;char b = new chara;StringReader sr = new StringReader(subString);sr.Read(b, 0, ll); /把substring 读到char数组里int sort=(int)b0;/ wordi 和 wordNumi对应/先识别出一整个串，再根据开头识别是数字还是字母Wordwid=subString;if(subString.Equals(void)wordNumwid=0;else if(subString.Equals(main)wordNumwid=1;else if(subString.Equals()wordNumwid=2;else if(subString.Equals()wordNumwid=3;else if(subString.Equals(int)wordNumwid=4;else if(subString.Equals(=)wordNumwid=6;else if(subString.Equals()wordNumwid=22;else if(subString.Equals(;)wordNumwid=23;else /识别变量和数字if(sort47&sort58)wordNumwid=7;else wordNumwid=5;Console.Write(subString+(+wordNumwid+)+ );wid+;Console.WriteLine(n);while (strBufferText!=null);wordNumwid=24;myTextRead.myStreamReader.Close();/*/读入LR分析表/* /*此处代码略*/int state = new int100;string symbol =new string100;state0=0;symbol0=#;int p1=0;int p2=0;Console.WriteLine(n按文法规则归约顺序如下:n);/*/ 归约算法如下所显示/*while(true)int j,k;j=statep2;k=wordNump1;t=LRj,k; /当出现t为0的时候if(t=0)/错误类型string error;if(k=0)error=void;elseif(k=1)error=main;elseif(k=2)error=();elseif(k=3)error=;elseif(k=4)error=int;elseif(k=6)error=;elseif(k=22)error=;elseif(k=23)error=;elseerror=其他错误符号;Console.WriteLine(n检测结果:);Console.WriteLine(代码中存在语法错误);Console.WriteLine(错误状况:错误状态编号为 +j+ 读头下符号为 +error);break;elseif(t=-100) /-100为达到接受状态Console.WriteLine(n);Console.WriteLine(n检测结果:);Console.WriteLine(代码通过语法检测);break;if(t0)p2=p2+1;statep2=t;symbolp2=Convert.ToString(wordNump1);p1=p1+1;myTextRead.myStreamReader.Close();Console.Read();示例：1：void main ()int i = 8 ;int aa = 10 ;int j = 9 ;2：void main ()intq i = 8 ;int aa = 10 ;int j = 9 ;对于intq i=8 中 intq这个错误类型，词法分析通过，而语法分析正确识别出了错误，达到预期目标产生出错信息:运行显示如下:13 中间代码生成器设计进入编译程序的第三阶段：中间代码产生阶段。为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。常用的几种中间语言有: 逆波兰式、四元式、三元式、树表示。本课程设计主要实现逆波兰式的生成。1.3.1 逆波兰式的定义和设计思想及算法1、逆波兰式定义: 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。2、生成逆波兰式的设计思想及算法(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。(4)如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。1.3.2 核心代码及其结果显示#include#include#define max 100char exmax;void trans()char strmax;char stackmax;char ch;int sum,j,t,top=0;int i=0;/*计数器*/printf(*n);printf(*说明:以 # 号为结束标志.n);printf(*n);printf(表达示: );do i+;scanf(%c,&stri);/*注: str0没有数据*/if(i=max)printf(表达式长度过长!); while(stri!=# & i!=max);sum=i;/*数组长度,即表达式长度*/t=1;i=1;ch=stri;i+;while(ch!=#)switch(ch) case (:top+;stacktop=ch;break;case ):while(stacktop!=() ext=stacktop;top-;t+;top-;break;case +:case -:while(top!=0&stacktop!=() ext=stacktop;top-;t+;top+;stacktop=ch;break;case *:case /:while(stacktop=*|stacktop=/)ext=stacktop;top-;t+;top+;stacktop=ch;break;case :break;default: while(ch=0&ch=9)ext=ch;t+;ch=stri;i+;i-;ext=&;t+;ch=stri;i+;while(top!=0)if(stacktop!=() ext=stacktop;t+;top-; else printf(error);top-;exit(0);ext=#;printf(n原表达式是: );for(j=1;jsum;j+)printf(%c,strj);printf(