编译原理课程设计报告.docx

《编译原理课程设计报告.docx》由会员分享，可在线阅读，更多相关《编译原理课程设计报告.docx（22页珍藏版）》请在三一办公上搜索。

1、编译原理课程设计报告编译原理课程设计报告 一、分析 通过设计，编制，调试一个语法及语义分析程序，加深对语法及语义分析原理的理解。 IF 布尔表达式 THEN 赋值语句 ELSE 赋值语句 其中 、可以选择递归下降法、LL、算符优先分析法、LR法完成以上任务，中间代码选用四元式。 、 写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。 、 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 二、算法设计 程序要求有三部分组成，即词法分析、语法分析、以及语义分析。其中词法分析部分要求完成对输入程序的关键字、标识符、常数、运算符进行识别；并分析词法分析的结果，检查程序输

2、入的关键字是否为符合设计文法的关键字，检查标志符是否是合法标志符，识别运算符的种类。语法分析部分主要是以算符优先文法的设计思想和步骤完成对词法分析结果的的语法分析工作，判断输入的程序是否符合设计的IF-THEN-ELSE文法。在语法分析通过的基础上进行语义分析，其主要任务是完成对语法分析后的程序的语义分析，根据语法制导翻译去翻译输入的程序，从而得到程序的中间代码表示形式四元式。 词法分析、语法分析和语义分析的流程图如下： 开始输入需编译的文件名判断文件是否存在Y调用cifa函数进行此法分析此法分析成功Y语法分析分析成功？YN分析成功？Y输出四元式NN语义分析N结束 词法分析 A 词法分析器的功

3、能和输出形式 输入：所给文法的源程序字符串 输出：二元组构成的序列 B. 待分析的简单语言的词法 因为是模拟简单编译器, 所以就以C语言的小型子集作为模拟编译器的词法. 模拟程序语言的单词符号可分为下列五种; 关键字: (相当于Pascal语言中的begin) , if ,else , while , (相当于Pascal语言中的end ) 所有的关键字都是小写字母 . 运算符: + , - , * , / , = , , , = , , & ,| , ! 界 符: 逗号 ,分号 ,左圆括号 , 右圆括号 , # 常 数: 在这里只涉及到int型常量 其他单词是标识符和整形常数，通过以下正规式

4、定义： ID = letter* NUM = digit digit * 空格由空白，制表符和换行符组成，空格一般用来分隔ID，NUM，运算符，界符和关键字，词法分析阶段通常会被过滤掉。 C.词法分析的设计思想: 算法的基本任务是从字符串表示的源程序中识别出其具有独立意义的单词符号, 其基本思想是根据扫描到的单词符号的第一个字符的种类, 拼出相应的单词符号。 语法分析 语法分析要处理的输入是词法分析的输出即单词序列。该部分主要用到两个栈，一个用来保存单词标志号的状态栈另一是用来保存单词本身信息的符号栈。程序从词法分析输出的单词序列中读取一个单词，检查单词是否是合法单词，如果是合法的，则取符号栈

5、的栈顶元素，和当前单词的标志号进行优先级比较，如果小于当前单词的优先级那么将当前单词压入符号栈，将其标志号压入状态栈；如果大于当前单词的优先级那么继续弹出状态栈的元素，和上一个符号栈弹出的元素进行比较，如果两优先级相等则继续弹，如果小于上一次弹出的元素的优先级，则弹的所有元素按先后弹的倒置顺序排列为一个句柄，查找产生式找到相应的产生式进行规约，把规约或的元素当多当前一的元素继续进行比较，直到词法分析输出结果全部遍历完。在规约的过程中记下规约的次数，和每次规约的元素，以便语义分析和中间代码生成。 语义分析 语义分析主要是将语义分析结果转化成三地址码表示的中间代码的过程。 在语法分析的过程中，在每

6、次规约的过程中记录规约的类型和各个类型规约的次数。即当规约的语句是布尔表达式时每规约一次都将规约的语句转化成三地址码的形式保存在字符串E中并记录E中规约产生式的次数在m1.quad中；如果规约的产生式是第一个赋值语句块中的赋值语句，则将规约的产生式以三地址形式保存在字符串B1中并记录B1中规约产生式的次数在m2.quad中；如果规约的产生式是第二个赋值语句块中的赋值语句，则将规约的产生式以三地址形式保存在字符串B2中并记录B2中规约产生式的次数在 m3.quad中。最后控制将B1、B2和E中的内容输入。 三、LL文法 LL(1)文法分析流程图： 构造不带回溯的自上而下分析的文法条件 1. 文法

