编译原理实验报告.docx

1、编译原理实验报告34目录实验目的3基本内容3基本要求3系统的设计与实现 3 实验一：词法分析程序 4 实验二：语法制导的三地址代码生成11实验过程中遇到的主要问题及解决方法30实验总结31实验目的基本掌握计算机语言的词法分析程序的开发方法以及掌握计算机语言的语法分析程序设计与属性文法应用的实现方法。通过自己动手实现上课讲述的编译的相关程序，加深对所学知识的理解，进而培养“计算思维能力”模型化、抽象思维能力、逻辑思维能力以及算法设计与分析能力，程序设计与实现能力和计算机系统的认知、分析、设计和应用能力基本内容本课程实验内容由两个上机实验组成：词法分析程序编制实验、语法制导的三地址代码生成程序编制

2、实验。通过两个程序的编制，将构造出一个微型编译系统的基本框架。对于词法部分：编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。对于语法/语义部分：编制一个能够进行语法分析并生成三地址代码的微型编译程序。基本要求以给定文法编写的程序作为输入（文件，程序皆可/单行，多行皆可），分别测试 2 个程序。词法分析部分要求：1. 根据所给的正规式，编制正规文法，画出状态图；2. 根据状态图，设计词法分析函数int scan( )，完成以下功能： 1） 从键盘读入数据，分析出一个单词。2） 返回单词种别（用整数表示），3） 返回单词属性（不同的属性可以放在不同的全局变量中）。3. 编写

3、测试程序，反复调用函数 scan( )，输出单词种别和属性。将整个句子的相应成分正确的分析出，并要求错误处理。语法/语义部分要求：1. 考虑所给语法制导定义中文法，求拓广文法的FOLLOW集和项目集规范族。2. 利用FOLLOW集和项目集规范族填写SLR(1)分析表，构造语法分析程序，3. 处理的源程序存放在文件中或者直接输入，它可以包含多个语句。4. 考虑所给语法制导定义中语义规则，构造三地址代码生成程序。5. 测试所编写序的正确性，给定测试用例，输出三地址码，并要求错误处理。系统的设计与实现本次实验所构造的编译系统由 3 个部分组成，分别为词法分析程序，语法分析程序，语义动作部分。语法分析

4、程序通过调用词法分析程序以获得所规约的句子成分的具体内容和分类，在用文法产生式进行规约的每一步调用语义动作部分生成 3 地址码并打印出来。系统结构图如下：读入输入的程序等待新的归约语义分析程序语法分析程序词法分析程序的功能：分析出根据文法产生式所定义的一句话的相关内容（以;号定义一句话的完结） 记录下分析出的单词的具体内容和种类等，传到语法分析器。语法/语义分析程序的功能：从词法分析器分析出的结果入手，通过查 SLR(1)的分析表来进行语法分析，在每一步的归约调用语义分析程序，产生三地址码。具体的设计如下：a) 词法的正规式描述实验一：词法分析程序词法分析程序词法分析出一句话语法分析出的一次规

5、约标识符 (|)*(|_|.)(|)*十进制整数 (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(|.)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*八进制整数 0(1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)* (|.)(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十六进制整数 0x(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)* (|.)(0|1|2|3|4|5|6|7|8|9|a|b

6、|c|d|e|f)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)*运算符和分隔符 + - * / = ( ) ； 关键字 if then else while dob) 变换后的正规文法 0 0x +| - |* |/ | |= |( | ) |；if| then| else |while |doa|b|c|d|e|f|g|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q| R|S|T|U|V|W|X|Y|Z0|1|2|3|4|5|6|7|8|9(|)|(|_|.) (|.)(0|1|

7、2|3|4|5|6|7)| (0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f) |c) 状态图a-z | A-Z0-90-91-90-9125670-70-700-7.0-78910110-f0-fx0-f.0-f121314150-9| a-z | A-Z0-9| a-z | A-Z.|_3161718+|-|*|/|=|(|)|;|#| |319a-z | A-Z|0-9.d) 设计思路一个字符一个字符的进行分析，通过上述的状态转移图将整个词法分析器划分为 3 个小的模块， 分别处理数字，字符和其他符号，而数字部分又在细分为 8 进制，10 进制，16 进制，小数部分这几块

8、；字符部分需要加入对关键字的判断。根据状态的转移，凡是一旦出现了非上述图中的转台变换， 一律转到出错处理程序中，出错处理程序的入口皆为 error()，根据出错地点不同，带入相应的数字已区分出不同的错误。此程序加入了续编译功能。e) 词法分析程序的数据结构与算法string scont=int,char,long,void,bool,if,else,do,while,for,then;/关键字map m1;/关键字的映射表typedef pair Char_Pair;typedef struct word/词法分析的结果string con;/具体内容char type;/种类word;str

9、ing toreal(string buf,int n,int b)/转化小数int i,l;double s=0; double base=b; int final;string st; char str20;l=buf.length();for(i=n;i=0&bufi=9)s=s+(double)(double)(bufi-0)/(double)base); base=base*b;final=s*1000000000;/由于返回一个字符串变量，因此将小数部分扩大后再进行除法while(final%10=0)final/=10; sprintf(str,%d,final); st=str

