合肥工业大学编译原理实验

宣城校区实 验 报 告课 程 名 称 编译原理 专 业 班 级 计算机0001班 学生姓名及学号 赵保飞 2015216768 指 导 教 师 李芒宏 实 验 地 点 计算机中心楼第四机房 2017 2018 学年第 一 学期编译原理课程实验报告实验名称词法分析设计姓 名赵保飞系院专业计算机科学与技术班级计算机01班学号2015216768实验日期2017.10.18指导教师李芒宏成绩一、实验目的和要求通过本实验的编程实践，使学生了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。二、实验原理（1）实验数据结构说明KString数组-关键字表；schar数组分界符；mchar数组算术运算符；rString数组关系运算符；ArrayList型String数组ci常数；ArrayList型String数组id标识符（2）实验算法描述（3）算法流程图三、源程序代码和测试结果package lexicalAnalysis;import java.util.*;import java.io.*;public class lexicalAnalysis static String k=for,main,if,while,void,public,static,printf,scanf,asm,do,return,typedef,auto,double,break,short,using,default,long;/关键字static char s=,;,(,),;/2分界符static char m=+,-,*,/;/3算术运算符static String r=,=,;/4关系运算符ArrayList ci=new ArrayList();/5常数ArrayList id=new ArrayList();/6标识符String tempToken=;/临时存放组成一个“词”单位串int pint ,row = 1,line = 1;/当前指针指示,行数,列数char ch;/存放最新读入源程序字符String instring;/存放输入de源程序代码public static void main(String args)throws Exception/ TODO Auto-generated method stublexicalAnalysis one = new lexicalAnalysis();System.out.println(单词+t二元序列+t类 型+t位置（行，列）);one.readtext();boolean isdigit(char c)/判断所读字符是否为数字，是则返回ture,否则返回falseif(c=48 & c64&c96&c)/当其后的字符是=或时,要再读一个字符。否则不要再读。 return true;else return false; void clearBlank()/检查空白直到读入字符非空白 while(ch= ) getchar(); void getchar()pint+;if(pint = instring.length()-1)ch=instring.charAt(pint);if(ch = n)change_row_line();getchar();elsech= ;/instring数据读取完，需重新读入void retract()/读入前一个字符 pint-; ch=instring.charAt(pint); void distinguishLeter()/识别字符串tempToken=;/清空while(isletter(ch) | isdigit(ch) | isline(ch)/字母，数字，下划线仍是字符串合法组成，继续识别tempToken=tempToken + ch;getchar();void distinguishDigit()/识别数字串 tempToken=;/先将strtoken置空 while(isdigit(ch)/当数字时继续识别数字串 tempToken=tempToken+ch;/将新识别的字符加到strtoken后 getchar(); if(isletter(ch)|isline(ch)/识别完数字串而其后是字母，下划线时出错处理 while(isletter(ch)|isline(ch)|isdigit(ch)/当是字母，数字，下划线时继续识别错误数字串 tempToken=tempToken+ch;/将新识别的字符加到strtoken后 getchar(); display(0,tempToken, );/输出错误数字串 tempToken=;/将strtoken置空返回 void display(int i,String s,char a)/各种输出处理 switch(i) case -1:System.out.println(a+tError+tError+t+row+,+line+); break; case 0:System.out.println(s+tError+tError+t(+row+,+line+); break; case 1:System.out.println(s+t(1,+s+)+t关键字 +t(+row+,+line+); break; case 2:System.out.println(a+t(2,+a+)+t分界符+t(+row+,+line+); break; case 3:System.out.println(a+t(3,+a+)+t算术运算符+t(+row+,+line+); break; case 4:System.out.println(s+t(4,+s+)+t关系运算符 +t(+row+,+line+); break; case 5:System.out.println(s+t(5,+s+)+t常数+t+(+row+,+line+); break; case 6:System.out.println(s+t(6,+s+)+t标识符+t(+row+,+line+); break; line+;/列数加一 void change_row_line()/改变行数和列数row+;line=1;void handleString()/输入串处理pint=-1;/将搜索指示器置-1System.out.println(要处理的语句为 ： +instring);getchar();/读入一个字符while(pintinstring.length()/当搜索指示器没有越界时clearBlank();/检查空白直到读入读入非空if(isdigit(ch)/当ch为数字时进行数字串识别distinguishDigit();/数字串识别if(tempToken.length()!=0)/经过数字串识别后，如果strtoken不为空if(reseverci(tempToken)=-1)/如果strtoken不在ci表中，将strtoken加入ci表中ci.add(tempToken);/将strtoken加入ci表中display(5,tempToken, );/输出数字串else /如果strtoken在ci表中，仅输出display(5,tempToken, );/输出数字串else if(isletter(ch)/当ch为字母时进行字符串识别distinguishLeter();/字符串识别if(reserve(tempToken)=-1)/如果strtoken不在k表中if(reseverid(tempToken)=-1)/如果strtoken不在id表中id.add(tempToken);/将strtoken加入id表中display(6,tempToken, );/输出标识串else /如果strtoken在id表中display(6,tempToken, );/输出标识串else /如果strtoken在关键字表display(1,tempToken, );/输出关键字else if(in_s(ch)!=-1)/分界符处理包含在one.in_s(one.ch)中 else if(in_m(ch)!=-1)/算术运算符处理包含在one.in_m(one.ch)中else if(in_k(ch)!=-1)/关系运算符处理包含在one.in_k(one.ch)中elsedisplay(-1, ,ch);/errorgetchar();/读下一位int reserve(String s)/判断字符串是否是保留字int i;for(i=0;ik.length;i+)if(s.equals(ki)return i;/是保留字，就返回编码return -1;/不是保留字，就返回-1int reseverid(String s)/判断识别的标志符是否已经在id表中int i;for(i=0;iid.size();i+)if(s.equals(id.get(i)return i;/识别的标志符已经在id表中，返回位置return -1;/识别的标志符不在id表中，返回-1int reseverci(String s)/判断识别的数字串是否已经在ci表中int i;for(i=0;ici.size();i+)if(s.equals(ci.get(i)return i;/识别的数字串已经在ci表中，返回位置return -1;/识别的数字串不在ci表中，返回-1int in_s(char c)/确认分界符int i;for(i=0;is.length;i+)if(c=si)/与某个分界符配备时display(2, ,c);/输出分界符getchar();/读下一位return i;/返回所在位置return -1;/不在分界符表中int in_m(char c)/查找算术运算符int i;for(i=0;im.length;i+)if(c=mi)/与某个算术运算符配备时display(3, ,c);/输出算术运算符getchar();/读下一位return i;/返回所在位置return -1;/不在算术运算符表中int in_k(char b)/查找关系运算符int i;if(remove()=false)/读下一位为假时，进行一位关系运算符识别for(i=0;ir.length;i+)if(ri.length()=1)/当关系运算符为一位时，尝试匹配 if(ri.equals(Character.toString(b)display(4, ri, );/输出关系运算符getchar();/读下一位return i;/返回所在位置else/读下一位为假时，进行两位关系运算符识别char a=new char2;/将两位字符放入a中a0=b;getchar();a1=ch;for(i=0;iTG（2）G-+TG|-TG（3）G-（4）T-FS（5）S-*FS|/FS（6）S-（7）F-(E)（8）F-i（1）实验数据结构说明Char数组-Vn数组-非终结符表；char数组-Vt数组-终结符；String数组-Gr数组-文法；Boolean型FIRST二维数组对应每个非终结符的first集，初始化均为false；Boolean型FOLLOW二维数组对应每个非终结符的Follow集，初始化均为false;String型M二维数组对应预测分析表（2）实验算法描述算法总的来讲不是很复杂，但是细节上可能有点复杂。总的是依据本实验的数据结构FIRST和FOLLOW集，这两个数据结构虽然浪费了不少空间但是确实让程序的实现变得更简单。First()总的来求所有的非终结符的first集，first1()分工为具体求某一个具体非终结符的first集；first2()则是求某一个集体的产生式的first集。通过这三个函数的逐级分工来实现求所有的非终结符的first集。Follow集来说相对难求一点，但把它放到first集后面求来说相对简单一点。通过上面的分布设计就可以实现了。（3）算法流程图三、源程序代码和测试结果package exp3;import javax.swing.*;import java.awt.*;import java.awt.GridLayout.*;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;class WinGrid extends JFrameGridLayout grid ;JPanel chessboard;JTextField text; JTextArea textShow; JButton button; ReaderListen listener;WinGrid()init();setVisible(true); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); void init() setLayout(new FlowLayout(); text = new JTextField(10); setBounds(466,166,500,400); button = new JButton(读取); textShow = new JTextArea(9,30); listener = new ReaderListen(); listener.setJTextField(text); listener.setJTextArea(textShow); text.addActionListener(listener); button.addActionListener(listener); add(text); add(button); add(new JScrollPane(textShow); class ReaderListen implements ActionListener JTextField text; JTextArea textShow; LL one=new LL(); String s;String temp1= new String186; public void setJTextField(JTextField text) this.text = text; public void setJTextArea(JTextArea textShow) this.textShow = textShow; public String S() String t = text.getText(); return t; Override public void actionPerformed(ActionEvent e) try String s = text.getText()+#; textShow.append(s+n); textShow.append(步骤+t+分析栈+t+剩余输入串+t+所用产生式+t+动作+n); one.right(s,temp1); for(int i = 0;i18;i+) for(int k=0;kTG,G-+TG|-TG,G-,T-FS,S-*FS|/FS,S-,F-(E),F-i;/文法LL()first();/求first集 follow();/求follow集 buildM();/求预测分析表 int or(int i,String s)/返回该文法第i符号离他最近的在其右边一个“|”位置 for(i=i+1;is.length();i+) if(s.charAt(i)=|) return i;/存在，就返回位置 return -1;/返回-1表示没有“|”在其右边 int vnNum(char c)/返回c在非终结符表中的位置 int i; for(i=0;iVn.length;i+) if(c=Vni) return i;/在表中，就返回位置 return -1;/返回-1表示不在表中 int vtNum(char c)/返回c在终结符表中的位置 int i; for(i=0;iVt.length;i+) if(c=Vti) return i; return -1; void first2(String s, int j)/求关于某一个产生式s,关于第j个字符的的first集 int v=vnNum(s.charAt(0);/v是产生式左边的非终结符所在序号 int i; if(vtNum(s.charAt(j)!=-1)/若产生式右边第一个为终结符 FIRSTvvtNum(s.charAt(j)=true;/就把s.charAt(j)加入s.charAt(0)的first集 else/产生式右边第一个为非终结符if(!FIRSTvnNum(s.charAt(j)Vt.length)first1(s.charAt(j);for(i=0;iVt.length;i+)if(FIRSTvnNum(s.charAt(j)i & Vti!=)FIRSTvi=true; if(vtNum()!=-1)/终结符中有if(FIRSTvnNum(s.charAt(j)vtNum()if(j = s.length()-1)FIRSTvvtNum()=true;return ;if(s.charAt(j+1)!=|)j+;first2(s,j);elseFIRSTvvtNum()=true; void first1(char v)/求非终结符v关于该文法的first集 int i,j; String s; for(i=0;iGr.length;i+) s=Gri; if(s.charAt(0) = v) j=3; first2(s,j); while(or(j,s)!=-1&js.length() j=or(j,s); first2(s,j+1); FIRSTvnNum(v)Vt.length=true;/将fivn(v)Vt.length设为true，表示已求v的first集 void first()/求所有非终结符的first集 int i,j; for(i=0;iVn.length;i+)/遍历非终结符表求各自first集 if(!FIRSTiVt.length) first1(Vni); void follow2(String s,int j)/求关于某一个产生式的follow集 int i; if(j=s.length()-1|(js.length()-1&s.charAt(j+1)=|) if(s.charAt(0)!=s.charAt(j)/考察字符与产生式左边的非终结符不同时 if(!FOLLOWvnNum(s.charAt(0)Vt.length) follow1(s.charAt(0); for(i=0;iVt.length;i+)/产生式左边的非终结符的follow集加到考察字符的follow集中 if(FOLLOWvnNum(s.charAt(0)i) FOLLOWvnNum(s.charAt(j)i=true; if(js.length()-1&s.charAt(j+1)!=|) if(vtNum(s.charAt(j+1)!=-1)/该字符为终结符 if(VtvtNum(s.charAt(j+1)!=) FOLLOWvnNum(s.charAt(j)vtNum(s.charAt(j+1)=true; else for(i=0;iVt.length;i+)/该字符的first集中除的非终结符加入考察字符的follow集中 if(FIRSTvnNum(s.charAt(j+1)i&Vti!=) FOLLOWvnNum(s.charAt(j)i=true; if(vtNum()!=-1)/非终结符中有 if(s.charAt(0)=s.charAt(j) return; boolean m=true;/当考察字符右边的字符串的first集中有，m为真，没有时，m为假 for(i=j+1;is.length();i+) if(vtNum(s.charAt(i)!=-1) m=false; break; if(s.charAt(i)=|) break; if(!FIRSTvnNum(s.charAt(i)vtNum()/当考察字符右边的字符串中的有一非终结符的first集中不含，m为假 m=false; if(m) if(!FOLLOWvnNum(s.charAt(0)Vt.length) follow1(s.charAt(0); for(i=0;iVt.length;i+)/产生式左边的非终结符的follow集加到考察字符的follow集中 if(FOLLOWvnNum(s.charAt(0)i) FOLLOWvnNum(s.charAt(j)i=true; void follow1(char v)/求非终结符v关于该文法的follow集 if(v=E)/v为开始符号时 FOLLOWvnNum(v)vtNum(#)=true; int i,j; String s; for(i=0;iGr.length;i+) s=Gri; for(j=3;js.length();j+) if(s.charAt(j)=v)/产生式右边有考察字符 follow2(s,j);/求关于该产生式的follow集 FOLLOWvnNum(v)Vt.length=true; void follow()/求所有非终结符的follow集 int i,j; for(i=0;iVn.length;i+)/非终结符的follow集未求时 if(!FOLLOWiVt.length) follow1(Vni); void MM(int j,int i,String s,int m)/将某一个产生式填入预测分析表中 char u=Gri.charAt(0); int k; if(vtNum(Gri.charAt(j)!=-1)/为终结符if(Gri.charAt(j)!=)/Gri.charAt(j)不为时将s加到Mvn(u)vt(Gri.charAt(j)中MvnNum(u)vtNum(Gri.charAt(j)=s;else/是 for(k=0;kVt.length-1;k+)/Gri.charAt(j)为，将属于u的follow集的元素b的位置用s加到Mvn(u)vt(b)中if(FOLLOWvnNum(u)k)MvnNum(u)k=s; else/Gri.charAt(j)为非终结符for(k=0;kVt.length-1;k+)/对于终结符a属于Gri.charAt(j)的first集时，将s加到Mvn(u)vt(a)中if(FIRSTvnNum(Gri.charAt(j)k)MvnNum(u)k=s;if(FIRSTvnNum(Gri.charAt(j)vtNum()/当属于Gri.charAt(j)的first集时，将属于u的follow集的b将s加到Mvn(u)vt(b)中if(j=m-1)for(k=0;kVt.length-1;k+)if(FOLLOWvnNum(u)k)MvnNum(u)k=s;elsej=j+1; MM(j,i,s,m); void buildM()/构造预测分析表 int i,j,m; String s; for(i=0;iGr.length;i+) j=3; while(jGri.length() m=or(j,Gri); if(m=-1) m=Gri.length(); s=Gri.substring(j, m);/将j到m-1赋值到s 截取一段字符（从索引出发） MM(j,i,s,m); j=m+1; void right(String s,String t)/分析一个字符串是否符合该文法 Stack temp=new Stack();/分析栈 String tempp = t;/保存输出临时数组 String z; temp.setSize(20); temp.push(new Character(#);/初始化将#入栈 temp.push(new Character(E);/初始化将E入栈 char u,v; int i=0,j,k=0; String m,action=初始化,rule= ; while(i s.length() temppk0 = String.valueOf(k);/整数型变量赋值给字符串数组使用函数String.valueOF() u=s.charAt(i); String temp0_string =; for(j=0;j+m; if(!m.equals()/产生式m不是 action=action+,push(; for(j=m.length()-1;j-1;j-)/将产生式反序入栈 action=action+m.charAt(j); temp.push(new Character(m.charAt(j); action=action+); else/分析表中没有产生式，提示错误 rule= ; temppk+11 = 错误; /String O = String.valueOf(u); /String P = String.valueOf(v); String Q = u+t不在+v+对应的分析表中; temppk+12 = Q; return ; else/栈顶元素为终结符时 rule=; if(v=u)/栈顶元素与输入符匹配 if(v=#)/栈顶元素为#时，成功 temppk+11 = 成功; return ; else i+; action=getnext(I); else/栈顶元素与输入符不匹配，提示错误 temppk+11 = 错误; String Q = u+t不在+v+不等; temppk+12 = Q; return ; k+; return ; 四、实验评价、收获与体会从第一个实验越到第二个实验，难度着实陡增，时间有非常短，匆匆忙忙的结果是现在这一份结果。试验中的FIRST集FOLLOW集的自动化求是非常困难的，实现这一结果要密切结合初始的数据结构，所以一开始就要有系统的考虑，数据结构的设计与后面的程序功能的实现有无帮助，最好是能简化后面的功能实现。所以程序设计要先有一个总体布局，然后开动才能事半功倍。编译原理课程实验报告实验名称LR（1）分析表姓 名赵保飞系院专业计算机科学与技术班级计算机01班学号2015216768实验日期2017.11.1指导教师李芒宏成绩一、实验目的和要求构造 LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解 LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、实验原理文法： （1 ）E- E+T （2 ）E-T （3 ）T- T*F （4 ）T-F （5 ）F- (E) （6 ）F- i（1）实验数据结构说明（2）实验算法描述(1)总控程序，也可以称为驱动程序。对所有的 LR 分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的 LR 分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。（3）算法流程图三、源程序代码和测试结果#include stdafx.h#include #include #pragma warning(disable:4996)/strcpy()函数using namespace std; typedef struct Ge/存储文法char sleft;/文法左部char sright4;/文法右部sentence;typedef struct Aint move6;/移进int change6;/规约action_grid;typedef struct Gchar head3;int gt3;goto_grid;int status20