7、不含左递归， 2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 Aa 1|a 2|a n 则 FIRST(a i)FIRST(a j)f (ij) 3. 对文法中的每个非终结符A，若它存在某个候选首符集包含e，则 FIRST(A)FOLLOW(A)=f 如果一个文法G满足以上条件，则称该文法G为LL(1)文法。 构造预测分析表的步骤： 对每个产生式Aa1|an执行,。 对FIRST(A)中每个终结符a, 把Aai加入到MA,a, 其中a FIRST(ai) 若FIRST(ai), 则对任何属于FOLLOW(A)的终结符b,将A ai加入MA,b。 把所有无定义的MA,

8、a标记为出错。 在上面的属性文法中我们使用了这样的假定：每当需要临时变量时，newtemp产生新的临时名字； lookup(id.name)用于根据名字的拼写检查符号表中是否存在该名字的条目。如果有，返回该条目的指针，否则lookup返回nil，以表示没有找到；E的属性place用来存放E值的变量名在符号表的登录项或一整数码；函数newtemp用来产生一个新的临时变量的名字，把该名字也存入符号表，并返回该条目的地址。过程emit将其参数写到输出文件上。emit的参数构成一个三地址语句；变量nextstat给出在输出序列中下一个三地址语句的序号，emit在产生每个三地址语句后将nextstat加

9、1。我们给relop以属性op，用来确定该关系算符究竟代表哪个关系运算。E.true，E.falsen和S.next都是三地址语句的标号，它们都是继承属性.。E.true和E.false分别表示E为真和为假时控制流应该转向的标号，这两个属性由E的上下文决定；S.next表示执行完S后应该执行的第一个三地址语句的标号，它也是由S的上下文决定 语法分析方法描述 开始时，将#和文法开始符号放入栈底。总控程序在任何时候都是根据栈顶符号X和当前的输入符号进行工作的，它与文法无关 总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一: 1. 若Xa，则宣布分析成功，停止分析。 2. 若Xa ，

10、则把X从STACK栈顶逐出，让指针指向下一个输入符号。 3.若X是一个非终结符，则查看分析表M。 若MX，a中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为 ，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。 若MX，a中存放着“出错标志”，则调用出错诊察程序ERROR。 四、详细设计 4.1 语法规则 定义的文法，如下： Z-S S-AB A-CDE C-void D-main E- B-F F-GF F-G G-HIJ H-int I-KLM K-character L-= M-num

11、J-; 4.2程序流程图 语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查 语法错误，报告错误的性质和位置，并进行适当的纠错工作.法分析的方法有多种多样，常用的方法有递归子程序方法、运算符优先数法、状态矩阵法、LL方法和LR方法。归纳起来，大体上可分为两大类，即自顶向下分析方法和自底向上分析方法. Syntax进行语法分析.对于语法分析，这里采用LR(1)分析法，判断程序是否满足规定的结构.构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR分析方法是严格的从左向右扫描，和自底向上的语法分析方法。 4.3基本树形结构： if语句： 表达式 语

12、句 语句 if语句 while语句： 表达式 语句 while语句 for循环语句： for语句 表达式 表达式 语句 表达式 复合语句： 声明 语句 语句 语句 复合语句 五、实验结果 要编译的文件： 词法分析： 输出的四元式： 六、心得体会 这段时间的课程设计让我知道计算机将高级语言翻译成机器语言的过程，并且体会到了中间的设计分析处理过程，再一次熟悉了C语言的编写。也学到了许多课本上没写的东西，在实验的编写中有许多的坎坷，但是在大家集体和老师的帮助下，都慢慢的克服，也没有什么困难是不可克服的！经过这个实验，也深入体会到计算机的内部世界，进一步的摸清楚计算机的构架。为以后的学习工作再一次奠定

13、了基础，受益匪浅！ 七、源代码 #include #include #include #include #include enum keyword $right_paren,$left_paren,$mul,$div,$add,$sub,$fenhao, $equal,$IF,$THEN,$ELSE,$greater,$less,$id,$num,$end;/关键字的枚举 typedef struct Token keyword type; char ch; Token;/定义的token结构 typedef enumJUMP,JG,JL,equal,END,add,mul,sub,divOp

