编译原理课程设计报告2

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

2、关键字是否为符合设计文法的关键字，检查标志符是否是合法标志符，识别运算符的种类。语法分析部分主要是以算符优先文法的设计思想和步骤完成对词法分析结果的的语法分析工作，判断输入的程序是否符合设计的if-then-else文法。在语法分析通过的基础上进行语义分析，其主要任务是完成对语法分析后的程序的语义分析，根据语法制导翻译去翻译输入的程序，从而得到程序的中间代码表示形式四元式。 词法分析、语法分析和语义分析的流程图如下：（1） 词法分析a 词法分析器的功能和输出形式输入：所给文法的源程序字符串输出：二元组（单词种别,单词符号的属性值）构成的序列b. 待分析的简单语言的词法因为是模拟简单编译器, 所

3、以就以c语言的小型子集作为模拟编译器的词法.模拟程序语言的单词符号可分为下列五种; 关键字: (相当于pascal语言中的begin) , if ,else , while , (相当于pascal语言中的end ) 所有的关键字都是小写字母 . 运算符: + , - , * , / , = , , , = , , & ,| , ! 界 符: 逗号 ,分号 ,左圆括号 , 右圆括号 , # 常 数: 在这里只涉及到int型常量 其他单词是标识符（id）和整形常数（num），通过以下正规式定义： id = letter（letter|digit）*num = digit digit *空格由空白

4、，制表符和换行符组成，空格一般用来分隔id，num，运算符，界符和关键字，词法分析阶段通常会被过滤掉。c.词法分析的设计思想:算法的基本任务是从字符串表示的源程序中识别出其具有独立意义的单词符号, 其基本思想是根据扫描到的单词符号的第一个字符的种类, 拼出相应的单词符号。（2）语法分析语法分析要处理的输入是词法分析的输出即单词序列。该部分主要用到两个栈，一个用来保存单词标志号的状态栈另一是用来保存单词本身信息的符号栈。程序从词法分析输出的单词序列中读取一个单词，检查单词是否是合法单词，如果是合法的，则取符号栈的栈顶元素，和当前单词的标志号进行优先级比较，如果小于当前单词的优先级那么将当前单词压

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

6、一次都将规约的语句转化成三地址码的形式保存在字符串e中并记录e中规约产生式的次数在m1.quad中；如果规约的产生式是第一个赋值语句块中的赋值语句，则将规约的产生式以三地址形式保存在字符串b1中并记录b1中规约产生式的次数在m2.quad中；如果规约的产生式是第二个赋值语句块中的赋值语句，则将规约的产生式以三地址形式保存在字符串b2中并记录b2中规约产生式的次数在 m3.quad中。最后控制将b1、b2和e中的内容输入。3、 ll（1）文法 ll(1)文法分析流程图： 构造不带回溯的自上而下分析的文法条件1. 文法不含左递归，2. 对于文法中每一个非终结符a的各个产生式的候选首符集两两不相交。

7、即，若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,a标记为出错。在上面的属性文法中我们使用了这样的假定：每当需要临时变量时，newtemp产生新的临时

8、名字； lookup()用于根据名字的拼写检查符号表中是否存在该名字的条目。如果有，返回该条目的指针，否则lookup返回nil，以表示没有找到；e的属性place用来存放e值的变量名在符号表的登录项或一整数码（若此变量是一个临时变量）；函数newtemp用来产生一个新的临时变量的名字，把该名字也存入符号表，并返回该条目的地址。过程emit将其参数写到输出文件上。emit的参数构成一个三地址语句；变量nextstat给出在输出序列中下一个三地址语句的序号，emit在产生每个三地址语句后将nextstat加1。我们给relop以属性op，用来确定该关系算符究竟代表哪个关系运算。e.

9、true，e.falsen和s.next都是三地址语句的标号，它们都是继承属性.。e.true和e.false分别表示e为真和为假时控制流应该转向的标号，这两个属性由e的上下文决定；s.next表示执行完s后应该执行的第一个三地址语句的标号，它也是由s的上下文决定语法分析方法描述开始时，将#和文法开始符号放入栈底。总控程序在任何时候都是根据栈顶符号x和当前的输入符号进行工作的，它与文法无关 总控程序根据现行栈顶符号x和当前输入符号a，执行下列三种动作之一:1. 若xa，则宣布分析成功，停止分析。2. 若xa ，则把x从stack栈顶逐出，让指针指向下一个输入符号。3.若x是一个非终结符，则查看

10、分析表m。 若mx，a中存放着关于x的一个产生式，把x逐出stack栈顶，把产生式的右部符号串按反序一一推进stack栈(若右部符号为，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。若mx，a中存放着“出错标志”，则调用出错诊察程序error。四、详细设计4.1 语法规则定义的文法，如下： （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

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

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

13、七、 源代码#include#include#include#include#includeenum keyword $right_paren,$left_paren,$mul,$div,$add,$sub,$fenhao, $equal,$if,$then,$else,$greater,$less,$id,$num,$end;/关键字的枚举typedef struct tokenkeyword type;char ch;token;/定义的token结构typedef enumjump,jg,jl,equal,end,add,mul,sub,divopkind;/操作符定义为opkindty

14、pedef structint label;/标号opkind op;/操作符char par1,par2;/操作数unionchar 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 quad_len;/四元式表有效长度int quad_index;/四元式索

15、引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,j;int flag;struct lcharchar char_ch;struct lchar

16、*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 newchar();void push();/进队列char dosome(void);/算法函数void

17、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 nlabel,opkind nop,char npar1,char npar2,int naddress);v

