最新编译原理LL1语法分析实验报告.docx
《最新编译原理LL1语法分析实验报告.docx》由会员分享，可在线阅读，更多相关《最新编译原理LL1语法分析实验报告.docx（17页珍藏版）》请在冰点文库上搜索。
最新编译原理LL1语法分析实验报告
学号20102798专业软件工程姓名薛建东
实验日期2013.04.08教师签字成绩
实验报告
【实验名称】LL
（1）语法分析
【实验目的】
通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。
使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练掌握开发应用程序的基本方法。
【实验内容】
根据某一文法编制调试LL
（1）分析程序，以便对任意输入的符号串进行分析。
构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。
分析法的功能是利用LL
（1）控制程序根据显示栈栈顶内容、向前看符号以及LL
（1）分析表，对输入符号串自上而下的分析过程。
【设计思想】
（1）、LL
（1）文法的定义
LL
（1）分析法属于确定的自顶向下分析方法。
LL
（1）的含义是：
第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式（规则）进行推导。
LL
（1）文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL
（1）文法,最后再进行句子分析。
需要预测分析器对所给句型进行识别。
即在LL
（1）分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。
LL
（1）分析方法要求文法满足如下条件：
对于任一非终极符A的两个不同产生式A,A，都要满足下面条件：
SELECT（A）∩SELECT（A）=
（2）、预测分析表构造
LL
（1）分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。
它的行对应文法的非终极符，列对应终极符，表中的值有两种：
一是产生式的右部的字符串，一是null。
若用M表示LL
（1）分析表，则M可表示如下：
M:
VN×VTP∪{Error}
M（A,t）=Aα，当tselect（Aα），否则
M（A,t）=Error
其中P表示所有产生式的集合。
（3）、语法分析程序构造
LL
（1）分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号，#为句子括号即输入串的括号。
分析表用一个二位数组M表示，数组元素M[A，a]中的下标A表示非终结符，a为终结符或句子括号‘#’，二维数组中存放的是一条关于A的产生式，表明当非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，则表明用A的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。
LL
（1）分析过程主要包括以下四个动作：
替换：
当XVN时选相应产生式的右部去替换X。
此时X出栈，逆序入栈。
匹配：
当XVT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。
接受：
当格局为（#，空#）时报告分析成功。
报错：
出错后，停止分析。
并给出相应的错误提示信息。
【实验要求】
1、编程时注意编程风格：
空行的使用、注释的使用、缩进的使用等。
2、如果遇到错误的表达式，应输出错误提示信息。
【流程图】
1.总体思路分析及流程图
给定一个正规文法G，在LL
（1）预测分析中，必须先求出First集和Follow集，然后求出Select集，通过Select集判断是否是LL1文法，如果是的话，构造预测分析表。
求出预测分析表之后，再输入一个字符串，依据LL1分析表单步输出字符串的分析过程。
功能模块分解图
（1）主程序流程图
（2）核心算法流程图
1.计算非终结符的First集的算法及流程：
First集合的构造算法：
（1）若X∈VT，则First（X）={X}。
（2）若X∈VN，且有产生式X→a……，则把a加入到First（X）中；若X→ε也是一条产生式，则把ε也加到First（X）中。
（3）若X→Y……是一个产生式且Y∈VN，则把First（Y）中的所有非ε-元素都加到First（X）中；若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，First（Yj）都含有ε（即Y1…Yi-1*ε），则把First（Yj）中的所有非ε-元素都加到First（X）中；特别是，若所有的First（Yj）均含有ε，j=1,2,…，k，则把ε加到First（X）中。
连续使用上面的规则，直至每个集合First不再增大为止。
2.计算非终结符的Follow集：
Follow集合的具体构造算法如下：
（1）对于文法的开始符号S，置#于Follow（S）中；
（2）若A→αBβ是一个产生式，则把First（β）|{ε}加至Follow（B）中；
（3）若A→αB是一个产生式，或A→αBβ是一个产生式而βε（即ε∈First（β）），则把Follow（A）加至Follow（B）中。
连续使用上面的规则，直至每个集合Follow不再增大为止。
3.预测分析控制程序的算法流程
【源代码】
#include
#include
#include
#include
charA[20];/*分析栈*/
charB[20];/*剩余串*/
charv1[20]={'i','+','*','（','）','#'};/*终结符*/
charv2[20]={'E','G','T','S','F'};/*非终结符*/
intj=0,b=0,top=0,l;/*L为输入串长度*/
typedefstructtype/*产生式类型定义*/
{
charorigin;/*大写字符*/
chararray[5];/*产生式右边字符*/
intlength;/*字符个数*/
}type;
typee,t,g,g1,s,s1,f,f1;/*结构体变量*/
typeC[10][10];/*预测分析表*/
voidprint（）/*输出分析栈*/
{
inta;/*指针*/
for（a=0;a<=top+1;a++）
printf（"%c",A[a]）;
printf（"\t\t"）;
}/*print*/
voidprint1（）/*输出剩余串*/
{
intj;
for（j=0;jprintf（""）;
for（j=b;j<=l;j++）
printf（"%c",B[j]）;
printf（"\t\t\t"）;
}/*print1*/
voidmain（）
{
intm,n,k=0,flag=0,finish=0;
charch,x;
typecha;/*用来接受C[m][n]*/
/*把文法产生式赋值结构体*/
e.origin='E';
strcpy（e.array,"TG"）;
e.length=2;
t.origin='T';
strcpy（t.array,"FS"）;
t.length=2;
g.origin='G';
strcpy（g.array,"+TG"）;
g.length=3;
g1.origin='G';
g1.array[0]='^';
g1.length=1;
s.origin='S';
strcpy（s.array,"*FS"）;
s.length=3;
s1.origin='S';
s1.array[0]='^';
s1.length=1;
f.origin='F';
strcpy（f.array,"（E）"）;
f.length=3;
f1.origin='F';
f1.array[0]='i';
f1.length=1;
for（m=0;m<=4;m++）/*初始化分析表*/
for（n=0;n<=5;n++）
C[m][n].origin='N';/*全部赋为空*/
/*填充分析表*/
C[0][0]=e;C[0][3]=e;
C[1][1]=g;C[1][4]=g1;C[1][5]=g1;
C[2][0]=t;C[2][3]=t;
C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1;
C[4][0]=f1;C[4][3]=f;
printf（"提示:
本程序只能对由'i','+','*','（','）'构成的以'#'结束的字符串进行分析,\n"）;
printf（"请输入要分析的字符串:
"）;
do/*读入分析串*/
{
scanf（"%c",&ch）;
if（（ch!
='i'）&&（ch!
='+'）&&（ch!
='*'）&&（ch!
='（'）&&（ch!
='）'）&&（ch!
='#'））
{
printf（"输入串中有非法字符\n"）;
exit
（1）;
}
B[j]=ch;
j++;
}while（ch!
='#'）;
l=j;/*分析串长度*/
ch=B[0];/*当前分析字符*/
A[top]='#';A[++top]='E';/*'#','E'进栈*/
printf（"步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n"）;
do
{
x=A[top--];/*x为当前栈顶字符*/
printf（"%d",k++）;
printf（"\t\t"）;
for（j=0;j<=5;j++）/*判断是否为终结符*/
if（x==v1[j]）
{
flag=1;
break;
}
if（flag==1）/*如果是终结符*/
{
if（x=='#'）
{
finish=1;/*结束标记*/
printf（"acc!
\n"）;/*接受*/
getchar（）;
getchar（）;
exit
（1）;
}/*if*/
if（x==ch）
{
print（）;
print1（）;
printf（"%c匹配\n",ch）;
ch=B[++b];/*下一个输入字符*/
flag=0;/*恢复标记*/
}/*if*/
else/*出错处理*/
{
print（）;
print1（）;
printf（"%c出错\n",ch）;/*输出出错终结符*/
exit
（1）;
}/*else*/
}/*if*/
else/*非终结符处理*/
{
for（j=0;j<=4;j++）
if（x==v2[j]）
{
m=j;/*行号*/
break;
}
for（j=0;j<=5;j++）
if（ch==v1[j]）
{
n=j;/*列号*/
break;
}
cha=C[m][n];
if（cha.origin!
='N'）/*判断是否为空*/
{
print（）;
print1（）;
printf（"%c->",cha.origin）;/*输出产生式*/
for（j=0;jprintf（"%c",cha.array[j]）;
printf（"\n"）;
for（j=（cha.length-1）;j>=0;j--）/*产生式逆序入栈*/
A[++top]=cha.array[j];
if（A[top]=='^'）/*为空则不进栈*/
top--;
}/*if*/
else/*出错处理*/
{
print（）;
print1（）;
printf（"%c出错\n",x）;/*输出出错非终结符*/
exit
（1）;
}/*else*/
}/*else*/
}while（finish==0）;
}/*main*/
【运行结果】
第五章生态系统及其稳定性复习测试
台山一中大江实验中学许楚山
总分100分时间60分钟
一．选择题：
本题共30小题，每题2分，共60分。
每小题给出的四个选项中，只有一个选项最符合题目要求。
1、在我国西部大开发战略中，“保护天然林”和“退耕还林（草）”是两项重要内容。
采取这两项措施的首要目标是（）
A、开展生态旅游B、发展畜牧业
C、增加木材产量D、改善生态环境
解析：
D
2.下列生物中，全部属于生产者的一组是（）
A．海带、梨树、酵母菌
B.蘑菇、水绵、洋葱
C．马铃薯、菠菜、乳酸菌D.硝化细菌、紫菜、苹果树
解析：
D
3．下列不属于生态系统中分解者的是（）
A．硝化细菌B．蘑菇
C．酵母菌 D．霉菌
解析：
A
4．春暖花开，蜜蜂忙
着在花丛中采蜜。
招引蜜蜂采蜜的信息属于（）
A．物理信息B．化学信息C．行为信息D．声信息
解析：
C
5.生态系统的能量流动是指（）
A.太阳能被绿色植物固定的过程B.系统内生物体能量代谢的过程
C.生态系统中能量的输入,传递,转化,和散失过程D.能量从生物体进入环境的过程
解析：
C
6．在浮游植物→小鱼→海豹→虎鲸这条食物链中，鲸增加1kg体重，至少消费浮游植物的量为（）
A．1kgB．10kgC．125kgD．1000kg
解析：
C
7．以虫治虫是生态农业的重要内容，下图表示某一生系统中四种生物所含有机物的总量。
假设这四种生物只构成一条食物链。
请问在一段时间内，如果甲的种群数量增加，其可能引起的后果是（）
A．乙和丁的种群数量都增加
升级会员 