14、Kind;/操作符定义为opkind typedef struct int label;/标号 OpKind op;/操作符 char par1,par2;/操作数 union char result;/结果 int address;/地址 ; Quad; /四元式入口 #define MAX_TOKEN 256/Token表大小 #define MAX_QUAD 256/四元式数组大小 Token tokentableMAX_TOKEN; Quad quadMAX_QUAD; int token_index;/token表索引 int total_len;/token表有效长度 int qu

15、ad_len;/四元式表有效长度 int quad_index;/四元式索引 Token cur; Token queue10; int label,k,one; /标记接口 char curchar;/存储当前待比较字符 char curtocmp;/存储当前栈顶字符 ifstream ins; int trueadd,falseadd,end; int table58=1,0,0,0,0,1,0,0, 0,1,1,0,0,0,1,1, 1,0,0,0,0,1,0,0, 0,1,1,1,1,0,1,1, 1,0,0,0,0,1,0,0; /存储预测分析表，1为有产生式，0为没有 int i,

16、j; int flag; struct Lchar char char_ch; struct Lchar *next; Lchar,*temp,*top,*base; int right;/定义开关项 bool initialize(char filename255);/文件打开初始化 bool accidence;/词法分析 void print;/输出单词表 void backpath(int,int);/回填出口 void ERROR; void sentence;/分析语句 void boolean;/ 分析E-id id语句 bool nexttoken;/读下一单词 char ne

