编译原理课程设计语法分析器.docx
《编译原理课程设计语法分析器.docx》由会员分享，可在线阅读，更多相关《编译原理课程设计语法分析器.docx（14页珍藏版）》请在冰点文库上搜索。
编译原理课程设计语法分析器
计算机类
课程设计报告
课程名称：
编译原理
课程设计题目：
语法分析器
姓名：
系：
计算机
专业：
计算机科学与技术
年级：
学号：
指导教师：
职称：
副教授
2011~2012学年第二学期
目录
1正则表达式1
1.1正则表达式1
1.2确定化（化简）后的状态转换图1
1.3分析程序代码1
1.4程序运行截图2
1.5小结3
2LL
（1）分析4
2.1LL
（1）文法4
2.2LL
（1）预测分析表4
2.3分析程序代码4
2.4程序运行截图7
2.5小结8
参考文献：
8
1正则表达式
1.1正则表达式
ab（a|b）*ba
1.2确定化（化简）后的状态转换图
1.3分析程序代码
importjava.util.Scanner;
importjava.util.regex.Matcher;
importjava.util.regex.Pattern;
//导入所需要的包
publicclassRegTest{//创建类RegTest
staticbooleantest（Strings1,Strings2）{
/*编写测试函数返回布尔类型，用于验证输入字符串与要验证的表达式是否符合*/
Patternp=Ppile（s1）;//正则表达式
Matcherm=p.matcher（s2）;//操作字符串
booleanb=false;
//p=Ppile（s1）;//
//m=p.matcher（s2）;
b=m.matches（）;
//判断是否满足是则返回true否返回false
if（b==false）{
System.out.println（"您输入的不符合您要求的正则表达式"）;
}else{
System.out.println（"符合您所输入的正则表达式"）;
}
returnb;
}
publicstaticvoidmain（String[]args）{
//主函数
Scannercin=newScanner（System.in）;
//用于输入字符串
Strings;
while（true）{
System.out.println（"请输入正则表达式：
"）;
Strings1=cin.nextLine（）;
System.out.println（"请输入字符串:
"）;
Strings2=cin.nextLine（）;
//输入表达式和要验证的字符串
test（s1,s2）;
//调用函数，测试是否符合要验证的表达式
while（true）{
System.out.println（"是否继续验证该表达式？
（yes/no）"）;
s=cin.nextLine（）;
//如果还想继续验证刚才输入的表达式，可以继续输入字符串
if（!
s.equals（"yes"））{
break;
}
System.out.println（"请输入字符串:
"）;
s2=cin.nextLine（）;
test（s1,s2）;
//调用函数，测试是否符合要验证的表达式
}
System.out.println（"是否继续验证正则表达式？
（yes/no）"）;
s=cin.nextLine（）;
//如果需要验证其他字符串的话,可以继续输入
if（!
s.equals（"yes"））{
break;
}
}
}
}
1.4程序运行截图
1.5小结
总的来说对于正则表达有一定的了解，正则表达简单来说不算难，但是要深入就很难。
通过这次的报告，我清楚了解到正则表达式在实际的生活中其实还是很有用的，需要用的地方很多，编译原理，不止在编程上有用处，在实际生活中也是用处很大的。
对于现在的我来说正则表达式，只能算是了解，还得继续学习。
2LL
（1）分析
2.1LL
（1）文法
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→（E）|i
2.2LL
（1）预测分析表
i
+
*
（
）
#
E
E→TE'
E→TE'
E'
E'→+TE'
E'→ε
E'→ε
T
T→FT'
T→FT'
T'
T'→ε
T'→*FT'
T'→ε
T'→ε
F
F→i
F→（E）
2.3分析程序代码
importjava.util.ArrayList;
importjava.util.Scanner;
publicclassLL1Analysis{
publicstaticvoidmain（Stringa[]）
{
intid=1;
intindex1=1;//记录栈最后一个非终结符的位置
StringtopStack,topIn,operation;
StringBufferinString=null;
ArrayListlist=newArrayList（）;
System.out.println（"请输入一个语句:
"）;
Scannerin=newScanner（System.in）;
Stringins=in.nextLine（）.trim（）;
if（ins.indexOf（"#"）<0）//假如最后完了输入#号也没事
ins+="#";
else
ins=ins.substring（0,ins.indexOf（"#"）+1）;//截取#号在内的前部
inString=newStringBuffer（ins）;
intkong=inString.indexOf（""）;
while（kong>=0）//去掉输入串表达式中的空格
{
inString.delete（kong,kong+1）;
kong=inString.indexOf（""）;
}
StringBufferstack=newStringBuffer（"#E"）;//分析栈，初始放入E
Stringll[][]={{"","i","+","*","（","）","#"},
{"E","E’T/P","","","E’T/P","",""},
{"E’","","E’T/N","","","ε/P","ε/P"},
{"T","T’F/P","","","T’F/P","",""},
{"T’","","ε/P","T’F/N","","ε/P","ε/P"},
{"F","ε/N","","","）E/N","",""},
{"）","","","","","ε/N",""},
{"#","","","","","","acc"}
};//ll
（1）分析矩阵
System.out.println（"LL
（1）分析过程如下：
"）;
System.out.println（"\n序号\t分析栈"+getBlank（20）+"输入数据"+getBlank（20）+"动作"）;
StringBufferliutemp=null;
while（stack.length（）>0）
{
intx=0,y=0;//记录在分析表中的的横纵坐标
if（stack.toString（）.endsWith（"\'"）||stack.toString（）.endsWith（"’"））//证明是带了一撇的非终结符
index1=stack.length（）-2;//
else
index1=stack.length（）-1;
topStack=String.valueOf（stack.substring（index1,stack.length（）））;//栈顶元素
if（inString.length（）>0）
topIn=String.valueOf（inString.charAt（0））;//剩余输入串的第一个元素
else
topIn="";
for（inti=1;iif（topStack.equals（ll[i][0]））
{
x=i;
break;
}
for（inti=1;iif（topIn.equals（ll[0][i]））
{
y=i;
break;
}
operation=ll[x][y];//动作命令
if（operation.length（）>=3）
{
Stringfirst=operation.substring（0,operation.length（）-2）;//替换部分
Stringlast=operation.substring（operation.length（）-2,operation.length（））;//是否换行部分
if（first.equals（"ε"））//如果是空字符，有不要加入栈
first="";
if（operation.equals（"acc"））
{
if（stack.length（）==1&&inString.length（）==1）
{
System.out.println（id+"\t"+stack+getBlank（21-stack.length（）-inString.length（））+inString+getBlank（11-operation.length（））+operation）;
stack.delete（0,1）;
inString.delete（0,1）;
System.out.println（"匹配成功！
"）;
}
else
{
System.out.println（id+"\t"+stack+getBlank（21-stack.length（）-inString.length（））+inString+getBlank（6）+"error"）;
System.out.println（"不能完整匹配！
"）;
}
}
elseif（last.equals（"/P"））
{
System.out.println（id+"\t"+stack+getBlank（21-stack.length（）-inString.length（））+inString+getBlank（11-operation.length（））+operation）;
stack.replace（index1,index1+topStack.length（）,first）;//把栈顶元素替换为分析表中值
if（first.equals（""））
list.add（ll[x][0]+"->ε"）;
else{
liutemp=newStringBuffer（first）;
list.add（ll[x][0]+"->"+reverse（liutemp））;
}
id++;
}elseif（last.equals（"/N"））
{
System.out.println（id+"\t"+stack+getBlank（21-stack.length（）-inString.length（））+inString+getBlank（11-operation.length（））+operation）;
stack.replace（index1,index1+topStack.length（）,first）;
inString.delete（0,1）;//相当于读下一个元素
liutemp=newStringBuffer（first）;
list.add（ll[x][0]+"->"+topIn+reverse（liutemp））;
if（stack.toString（）.endsWith（"\'"）||stack.toString（）.endsWith（"’"））
index1=stack.length（）-2;//重新设置index1值
else
index1=stack.length（）-1;
id++;
}else{
System.out.println（"分析表构造出错！
"）;
System.exit（0）;
}
}elseif（y==0）{
System.out.println（id+"\t"+stack+getBlank（21-stack.length（）-inString.length（））+inString+getBlank（6）+"error"）;
System.out.println（"输入的符号不符合规定文法！
"）;
System.exit（0）;
}elseif（x!
=0&&y!
=0&&operation.length（）==0）
{
System.out.println（id+"\t"+stack+getBlank（21-stack.length（）-inString.length（））+inString+inString+getBlank（6）+"error"）;
System.out.println（"输入符号串不完整！
"）;
System.exit（0）;
}
}
System.out.println（"\n该语句自顶向下构建语法树过程：
"）;
for（inti=0;iSystem.out.println（list.get（i））;
}
publicstaticStringBufferreverse（StringBufferbuffer）{//字母、运算符倒置
StringBufferbuf=newStringBuffer（）;
intix=-1;
intlength=0;
if（buffer.indexOf（"'"）<0&&buffer.indexOf（"’"）<0）
buf.append（buffer.reverse（））;
else{
while（buffer.length（）>0）{
length=buffer.length（）;
if（buffer.charAt（length-1）=='\''||buffer.charAt（length-1）=='’'）
{
buf.append（buffer.substring（length-2,length））;
buffer.delete（length-2,length）;
}else{
buf.append（buffer.charAt（length-1））;
buffer.delete（length-1,length）;
}
}
}
returnbuf;
}
publicstaticStringgetBlank（intn）{//得到n个连续空格
Stringblank="";
for（inti=0;iblank+="";
returnblank;
}
}
2.4程序运行截图
2.5小结
对于LL
（1）分析法有一定了解，对于完成整个算法还是挺吃力的，查看的相当的一些资料，才慢慢理解，并且慢慢的想出其算法。
最后才能根据算法写出来，并运行。
总的来说对于算法有了更深刻的理解。
算法在计算机中用处还真是挺大的。
参考文献：
[1]杨德芳主编.编译原理实用教程[M].北京：
中国水利水电出版社，2007
升级会员 