编译原理实验文档.doc

编译原理 实验报告学生姓名： 学 号： 学 院： 计算机与信息工程学院 专业年级： 指导教师： 开始时间： 2012年6月25日 目 录实验一 词法分析31 实验目的32 实验内容33 实验步骤34 实验结果65 实验心得6实验二 LL（1）分析61 实验目的62 实验内容73 实验步骤74 实验结果75 实验心得8实验三 逆波兰式的产生及计算81 实验目的82 实验内容83 实验步骤84 实验结果95 实验心得9实验四 算符优先分析算法101 实验目的102 实验内容103 实验步骤104 实验结果115 实验心得11实验五 LR（1）分析法121 实验目的122 实验内容122 实验步骤124 实验结果135 实验心得14附录：14实验一 词法分析1 实验目的通过设计、调试词法分析程序，实现从源程序中分出 各种单词的方法；熟悉词法分析程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标：1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。2、掌握词法分析的实现方法。3、上机调试编出的词法分析程序。2 实验内容词法分析是编译程序的第一个阶段，主要任务是对于字符串流的输入，根据词表，将关键字、变量等转化成自定义逻辑结构，就是输入源程序，去除空白符等无意义字符，然后按照各自的分类，转换成一个变量表。3 实验步骤1.词法分析的基本状态转换图图1. 词法分析状态转换图2.程序流程图如下图所示：开始是特殊符号数字掠过空格和回车符error N N N Y Y 取数是字母 Y换成属性字换成属性字读标识符 查保留字表查保留字表 N换成属性字换成属性字 Y 结束图2 词法分析流程图3.程序设计可按照状态转换图来设计，将关键字，界符，运算符保存在数组里。编写函数判断是否数组里有符合的字符串。4程序分析过程可以为一下几个步骤：（1）字符串的输入采用读取文件方式，然后将文件中的数据读入数组中。 String strs = null;public void actionPerformed(ActionEvent arg0) if(strBuffer!=null)strs = strBuffer.toString().split(#);elsestrBuffer = new StringBuffer(getContentArea().getText();strs = strBuffer.toString().split(rn);for(String str :strs)analysis.analyse(str);getAnalysisArea().setText();getAnalysisArea().setText(分析结果如下:+rn+源程序共有+strs.length+行rn+analysis.getBuffer().toString();（2）对标识符和关键字的判断 int x=0;for(int i=0;istr.length;i+)int flag=0;String str1=;char chars=stri.toCharArray();for(int j=0;j=0)&(ch=A)&(ch=a)&(ch=z)return true;elsereturn false;/* * 判断是否为关键字 * * */public void isKeyword(String str)int i=0;for(;ikeyWord.length;i+)if(str.equals(keyWordi) /是关键字System.out.println(关键字：+str);buffer.append(关键字：+str).append(rn);i=keyWord.length;/结束循环，i等于keyWord.length+1/结束循环,i等于keyWord.lengthif(i=keyWord.length)/普通标志符int j=0;for(;jidLength;j+)/在标志符表中查找是否有该标志符if(str.equals(idj)/标志符表中已经有该标志符System.out.println(标识符：+str);/输出该标志符在标志符表中的位置buffer.append(标识符：+str).append(rn);j=idLength;/结束循环，j等于idLength+1if(j=idLength)/标志符表中没有该标志符，将该标志符存入标志符表中，并返回其在符号表中的位置idLength+;/标志符新增一个ididLength-1=str;/将新标志符存放到标志符表中，索引从0开始System.out.println(标识符：+str);buffer.append(标识符：+str).append(rn);/是否为数字public void isNumber(String str)int i=0;for(;inumLength;i+)if(str.equals(numi)System.out.println(常量：+str);buffer.append(常量：+str).append(rn);i=numLength;if(i=numLength)numLength+;numnumLength-1=str;System.out.println(常量：+str);buffer.append(常量：+str).append(rn);public void analyse(String str)char ch;/存放当前字符char ch2;/存放下一个字符for(int i=0;istr.length();i+,word=)ch=str.charAt(i);/从0索引if(ch=n|ch=t|ch= );/忽略回车、Tab、空格字符else if(isDigit(ch)word=word+ch;for(int j=1;j=str.length()-i;j+)int k=i+j;if(k=(str.length()+1)/错误语句，没有;界符isNumber(word);j=str.length();/跳出循环i=i+j-1;elsech2=str.charAt(k);if(isDigit(ch2)|ch2=.)word=word+ch2;elseisNumber(word);i=i+j-1;/跳过j-1个字符j=str.length();/跳出循环else if(isLetter(ch)|ch=_)/变量以字符或者下划线开头word=word+ch;for(int j=1;j=str.length()-i;j+)int k=i+j;if(k=str.length()isKeyword(word);i=i+j-1;j=str.length();/识别到行尾，跳出循环elsech2=str.charAt(k);if(isLetter(ch2)|isDigit(ch2)|ch2=_)/变量由字母、数字或下划线组成word=word+ch2;elseisKeyword(word);i=i+j-1;/跳过j-1个字符j=str.length();/跳出循环，识别下一个单词else if(ch=+)word=word+ch;ch2=str.charAt(i+1);if(ch2=)System.out.println(符号： +ch+ch2);buffer.append(符号： +ch+ch2).append(rn);i+;elseSystem.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=-)word=word+ch;ch2=str.charAt(i+1);if(ch2=)System.out.println(符号： +ch+ch2);buffer.append(符号： +ch+ch2).append(rn);i+;elseSystem.out.println(符号：+ch);buffer.append(符号：+ch).append(rn); else if(ch=*)word=word+ch;ch2=str.charAt(i+1);if(ch2=)System.out.println(符号： +ch+ch2);buffer.append(符号： +ch+ch2).append(rn);i+;elseSystem.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=/)word=word+ch;ch2=str.charAt(i+1);if(ch2=)System.out.println(符号： +ch+ch2);/除等/=buffer.append(符号： +ch+ch2).append(rn);i+;else if(ch2=/)System.out.print(单行注释t);buffer.append(单行注释t).append(rn);System.out.print(注释内容为：);buffer.append(注释内容为：).append(rn);for(int m=i;mstr.length();m+)System.out.print(str.charAt(m);buffer.append(str.charAt(m);System.out.println();buffer.append(rn);i=str.length();/注释行/，读取下一行elseSystem.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=%)word=word+ch;ch2=str.charAt(i+1);if(ch2=)System.out.println(符号： +ch+ch2);buffer.append(符号： +ch+ch2).append(rn);i+;elseSystem.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=)word=word+ch;ch2=str.charAt(i+1);if(ch2=)System.out.println(符号： +ch+ch2);buffer.append(符号： +ch+ch2).append(rn);i+;elseSystem.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=)word=word+ch;ch2=str.charAt(i+1);if(ch2=)System.out.println(符号： +ch+ch2);buffer.append(符号： +ch+ch2).append(rn);i+;elseSystem.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=!)word=word+ch;ch2=str.charAt(i+1);if(ch2=)System.out.println(符号： +ch+ch2);buffer.append(符号： +ch+ch2).append(rn);i+;elseSystem.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=&)word=word+ch;ch2=str.charAt(i+1);if(ch2=&)System.out.println(符号： +ch+ch2);buffer.append(符号： +ch+ch2).append(rn);i+;elseSystem.out.println(非法字符&);buffer.append(非法字符&);System.out.println(位置：+line+行+i+字符);buffer.append(位置：+line+行+i+字符).append(rn);else if(ch=|)word=word+ch;ch2=str.charAt(i+1);if(ch2=|)System.out.println(符号： +ch+ch2);buffer.append(符号： +ch+ch2).append(rn);i+;elseSystem.out.println(非法字符|);buffer.append(非法字符|);System.out.println(位置：+line+行+i+字符);buffer.append(位置：+line+行+i+字符).append(rn);else if(ch=()word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=)word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=)word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=)word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=)word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=)word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=,)word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=;)word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=)word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=)word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);else if(ch=.)word=word+ch;System.out.println(符号：+ch);buffer.append(符号：+ch).append(rn);elseSystem.out.println(非法字符：+ch);buffer.append(非法字符：+ch);System.out.println(位置：+(line+1)+行+(i+1)+字符);buffer.append(位置：+(line+1)+行+(i+1)+字符).append(rn);4 实验结果图3 实验结果实验二 LL（1）分析1 实验目的根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。2 实验内容对下列文法，用LL（1）分析法对任意输入的符号串进行分析： （1）E-TE（2）E-+T E（3）E-（4）T-F T（5）T-*F T（6）T-（7）F-(E)（8）F-i程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合则输出错误信息。3 实验步骤1.定义部分：定义变量，常量；2. 根据已由的文法规则建立LL（1）分析表；3.控制部分：从键盘输入表达式符号串4.利用LL（1）分析算法对表达式进行处理：根据LL（1）分析表对表达式符号串进行堆栈或其他操作，输出分析结果。若分析遇到错误，输出错误信息。4 实验结果对输入串i+i*i#进行分析：图1 实验结果实验三 逆波兰式的产生及计算1 实验目的将用中缀式表示的算术表达式转换为用逆波兰式表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。2 实验内容编写程序将输入的中缀表达式转化为后缀表达式，并计算结果。例如，输入为：12+(33-2)*8+4-15输出如下： 后缀表达式：12&33&2&-&8&*&+&4&+&15&-计算结果:249.03 实验步骤逆波兰式定义将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算 顺序。 1.逆波兰式生成的算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字， 则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优 先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此 运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式， 确定所有字符都得到正 确处理， 我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。2.逆波兰表达式求值的算法步骤(1)构造一个栈，存放运算对象。 (2)读入一个用逆波兰式表示的简单算术表达式。 (3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则 将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个 运算对象进行该运算， 将运算结果入栈，并且将执行该运算的两个运算对象从栈 顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部 的元素弹出，将运算结果入栈。 (4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都 得到正确处理，我们便可以求出该简单算术表达式的值。4 实验结果对输入串(4+7)*6/5#进行分析及计算：后缀表达式：4&7&+&6&*&5&/计算结果:13.2对输入串4.5*10-(1+80)#进行分析及计算：后缀表达式：4.5&10&*&1&80&+&-计算结果:-36.0实验四 算符优先分析算法1 实验目的 设计、编制并调试一个算符优先分析算法，加深对此分析法的理解2 实验内容完成一个交互式面向对象的算符优先分析程序，而一个交互式面向对象的算符优先分析程序基本功能是：（1） 输入文法规则（2） 对文法进行转换（3） 生成每个非终结符的FirstVT和LastVT（4） 生成算符优先分析表（5） 再输入文法符号（6） 生成移进规约步骤3 实验步骤1.设计相关数据结构char lable20; 文法终极符集char first1010; 文法非终结符FIRSTVT集char last1010; 文法非终结符LASTVT集char st1030; 用来存储文法规则2. 算符优先分析法的分析过程及其构成（1）规定运算符之间的优先关系（终结符）和结合性（2）比较相邻运算符之间的关系以确定句型的可归约串3.分析步骤（1）判断文法是否是算符优先文法（2）构造优先关系表（3）算符优先程序寻找可归约串4 实验结果图1 实验结果实验五 LR（1）分析法1 实验目的构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。2 实验内容实验规定对下列文法，用LR（1）分析法对任意输入的符号串进行分析： （0）E-S（1）S-BB（2）B-aB（3）B-b(1)输入一以#结束的符号串(包括a，b#)：在此位置输入符号串(2)输出过程如下：步骤 状态栈 符号栈 输入串ACTIONGOTO10#Abb#S32 实验步骤2.1程序结构描述（1）定义部分：定义常量、变量、数据结构。（2）初始化：设立LR(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用LR(1)分析算法进行表达式处理：根据LR(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。2.2 LR（1）分析器结构由三部分组成：输入串XXX# 输出Xn。X1#n1。10总控程序ACTION表GOTO 表图1 LR（1）分析器构成（1）其中:SP为栈指针，Si为状态栈，Xi为文法符号栈。状态转换表用GOTOi，X=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。（2） ACTIONi，a