17、wchar; void push;/进队列 char dosome(void);/算法函数 void pushs(char pchar);/入栈函数 void pop(void);/出栈函数 void doforpush(int t);/根据数组下标计算的值产生式入栈 void changchartoint;/根据curchar,curtocmp转为数字以判断是否有产生式 void semantic;/语法语义分析 char LL1;/LL(1)文法分析 void printQuad;/输出四元式 void ERROR(char str20); void AD_ADDRESS(int nlab

18、el,OpKind nop,char npar1,char npar2,int naddress); void AD_RESULT(int nlabel,OpKind nop,char npar1,char npar2, char nresult); void main cout endl 基于LL(1)法的条件语句语法语义分析程序 endl endl; coutfname; if(!initialize(fname)/初始化文件 return; if(!accidence)/词法分析 return; char ch; while(1) if(ins.eof)/ifstream ins;文件输

19、入串，若文件已完。则break break; insch;/继续读入文件内容 coutendl词法分析结果如下:; print;/打印词法分析的结果 coutendl; cout词法分析结束。endlendl; semantic; /语法语义分析 coutendl输出四元式:endl; printQuad;/输出四元式 if(right=1) cout分析成功endl; else cout分析失败endl; cout语法语义分析结束endl; char newchar char p; p=char(k); /int label,k,one; /标记接口 k+; return p; /文件打开初

20、始化 bool initialize(char filename100) one=0; token_index=0;/token表索引 total_len=0;/token表有效长度 quad_len=0;/四元表有效长度 quad_index=0;/四元表索引 label=0; /int label,k,one; /标记接口 end=0;/ 前面定义的全局变量int trueadd,falseadd,end; k=48; ins.open(filename,ios:nocreate | ios:in); if(ins.fail) cout文件打开出错!ch; if(ins.fail) bre

21、ak; while(ch= ) insch; if(ch=I) insbuf; /对关键字分析 if(strcmp(buf,F)=0) tokentabletotal_len+.type=$IF; else if(ch=T) insbuf; if(strcmp(buf,HEN)=0) tokentabletotal_len+.type=$THEN; else if(ch=E) insbuf; if(strcmp(buf,LSE)=0) tokentabletotal_len+.type=$ELSE; /对关系运算符分析 else if(ch=) tokentabletotal_len+.typ

22、e=$greater; else if(ch=A& ch=a & ch=0 & ch=9) tokentabletotal_len.type=$num; tokentabletotal_len+.ch =ch; Else /采用switch语句对运算符，括号分析 switch (ch) case + : tokentabletotal_len.type=$add; tokentabletotal_len+.ch =ch; break; case - : tokentabletotal_len.type=$sub; tokentabletotal_len+.ch =ch; break; case

23、 / : tokentabletotal_len.type=$div; tokentabletotal_len+.ch =ch; break; case * : tokentabletotal_len.type=$mul; tokentabletotal_len+.ch =ch; break; case ; : tokentabletotal_len.type=$fenhao; tokentabletotal_len+.ch =ch; break; case ( : tokentabletotal_len.type=$left_paren; tokentabletotal_len+.ch =c

24、h; break; case ) : tokentabletotal_len.type=$right_paren; tokentabletotal_len+.ch =ch; break; default:cout!endl; return true; /词法分析结束 /语法语义分析 void semantic if(!nexttoken) ERROR(s(0); cout开始进行语法语义分析:endl 所使用的产生式:endl - if E then S else Sendl if E then p1 else P2endl abendl x:=a*cendl x:=b*cendl 语法语义分

25、析过程如下:=total_len) return false; if(tokentabletoken_index.type=$fenhao) token_index+; cur.type=tokentabletoken_index.type; cur.ch=tokentabletoken_index.ch; token_index+; return true; /进队列 void push one=0; while(tokentabletoken_index.type!=$fenhao) queueone.type=tokentabletoken_index.type; queueone.ch

26、=tokentabletoken_index.ch; coutqueueone.ch; token_index+; one+; queueone.type=$end; queueone.ch=#; coutid id语句 void boolean char a,b; int c; if(!nexttoken) ERROR(E(0); if(cur.type=$id|cur.type=$num) a=cur.ch; if(!nexttoken) ERROR(E(0); if(cur.type=$greater|cur.type=$less) c=cur.type ; if(!nexttoken)

27、 ERROR(E(0); if(cur.type=$id|cur.type=$num) b=cur.ch; else ERROR(E(id/num); if(c=$greater) trueadd=quad_len-1; falseadd=quad_len; AD_ADDRESS(quad_len,JG,a,b,trueadd); AD_ADDRESS(quad_len,JUMP,0,0,falseadd); else trueadd=quad_len; falseadd=quad_len+1; AD_ADDRESS(quad_len,JL,a,b,trueadd); AD_ADDRESS(q

28、uad_len,JUMP,0,0,falseadd); else ERROR(E(id/num); else ERROR(E(greater/less); /分析语句 void sentence char rtn; char c; if(!nexttoken) ERROR(S(0); if(cur.type=$id) c=cur.ch; if(!nexttoken) ERROR(S(0); if(cur.type!=$equal) ERROR(S(equal); push; one=0; rtn=LL1; AD_RESULT(quad_len,equal,rtn,-,c); nexttoken

29、; while(cur.type=$id) c=cur.ch; if(!nexttoken) ERROR(S(0); if(cur.type!=$equal) ERROR(S(equal); push; one=0; rtn=LL1; AD_RESULT(quad_len,equal,rtn,-,c); nexttoken; /LL(1)文法分析 char LL1 right=1;/开关项为1 flag=0; char t; base=(struct Lchar *)malloc(sizeof(Lchar);/初始化堆栈 base-next=NULL; base-char_ch=#; temp

30、=(struct Lchar *)malloc(sizeof(Lchar); temp-next=base; temp-char_ch=E; top=temp;/初始化堆栈 t=dosome;/开始识别 if(right)/如果开关项为1 coutOK!endlendl; else coutError!char_ch=pchar; temp-next=top; top=temp; /出栈函数 void pop(void) curtocmp=top-char_ch; if(top-char_ch!=#) top=top-next; /根据数组下标计算的值产生式入栈 void doforpush(

31、int t) switch(t) case 0:pushs(A);pushs(T);break; case 5:pushs(A);pushs(T);break; case 11:pushs(A);pushs(T);pushs(+);break; case 12:pushs(A);pushs(T);pushs(-);break; case 20:pushs(B);pushs(F);break; case 25:pushs(B);pushs(F);break; case 33:pushs(B);pushs(F);pushs(*);break; case 34:pushs(B);pushs(F);p

32、ushs(/);break; case 40:pushs(i);break; case 45:pushs();pushs(E);pushs(); /根据curchar,curtocmp转为数字以判断是否有产生式 void changchartoint switch(curtocmp) case A:i=1;break; case B:i=3;break; case E:i=0;break; case T:i=2;break; case F:i=4; switch(curchar) case i:j=0;break; case +:j=1;break; case -:j=2;break; cas

33、e *:j=3;break; case /:j=4;break; case (:j=5;break; case ):j=6;break; case #:j=7; /算法函数 char dosome(void) int t,a=0; char bian1,bian2; OpKind opa; char c=$; next; for(;) pop; if(cur.type!=$id & cur.type!=$num) curchar=cur.ch; else curchar=i; coutendl; coutcurchar curtocmp1) return c; else return bian1; /产生数值语句的四元式 void AD_RESULT(int nlabel,OpKind nop,char npar1,char npar2, char