广东海洋大学编译原理实验3.docx
《广东海洋大学编译原理实验3.docx》由会员分享,可在线阅读,更多相关《广东海洋大学编译原理实验3.docx(17页珍藏版)》请在冰点文库上搜索。
广东海洋大学编译原理实验3
GDOU-B-11-112
广东海洋大学学生实验报告书(学生用表)
实验名称
实验3:
LL
(1)语法分析
课程名称
编译原理
课程号
16242211
学院(系)
数学与计算机学院
专业
计算机科学与技术
班级
计科1141
学生姓名
学号
实验地点
科425
实验日期
2017.4.21
1、实验目的
熟悉语法分析的过程;理解相关文法的步骤;
熟悉First集和Follow集生成。
二、实验要求
对于给定的文法,试编写调试一个语法分析程序:
要求和提示:
(1)可选择一种你感兴趣的语法分析方法(LL
(1)、算符优先、递归下降、
SLR
(1)等)作为编制语法分析程序的依据。
(2)对于所选定的分析方法,如有需要,应选择一种合适的数据结构,以构造
所给文法的机内表示。
(3)能进行分析过程模拟。
如输入一个句子,能输出与句子对应的语法树,能
对语法树生成过程进行模拟;能够输出分析过程每一步符号栈的变化情况。
设计一个由给定文法生成First集和Follow集并进行简化的算法动态模拟。
三、实验过程
1文法:
E->TE’
E’->+TE’|ε
T->FT’
T’->*FT’|ε
F->(E)|i:
2程序描述(LL
(1)文法)
本程序是基于已构建好的某一个语法的预测分析表来对用户的输入字符串进行分析,判断输入的字符串是否属于该文法的句子。
基本实现思想:
接收用户输入的字符串(字符串以“#”表示结束)后,对用做分析栈的一维数组和存放分析表的二维数组进行初始化。
然后取出分析栈的栈顶字符,判断是否为终结符,若为终结符则判断是否为“#”且与当前输入符号一样,若是则语法分析结束,输入的字符串为文法的一个句子,否则出错若不为“#”且与当前输入符号一样则将栈顶符号出栈,当前输入符号从输入字符串中除去,进入下一个字符的分析。
若不为“#”且不与当前输入符号一样,则出错。
3流程图
本程序中使用以下文法作对用户输入的字符串进行分析:
E→TE’
E’→+TE’|ε
T→FT’
T’→*FT’|ε
F→i|(E)
该文法的预测分析表为:
四、结果及截图
11、显示预测分析表,提示用户输入字符串
2、输入的字符串为正确的句子:
3、输入的字符串中包含了不属于终结符集的字符
4、输入的字符串不是该文法能推导出来的句子
五、程序代码:
packagecomplier;
importjava.io.*;
publicclassLL{
StringVn[]={"E","E'","T","T'","F"};//非终结符集
StringVt[]={"i","+","*","(",")","#"};//终结符集
StringP[][]=newString[5][6];//预测分析表
Stringfenxi[];//分析栈
intcount=1;//步骤
intcount1=1;//’分析栈指针
intcount2=0,count3=0;//预测分析表指针
StringinputString="";//输入的字符串
booleanflag;
publicvoidsetCount(intcount,intcount1,intcount2,intcount3){
this.count=count;
this.count1=count1;
this.count2=count2;
this.count3=count3;
flag=false;
}
publicvoidsetFenxi(){//初始化分析栈
fenxi=newString[20];
fenxi[0]="#";
fenxi[1]="E";
}
publicvoidsetP(){//初始化预测分析表
for(inti=0;i<5;i++){
for(intj=0;j<6;j++){
P[i][j]="error";
}
}
P[0][0]="->TE'";
P[0][3]="->TE'";
P[1][1]="->+TE'";
P[1][4]="->ε";
P[1][5]="->ε";
P[2][0]="->FT'";
P[2][3]="->FT'";
P[3][1]="->ε";
P[3][2]="->*FT'";
P[3][4]="->ε";
P[3][5]="->ε";
P[4][0]="->i";
P[4][3]="->(E)";
//打印出预测分析表
System.out.println("已构建好的预测分析表");
System.out.println("----------------------------------------------------------------------");
for(inti=0;i<6;i++){
System.out.print(""+Vt[i]);
}
System.out.println();
System.out.println("----------------------------------------------------------------------");
for(inti=0;i<5;i++){
System.out.print(""+Vn[i]+"");
for(intj=0;j<6;j++){
intl=0;
if(j>0){
l=10-P[i][j-1].length();
}
for(intk=0;kSystem.out.print("");
}
System.out.print(P[i][j]+"");
}
System.out.println();
}
System.out.println("----------------------------------------------------------------------");
}
publicvoidsetInputString(Stringinput){
inputString=input;
}
publicbooleanjudge(){
StringinputChar=inputString.substring(0,1);//当前输入字符
booleanflage=false;
if(count1>=0){
for(inti=0;i<6;i++){
if(fenxi[count1].equals(Vt[i])){//判断分析栈栈顶的字符是否为终结符
flage=true;
break;
}
}
}
if(flage){//为终结符时
if(fenxi[count1].equals(inputChar)){
if(fenxi[count1].equals("#")&&inputString.length()==1){//栈顶符号为结束标志时
//System.out.println("最后一个");
Stringfenxizhan="";
for(inti=0;i<=P.length;i++){//拿到分析栈里的全部内容(滤去null)
if(fenxi[i]==null){
break;
}else{
fenxizhan=fenxizhan+fenxi[i];
}
}
//输出当前分析栈情况,输入字符串,所用产生式或匹配
System.out.print(""+count);
StringcountToString=Integer.toString(count);
intfarWay=14-countToString.length();
for(intk=0;kSystem.out.print("");
}
System.out.print(fenxizhan);
farWay=20-fenxizhan.length();
for(intk=0;kSystem.out.print("");
}
System.out.print(inputString);
farWay=25-inputString.length();
for(intk=0;kSystem.out.print("");
}
System.out.println("接受");
flag=true;
returntrue;
}else{//分析栈栈顶符号不为结束标志符号时
Stringfenxizhan="";
for(inti=0;i<=P.length;i++){//拿到分析栈里的全部内容(滤去null)
if(fenxi[i]==null){
break;
}else{
fenxizhan=fenxizhan+fenxi[i];
}
}
//输出当前分析栈情况,输入字符串,所用产生式或匹配
System.out.print(""+count);
StringcountToString=Integer.toString(count);
intfarWay=14-countToString.length();
for(intk=0;kSystem.out.print("");
}
System.out.print(fenxizhan);
farWay=20-fenxizhan.length();
for(intk=0;kSystem.out.print("");
}
System.out.print(inputString);
farWay=25-inputString.length();
for(intk=0;kSystem.out.print("");
}
System.out.println("\""+inputChar+"\""+"匹配");
//将栈顶符号出栈,栈顶指针减一
fenxi[count1]=null;
count1-=1;
if(inputString.length()>1){//当当前输入字符串的长度大于1时,将当前输入字符从输入字符串中除去
inputString=inputString.substring(1,inputString
.length());
}else{//当前输入串长度为1时
inputChar=inputString;
}
//System.out.println(""+count+""+fenxizhan+"
//"+inputString+""+P[count3][count2]);
//System.out.println(count+inputChar+"匹配");
count++;
judge();
}
}else{//判断与与输入符号是否一样为结束标志
System.out.println("分析到第"+count+"步时出错!
");
flag=false;
returnfalse;
}
}else{
//非终结符时
booleanfla=false;
for(inti=0;i<6;i++){//查询当前输入符号位于终结符集的位置
if(inputChar.equals(Vt[i])){
fla=true;
count2=i;
break;
}
}
if(!
fla){
System.out.println("分析到第"+count+"步时出错!
");
flag=false;
returnfalse;
}
for(inti=0;i<5;i++){//查询栈顶的符号位于非终结符集的位置
if(fenxi[count1].equals(Vn[i])){
count3=i;
break;
}
}
if(P[count3][count2]!
="error"){//栈顶的非终结符与输入的终结符存在产生式时
Stringp=P[count3][count2];
Strings1=p.substring(2,p.length());//获取对应的产生式
if(s1.equals("ε")){//产生式推出“ε”时
Stringfenxizhan="";
for(inti=0;i<=P.length;i++){
if(fenxi[i]==null){
break;
}else{
fenxizhan=fenxizhan+fenxi[i];
}
}
//输出当前分析栈情况,输入字符串,所用产生式或匹配
System.out.print(""+count);
StringcountToString=Integer.toString(count);
intfarWay=14-countToString.length();
for(intk=0;kSystem.out.print("");
}
System.out.print(fenxizhan);
farWay=20-fenxizhan.length();
for(intk=0;kSystem.out.print("");
}
System.out.print(inputString);
farWay=25-inputString.length();
for(intk=0;kSystem.out.print("");
}
System.out.println(fenxi[count1]+P[count3][count2]);
//将栈顶符号出栈,栈顶指针指向下一个元素
fenxi[count1]=null;
count1-=1;
count++;
judge();
}else{//产生式不推出“ε”时
intk=s1.length();
Stringfenxizhan="";
for(inti=0;i<=P.length;i++){
if(fenxi[i]==null){
break;
}else{
fenxizhan=fenxizhan+fenxi[i];
}
}
//输出当前分析栈情况,输入字符串,所用产生式或匹配
System.out.print(""+count);
StringcountToString=Integer.toString(count);
intfarWay=14-countToString.length();
for(into=0;oSystem.out.print("");
}
System.out.print(fenxizhan);
farWay=20-fenxizhan.length();
for(into=0;oSystem.out.print("");
}
System.out.print(inputString);
farWay=25-inputString.length();
for(into=0;oSystem.out.print("");
}
System.out.println(fenxi[count1]+P[count3][count2]);
for(inti=1;i<=k;i++){//将产生式右部的各个符号入栈
Strings2=s1.substring(s1.length()-1,s1.length());
s1=s1.substring(0,s1.length()-1);
if(s2.equals("'")){
s2=s1.substring(s1.length()-1,s1.length())+s2;
i++;
s1=s1.substring(0,s1.length()-1);
}
fenxi[count1]=s2;
if(icount1++;
//System.out.println("count1="+count1);
}
//System.out.println(""+count+""+fenxizhan+"
//"+inputString+""+P[count3][count2]);
count++;
//System.out.println(count);
judge();
}
}else{
System.out.println("分析到第"+count+"步时出错!
");
flag=false;
returnfalse;
}
}
returnflag;
}
publicstaticvoidmain(Stringargs[]){
LLl=newLL();
l.setP();
Stringinput="";
booleanflag=true;
while(flag){
try{
InputStreamReaderisr=newInputStreamReader(System.in);
BufferedReaderbr=newBufferedReader(isr);
System.out.println();
System.out.print("请输入字符串(输入exit退出):
");
input=br.readLine();
}catch(Exceptione){
e.printStackTrace();
}
if(input.equals("exit")){
flag=false;
}else{
l.setInputString(input);
l.setCount(1,1,0,0);
l.setFenxi();
System.out.println();
System.out.println("分析过程");
System.out.println("----------------------------------------------------------------------");
System.out.println("步骤|分析栈|剩余输入串|所用产生式");
System.out.println("----------------------------------------------------------------------");
booleanb=l.judge();
System.out.println("----------------------------------------------------------------------"