编译原理语法分析实验报告

1、编译原理实验报告实验名称：编写语法分析程序实验类型：设计性实验指导教师：蒋勇专业班级：软件工程1401姓名:*学号: 实验地点：东六e座301实验成绩：日期：2016年5月17日实验一编写词法分析程序一、实验目的：1. 设计、编写、调试一个递归下降分析程序，实现对词法分析程序提供的 单词序列进行语法检查和结构分析。2. 掌握递归下降语法分析方法。3. 巩固理论知识。二、实验设计:1. 设计原理：1) 对丁文法的每一个非终结符u的文法规则是一个识别u的过程定义, 为每一个非终结符构造子程序。2) 如果u的右部符号串只有一个候选式则从左到右依次构造u的识别 代码。3) 如果u的右部符号串有终结符号

2、，则判断输入的符号是否匹配终结 符号，如果相等，则读入下一个符号；如果不相等，则有语法错误， 应当报错。4) 如果是非终结符号，则调用非终结符号的子程序即可。5) 如果u的右部有多个候选式，应该根据每个候选式的第一个符号来 确定该分支。6) 对丁含有e表达式的文法规则需耍判断输入的符号是否在u的 follow集里面。2. 设计方法：(1) 文法改造，消除二义性；(2) 对含有左递归或者左公因了的文法消除左递归，提取左公因了；(3) 求每一个右部符号串的first集合，如果右部含有£,则需耍求出其 产生式左部非终结符的follow集。判断文法是否是ll (1)文法， 若不是ll文法，说

3、明文法的复朵性超过自顶向下方法的分析能力。(4) 根据改写后的文法设计程序，依据设计原理构造每一个菲终结符的子 程序。3. 设计过程：(1) 改写文法、消除左递归(将左递归改为右递归)、提取左公因子；(2) 求出相应的first集和follow集；(3) 设计程序流程图，设计程序；(4) 编写程序;4. 框架思路，错误信息输出：对每一个非终结符构造其子程序，设定一个返冋值。如果语法分析有错 则返回1,没有错误就返回0；对于错误，在程序的相应行数报错。齐 个非终结符之间依据文法规则调用。每次遇到终结符函数都判断是否匹 配当前终结符号，如果不匹配则报错，返冋1。如果匹配，则读入下一个符号。三、实验

4、过程()木次实验的test语言语法规则：1) <program>-><declarati on _list>vstatement_list>2) <declaration_list>f vdeclaration_listxdeclaration_stat> | e3) <declaration_stat>->int id;4) <statement_list>f vstatementistvstatement> | e5) <statement>-><if_stat> | &

5、lt;while_stat> | <for_stat> | <read_stat>| <write_stat> | <compound_stat > |<expression_stat>6) vif stat>f if (vexpr>) vstatement>| 讦(vexpr>) vstatement >else v statement>7) <while_stat>-> while (<expression>) < statement >8) &l

6、t;for_stat>->for (<expression><expression>；vexpression>)<statement>9) <write_stat>->write <expression>10) <read_stat>->read id;11) <compo un d_stat>-><stateme nt_list>12) <expression_stat>->< expression >|;13) v express

7、ionidxbool expr>|vbool expr14) <bool_expr> f <additive_expr> | < additive_expr >(>|<|>=|<=|=| !=)< additive_expr >15) < additive_expr>->< additive_expr>+<term> | < additive_expr>-<term>|< term >16) < term >-*< ter

8、m >*<factor>|< term >/<factor>|< factor >17) < factor >-(< expression >)|id|num1. 将左递归改为右递归：2) <declaration_list>-><declaration_listxdeclaration_stat> | e改写后：<declarati on_ list>:=<declaratio n_l istl><declaration_listl>:=<de

9、clarati on_ statxdeclaration_listl> | e4)<statement_list>-><statementistxstatement> | e改写后：<statement_list>:=<statement_listl><statement_listl>:=<statementxstatementistl> | e15) < additive_expr>->< additive_expr>+<term> | < additive_e

