编译原理LL1语法分析实验报告Word文档下载推荐.docx
《编译原理LL1语法分析实验报告Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《编译原理LL1语法分析实验报告Word文档下载推荐.docx（10页珍藏版）》请在冰点文库上搜索。
（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.预测分析控制程序的算法流程
输入要分析的
字符串
出错
N
判断字符串是否正确
源代码】
#include<
stdio.h>
stdlib.h>
string.h>
终结符*/非终结符*/
dos.h>
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;
j<
b;
j++）/*输出对齐符*/printf（"
"
for（j=b;
=l;
j++）
B[j]）;
\t\t\t"
}/*print1*/voidmain（）
intm,n,k=0,flag=0,finish=0;
charch,x;
typecha;
/*用来接受C[m][n]*//*把文法产生式赋值结构体*/e.origin='
;
strcpy（e.array,"
TG"
e.length=2;
t.origin='
strcpy（t.array,"
FS"
t.length=2;
g.origin='
strcpy（g.array,"
+TG"
g.length=3;
g1.origin='
g1.array[0]='
^'
g1.length=1;
s.origin='
strcpy（s.array,"
*FS"
s.length=3;
s1.origin='
s1.array[0]='
s1.length=1;
f.origin='
strcpy（f.array,"
（E）"
f.length=3;
f1.origin='
f1.array[0]='
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;
提示:
本程序只能对由'
构成的以'
结束的字符串进行分析,\n"
请输入要分析的字符串:
"
do/*读入分析串*/
scanf（"
&
ch）;
if（（ch!
='
）&
&
（ch!
）&
））
输入串中有非法字符\n"
exit
（1）;
}
B[j]=ch;
j++;
}while（ch!
l=j;
/*分析串长度*/ch=B[0];
/*当前分析字符*/A[top]='
A[++top]='
/*'
printf（"
步骤\t\tdo{
x=A[top--];
/*xprintf（"
%d"
k++）;
for（j=0;
j++）/*if（x==v1[j]）{
进栈*/
分析栈\t\t剩余字符\t\t所用产生式\n"
为当前栈顶字符*/
判断是否为终结符*/
flag=1;
break;
if（flag==1）/*
if（x=='
）
{finish=1;
/*结束标记*/printf（"
acc!
\n"
/*接受*/getchar（）;
getchar（）;
exit
（1）;
}/*if*/if（x==ch）{print（）;
print1（）;
%c匹配\n"
ch）;
ch=B[++b];
/*下一个输入字符*/flag=0;
/*恢复标记*/
}/*if*/
else/*出错处理
{print（）;
%cexit
（1）;
}/*else*/
}/*if*/else/*非终结符处理
如果是终结符*/
*/
出错\n"
/*输出出错终结符*/
j++）if（x==v2[j]）{m=j;
/*行号*/break;
if（ch==v1[j]）
n=j;
/*列号*/break;
cha=C[m][n];
if（cha.origin!
）/*判断是否为空*/
print（）;
print1（）;
%c->
cha.origin）;
/*输出产生式*/
cha.length;
j++）printf（"
cha.array[j]）;
for（j=（cha.length-1）;
j>
=0;
j--）/*产生式逆序入栈*/
A[++top]=cha.array[j];
if（A[top]=='
）/*为空则不进栈*/top--;
else/*出错处理*/
%c出错\n"
x）;
/*输出出错非终结符*/exit
（1）;
}while（finish==0）;
}/*main*/
【运行结果】
升级会员 