10、;return st;word base10(string s)/识别 10 进制数int i,l;int num=0; char str20; word w; l=s.length();w.con=;w.type=n; for(i=0;i=0&si=9)num=(si-0)+num*10;else if(si=.)/发现小数点sprintf(str,%d.,num); w.con=str; w.con+=toreal(s,i+1,10); return w;else/错误处理error(1);w.con=!int10; return w;sprintf(str,%d,num);w.con=s

11、tr; return w;word base8(string s)int i,l;/识别 8 进制数int num=0;char str20;word w;w.type=o;l=s.length();for(i=1;i=0&si=7)num=(si-0)+num*8;else if(si=.)sprintf(str,%d.,num);/发现小数点w.con=str;w.con+=toreal(s,i+1,8);return w;elseerror(2);/错误处理w.con=!int8;return w;sprintf(str,%d,num);w.con=str;return w;word b

12、ase16(string s)int i,l;/16 进制数int num=0;char str20;word w;w.type=x;l=s.length();for(i=2;i=0&si=a&si=0&si=a&si|c=|c=|c=(|c=)|c=;|c=#|c= ) return true;elsereturn false;word Isidn(string s)/标示符int i,j;int first=0; int l;int sign=0; string str; l=s.length(); word w;if(m2s=1)/是关键字w.con=s;w.type=m3s; retu

13、rn w;for(i=0;i=A&si=a&si=0&si=1&si=0&si+1=0&s0=A&s0=a&s0 0x3f 00 while a+accxx do x=x-1; a=6.2+a*0X88.80;if ab then a=b else a=b-1+c;测试用例说明：本测试用例测试了十进制数，八进制数，十六进制数，十进制0，八进制0，十进制小数，八进制小数，十六进制小数，各个关键字以及分隔符，对于空格，回车，制表符的测试2截图：g) 思考题1. 词法分析能否采用空格来区分单词？答：不可以,不能只靠空格来区分单词。如要分析if a10 then,如果只用空格；来区分单词的话，只有三个

14、：单词if,ab和then，而事实上a,和10应该区分开，属于3个不同类型的token。因此，在进行词法分析的过程中，应该从状态入手，一个单词一个单词的分析，根据不同单词转入相应的状态进行处理。2. 程序设计中哪些环节影响词法分析的效率？如何提高效率？答：比如分析出了一个 identify，要判断它是否是一个关键字，其实我们大可不必单写一个算法，完全可以利用 C+的 STL 中的 map 预先为这些单词建立一个表，由于 map 支持字符串类型作为关键字，之后可以直接查表来判断是否是一个关键字。其效率比用任何的字符串类的算法要高。a) 文法语义及规则实验二/三：语法制导的三地址代码生成产生式语义

15、规则Sid = E ;S.code = E.code | gen(id.place:=E.place)Sif C thenS1;C.true = newlabel; C.false = S.next; S1.next = S.next;S.code = C.code | gen(C.true:) | S1.codeSif C thenS1 elseS2;C.true = newlabel; C.false = newlabel; S1.next = S2.next =S.next;S.code = C.code | gen(C.true:) | S1.code| gen(gotoS.next)

16、| gen(C.false:)| S2.code;Swhile C doS;S.begin = newlabel; C.true = newlabel; C.false = S.next; S1.next = S.begin;S.code = gen(S.begin:) | C.code |gen(C.true:) | S1.code | gen(gotoS.begin);CE1 E2C.code = E1.code | E2.code | gen(ifE1.placeE2.placegotoC.true) |gen(gotoC.false)CE1 E2C.code = E1.code | E

17、2.code | gen(ifE1.placeE7. CE,EC.EE C.EE CE.):CE.E E.E+T E.E-T E.T T.FT.T*F T.T/F F.(E)F.id F.int8 F.int10 F.int16I19(I7:):CEE. EE.+T EE.-TI8(I18:T)I9(I18:F)I10(I18:()I11(I18:id)I12(I18:int8)I13(I18:int10)I14(I18:int16)I29(I19:E):CEE6. CE=;#0s3s4s21ac2s53s11s12s13s14s104s11s12s13s14s105s11s12s13s14s

18、106s177s21s22s18s19s208r10r10r10r10s23s24r10r10r10r10r10r109r11r11r11r11r11r11r11r11r11r11r11r1110s11s12s13s14s1011r15r15r15r15r15r15r15r15r15r15r15r1512r16r16r16r16r16r16r16r16r16r16r16r1613r17r17r17r17r17r17r17r17r17r17r17r1714r18r18r18r18r18r18r18r18r18r18r18r1815s2616s21s22s4217s3s4s218s11s12s13

19、s14s1019s11s12s13s14s1020s11s12s13s14s1021s11s12s13s14s1022s11s12s13s14s1023s11s12s13s14s1024s11s12s13s14s1025s21s22s3526s3s4s227s38s3728r5r5s21s22r529r6r6s21s22r630r7r7s21s22r731r8r8r8r8s23s24r8r8r8r8r8r832r9r9r9r9s23s24r9r9r9r9r9r933r12r12r12r12r12r12r12r12r12r12r12r1234r13r13r13r13r13r13r13r13r13r13r13r1335r14r14r14r14r14r14r