10、xpr>-<term>|< term > 改写后：<additive_expr>:=<termxadditive_exprl><additive_expr>:=+<term><additive_exprl> | -<termxadditive_exprl> | e16) < term >f v term >*<factor>|< term >/<factor>|< factor >改写后：<term>:=<fa

11、ctorxterml><terml>:=*<factorxterml> | /<factorxterml>| e2. 提取公因式：14)<bool_expr> f <additive_expr> |<additive_expr>(>|<|>=|<=|=| !=)< additive_expr > 改写后： <bool_expr> := <additive_exprxbool_exprl><bool_exprl> := s | (> | &l

12、t; | >= | <= | = | ! =) <additive_expr>3. 是否奇以提取公因式一6)vif stat>f if (vexpr>) vstatement>| if (vexpr>) vstatement >else v statement > 不可以提取公因式，讦语句和if.else语句是相互独立的,并没有必然的 联系。4. 规则13超而读入符号解决方案：如果识别出标识符的符号id后，在读入一个符号，如果这个符号时二， 说明选择的是赋值表达式，如果不是二，则说明选择是布尔表达式。(二)、求出右部符号串的first

13、集和含有£产生式的左部非终结符的follow集1) <program>-><declarati on _list>vstatement_list>first(<declaration_listxstatement_list>) = ;2) <declaratio n_ list>:=<declarati on _listl><declarati on jistl>:=<declaratio n_ stat><declaration_listl> | efirst(<dec

14、laration_listl>) = int, e ;first(<declaration_statxdeclaration_listl>) = int;follow(<declaration_listl>) = ifwhile, for,read,write,id,(,num;3) <declaration_stat>f int id;first(int id;) = int;4) <stateme nt_list>:二 vstatementistl><stateme nt_listl>:=vstateme nt>

15、vstatementistl> | efirst(<statement_listl>) = if,while,for,read,write,；,id,num,(; first(<statementxstatement_listl>) = itwhile/orjeawritejjjdumx； follow(<statement_listl>) = ;5) <statement>f<if_stat> | <while_stat> | <for_stat> | <read_stat> | <w

16、rite_stat> | <compo un d_stat>|<expressio n_ stat>first(<if_stat>) = if;first(<while_stat>)= whilefirst(<for_stat>) = forfirst(<read_stat>) = read;first(<write_stat>) = writefirst(<compound_stat>)=first(<expression_stat>)=id,num/;/(6) vif stat

17、>f if (vexpr>) vstatement>| 讦(<expr>) vstatement >else < statement>first(if (vexpr>) vstatement >) = iffirst(if (vexpr>) vstatement >else v statement >)=if7) <while_stat>-> while (<expression>) < statement > first(while (<expression>)

18、 v statement >) = while8) <for_stat>->for (<expression><expression><expression>)<statement> first(for (<expression><expression><expression>)<statement> = for9) <write_stat>->write <expression> first(write <expression>)

19、= write10) <read_stat>->read id; first(read id;) = readll)<compo un d_stat>> <state m ent_l ist> first(<statement_list>) = 12) <expression_stat>>< expression > |; first(< expression >) = (,id,num;first(;) = ;13) < expression >f id=<bool_exp

20、r>| <bool_expr> first(id=<bool_expr>) = id;first(<bool_expr>) = id,num/;14) <bool_expr> f <additive_expr> | <additive_expr>(> |<|>=|<=|=|! additive_expr ><bool_expr> := <additive_exprxbool_exprl><bool_exprl> := e | (> i <

21、i >= i <= i = i ! =) <additive_expr>first(<additive_expr><bool_exprl>)= (, id, numfirst(>i< i>= |<= | = | !=)< additive_expr >)=>,<；>=,<=,=,!=follow(<bool_exprl>)=),;15) < additive_expr>->< additive_expr>+<term> |< a