18、oid 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;文件输入串，若文件已完。则break break;insch;/继续读入文件内容coutendl词法分析结果如下:;pr

19、int();/打印词法分析的结果coutendl;cout词法分析结束。endlendl;semantic(); /语法语义分析coutendl输出四元式:endl;printquad();/输出四元式if(right=1)cout分析成功endl;elsecout分析失败endl;cout语法语义分析结束endl;char newchar() char p; p=char(k); /int label,k,one; /标记接口k+;return p; /文件打开初始化bool initialize(char filename100) one=0;token_index=0;/token表索引

20、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()break;while(ch= )insch;if(ch=i)insbuf; /对关键字分析if(strcmp(buf,f)=0)tokentabletot

21、al_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+.type=$greater;else if(ch=a& ch=a & ch=0 & ch=9)tokentabletotal_len.type=$num; tokentabletotal_

22、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 / : tokentabletotal_len.type=$div; tokentabletotal_len+.ch =ch; break; case * :tokentabletotal_le

23、n.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 =ch; break;case ) :tokentabletotal_len.type=$right_paren; tokentabletotal_len+.ch =ch;break; default:cout!

24、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 语法语义分析过程如下:=total_len)return false;if(tokentabletoken_index.type=$fenhao)token_index+;cur.type=tokentabletoken_in

25、dex.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=tokentabletoken_index.ch;coutqueueone.ch;token_index+;one+; queueone.type=$end; queueone.ch=#;coutid id语句void boole

26、an() 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() 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_

27、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(quad_len,jump,0,0,falseadd); else error(e(id/num);elseerror(e(greater/less);/分析语句void sentence() char rtn; char c;if(!nexttoke

28、n() 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();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(qua

29、d_len,equal,rtn,-,c);nexttoken();/ll(1)文法分析char ll1() right=1;/开关项为1flag=0;char t;base=(struct lchar *)malloc(sizeof(lchar);/初始化堆栈base-next=null;base-char_ch=#;temp=(struct lchar *)malloc(sizeof(lchar);temp-next=base;temp-char_ch=e;top=temp;/初始化堆栈 t=dosome();/开始识别if(right)/如果开关项为1coutok!endlendl;els

30、ecouterror!char_ch=pchar;temp-next=top;top=temp;/出栈函数void pop(void) curtocmp=top-char_ch;if(top-char_ch!=#)top=top-next; /根据数组下标计算的值产生式入栈void doforpush(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);pus

31、hs(-);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);pushs(/);break;case 40:pushs(i);break;case 45:pushs();pushs(e);pushs();/根据curchar,curtocmp转为数字以判断是否有产生式void changchartoint() switch(curtocmp)case a:i=1;break

32、;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;case *:j=3;break;case /:j=4;break;case (:j=5;break;case ):j=6;break;待添加的隐藏文字内容2case #:j=7;/算法函数char dosome(void) int t,a=0;char bian1,bian2; opkind opa;char c=$;next();for

33、(;)pop();if(cur.type!=$id & cur.type!=$num)curchar=cur.ch;elsecurchar=i;coutendl;coutcurchar curtocmp1) return c;elsereturn bian1;/产生数值语句的四元式void ad_result(int nlabel,opkind nop,char npar1,char npar2, char nresult)quadquad_len.label=nlabel; quadquad_len.op=nop; quadquad_len.par1=npar1; quadquad_len.

34、par2=npar2; quadquad_len.result=nresult; quad_len+; /产生跳转地址的四元式void ad_address(int nlabel,opkind nop,char npar1,char npar2,int naddress) quadquad_len.label=nlabel; quadquad_len.op=nop;quadquad_len.par1=npar1;quadquad_len.par2=npar2; quadquad_len.address=naddress;quad_len+; /回填出口void backpath(int nla

35、bel,int addr)quadnlabel.address=addr;/错误处理void error(char str20) label+;coutendl;couterror! strendl;/词法分析。输出单词表tokenvoid print() for(token_index=0;token_indextotal_len;token_index+) if(token_index%100=0) coutendl;if(tokentabletoken_index.type=$if)coutsetw(2)if (0),;if(tokentabletoken_index.type=$els

36、e)coutsetw(2) else (1),;if(tokentabletoken_index.type=$then)coutsetw(2) then (-),;if(tokentabletoken_index.type=$id) /字母coutsetw(2)tokentabletoken_index.ch (25),;if(tokentabletoken_index.type=$num) /数字coutsetw(2)tokentabletoken_index.ch (26),;if(tokentabletoken_index.type=$equal)coutsetw(2)= (18),;if(tokentabletoken_index.type=$greater)coutsetw(1) (22),;if(tokentabletoken_index.type=$less)coutsetw(2) (22),; if(tokentabletoken_index.type=$add)coutsetw(2)+ (14),;if(tokentabletoken_index.type=$sub