22、dditive_expr>-<term>|< term > <additive_expr>:=<termxadditive_exprl><additive_exprl>:=+<termxadditive_exprl> | -<termxadditive_exprl> | efirst(< term ><additive_exprl>)= (,id,num first(+<term><additive_exprl>)=+first(-<termxaddi

23、tive_exprl>)=-follow(<additive_exprl>)=>,<,>=,<=,=/!=,；/)16) < term >-< term >*<factor>|< term >/<factor>|< factor > <term>:=<factor><terml><terml>:=*<factor><terml>|/<factor><terml>|e first(<

24、factor>) = (,idznum;first(*<factor><terml>)=*;first(/<factorxterml>)=/;follow(<terml>) =17) < factor >>(< expression >)|id|numfirst(<expression>)= (:first(id) =id;first(num) = num;(三)、<statement>程序流程图(四)、expression程序流程图四、试验调试记录：1、问题表现：当语法分析到最后一行时

25、进入死循环。分析原因：可能是文件没有结束条件，导致一直读取文件最后一个字符 解决方案：经过百度发现fscanf()具有返冋值，如果不为空返冋1,为空 则返回0。在文件结束吋，它会默认将文件最后一个字符继续读入。程 序就进入了死循环。所以在每次读取文件是都判断fscanf()是否小于等于 0,如杲成立，则把读入的字符数组置为空。解决结果：读到最后一行时没冇进入死循环。成功解决问题。2、问题表现：读到第5行时缺少；按照常理应该在这一行报错。但是确报 错在第6行。分析原因：因为第5行读到c时匹配，这个吋候就继续读入下一个字符， 但是这个字符是在卜一行的for,并不是；所以就在for所在的这一行报错。

26、 就显示的第6行冇错误。解决方案：其实我觉得这是没有错误的，所以就没有处理这个问题。像 codeblocks这个编译软件遇到这种问题也是在下一行报错。所以我没有改变这个报错模式。五、实验结果：1、测试数据：int a;int i;int 2b;int cfor (i=l; i<= 10 i=i+l)9a=a+ib=b*i;c=a+b;while(x<=)c=a+b+(x*y;if (a>b)read a;elsewrite b;write c2、实验现象：运用实验一词法分析的结杲进行语法分析 1)、第一处错误：int 2b;input the file name and th

27、e file ad±?ess：e：d航巾test. txt= resuit =4error: expected td before ? 2?the grammar has error(s)!process teturned 0 (0x0)execution time : 11. 996 spress any key to continue.将int 2b;改为int b;后2）、第二处错误:intcerror: expected 'before ? for?the graitimar has error (s)!process :returned 0 (0x0) execut

28、ion time : 7.928 s press any key to continue.加上;后解决该行错误第三处错误:for (i=l; i<= 10 i=i+l)input the file name and the file address: s:data'test. txt= resuit =error: expectedbefore ithe grammar has error (s)!process returned 0 (0x0)execution time : 6. 551 spress any key to corrtinue.4)、分析这个语句可以判断缺少一

29、个；在10后面加上分号后解决该行错误 第四处错误：a = a + iinput the file name and the file address:e:data'test.txt= resuit =10error： expected、before ? b?the grainmar has error (s) !process teturned 0 (0x0)execution time : 5.801 srress any key to continue.5)、在句末加上;后解决该行问题第五处错误：while(x<=)input the file name and the fi

30、le address：e:dattest. txt= resuit =14error： expected tf or 'num' or 5 (' before 5)the grainmar has error (s)!process teturned 0 (0x0) execution time : 8. 246 s press any key to continue.改为 while(x <= i)6）、第六处错误:c=a+b+（x*y;16error: expected before ' the grakimar has error (s) !proc

31、ess :returned 0 (0x0) execution time : 5. 829 s press any key to continue.改为 c=a+b+(x*y);7)、第七处错误:write cinput the file name and the file address： p:datatest.txt= result =27error： expected ' ;， before vthe grairimar has error (s)!process returned 0 (0x0) execution time : 5. 752 s press any key t

32、o continue.改为 write c;8）、第八处错误:input the file name and the file address：e:datxt= resuit =27error: expected巾t the end of inputthe grammar has error (s)!process teturned 0 (0x0)execution time : 7.790 shess my key to continue.在程序末尾加上9）、第九处错误：28error： expected航 the end of inputthe graimnar has error （s）

33、!process teturned 0 （0x0） execution time : 7.711 s press any key to continue.在程序结尾加上后解决了所冇语法问题input the file nairie and the file address: e:datatest. txt= resuit =the grammar has no error!process :returned 0 （0x0）execution time : 7. 012 spress any key to continue.六、讨论与分析1、test语言中不满足无回溯递归卜降分析的语法规则有：第

34、(2)、(4)、(14)、 (15)、(16)这几个语法规则。解决方案：将第(2)、(4)、(15)、(16)这几条规则改为右递归；对第(14)条语法规则提取左公因子。2、不是所有文法都可以满足递归下降分析条件，如：gs:stau|brataau|bbtabr|butcrtd对于规则stau|br,因为first(au)c1first(br) ho,所以该文法不是ll(1)文法。将a、b的产生式代入s的产生式,得到：s->aauu|bu|abrr|br,提取公因子后得到： s->a(auu|brr) |b(u|r),令 s1->auu|brr, s2->u|r,则得到如

35、下文法：s->asl|bs251- auu|brr52- >u|ra->aau|bb->abr|bu*cr-> d对于规则si-auulbrr,因为first(auu)n first(brr) h <p,所以它不是ll(1)文法,无论 重复多少次都不能把它变为ll (1)文法。3、改写文法有什么鑿端？递归算法的实现效率低，处理能力相对有限，通用性差，难以自动生成。七、自我评价木次实验自我感觉良好，独立完成了程序。对于规则(13)我参考了教材71 页的设计方法，但是这一页的这个程序存在着一个小错误。最终的测试结果和我 预想的并没有弟别。总的来说这是一次很有意义

36、的实验。但是代码木身却可以有 优化，我对每一个表达式都设置了返回值。所以遇到错误就会停止分析。不会一 次性把所有错误都显示出来，需要改错后再运行词法分析，然后再语法分析。在 这一点上是不人性化的。每一次实验都是对理论知识的复习和巩固。通过这一次 试验我也发现了自身存在很多的不足。八、关键代码：语法分析程序的入口int testgrammar()int flag = 0;if(file = fopen(scanout,"r") = null)printf("nopen file %s error!n"zscanout);flag = 1;if(flag =

37、 0)flag = program();fclose(file);return flag;< statement >语法规则:int statement()int flag = 0;if(strcmp(buff_o,“if“)二二 0) flag = if_stat();else if(strcmp(buff_o,"while,1) = 0) flag = while_stat();else if(strcmp(buff_0,"for") = 0) flag = for_stat();else if(strcmp(buff_o,"read&q

38、uot;) = 0) flag = read_stat();else if(strcmp(buff_o,"write") = 0) flag = write_stat();else if(strcmp(buff_o,"") = 0)flag = compound_stat();else if(strcmp(buff_o,"")= 0) | (strcmpfhuflo/'id1') = 0)11 (strcmp(buff_o/num“)二二 0) 11 (strcmp(buff_o,t)二二 0) flag = expr

39、ession_stat();elseprintf(h%dterror: expected 'reserved words' nt or 'delimiter1 or 'id' or'num' before ,%slnl,line,buff_l); return 1;return flag;对于改造文法列举其中一个:<declaration_list> := <declaration_listvdeclaration_stat>|£消除左递归后得到<declaration_list> := &l

40、t;declaration_listl><declaration_listl> := <declaration_statxdeclaration_listl>|e int declarationist() _int flag = 0;if (strcmp(buff_ozhintn) = 0)flag = declaratio n_ listl(); return flag; elseprintf(n%dterror: expected 'int1 before %s、n蔦line,buff_l); return 1;/<declaration_listl>f vdeclaration_statxdeclarationistl>| £ int declaration_listl() _int flag = 0;if (strcmp(buff_o/'int") = 0)flag = declarati on_ stat();if(flag > 0) return 1;flag = declarati on_ listl();return flag;else if(str