语法分析器的设计实验报告
一、实验内容
语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析)，先求出所输入的文法的每个非终结符是否能推出空，再分别计算非终结符号的FIRST集合，每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT集的交集是不是都为空，如果是，则输入文法符合LL(1)文法，可以进行分析。对于文法：
G[E]:
E->E+T|T
T->T*F|F
F->i|(E)
分析句子i+i*i是否符合文法。
二、基本思想
1、语法分析器实现
语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。
语法分析程序的流程图如图5-4所示。
语法分析程序流程图
该程序可分为如下几步：
（1）读入文法
（2）判断正误
（3）若无误，判断是否为LL(1)文法
（4）若是，构造分析表；
（5）由句型判别算法判断输入符号串是为该文法的句型。
三、核心思想
该分析程序有15部分组成：
（1）首先定义各种需要用到的常量和变量；
（2）判断一个字符是否在指定字符串中；
（3）读入一个文法；
（4）将单个符号或符号串并入另一符号串；
（5）求所有能直接推出&的符号；
（6）求某一符号能否推出‘& ’；
（7）判断读入的文法是否正确；
（8）求单个符号的FIRST；
（9）求各产生式右部的FIRST；
（10）求各产生式左部的FOLLOW；
（11）判断读入文法是否为一个LL(1)文法；
（12）构造分析表M；
（13）句型判别算法；
（14）一个用户调用函数；
（15）主函数；
下面是其中几部分程序段的算法思想：
1、求能推出空的非终结符集
Ⅰ、实例中求直接推出空的empty集的算法描述如下：
void emp(char c){ 参数c为空符号
char temp[10];定义临时数组
int i;
for(i=0;i<=count-1;i++)从文法的第一个产生式开始查找
{
if 产生式右部第一个符号是空符号并且右部长度为1,
then将该条产生式左部符号保存在临时数组temp中
将临时数组中的元素合并到记录可推出&符号的数组empty中。
}
Ⅱ、求某一符号能否推出'&'
int _emp(char c)
{ //若能推出&，返回1；否则，返回0
int i,j,k,result=1,mark=0;
char temp[20];
temp[0]=c;
temp[1]='\0';
存放到一个临时数组empt里,标识此字符已查找其是否可推出空字
如果c在可直接推出空字的empty[]中,返回1
for(i=0;;i++)
{
if(i==count)
return(0);
找一个左部为c的产生式
j=strlen(right[i]); //j为c所在产生式右部的长度
if 右部长度为1且右部第一个字符在empty[]中. then返回1(A->B,B可推出空)
if 右部长度为1但第一个字符为终结符,then 返回0(A->a,a为终结符)
else
{
for(k=0;k<=j-1;k++)
{
查找临时数组empt[].并标记mark-=1(A->AB)
if 找到的字符与当前字符相同(A->AB)
结束本次循环
else(mark等于0)
查找右部符号是否可推出空字,把返回值赋给result
把当前符号加入到临时数组empt[]里.
}
if 当前字符不能推出空字且还没搜索完全部的产生式
then 跳出本次循环继续搜索下一条产生式
else if //当前字符可推出空字,返回1
}
}
}
2、计算每个符号的first集：
实例中求单个符号的FIRST集的算法描述如下：
void first2 (int i) {
参数i为符号在所有输入符号中的序号
c等于指示器i所指向的符号
在保存终结符元素的termin[]数组查找c
if c为终结符(c∈V T )，then
FIRST(c)={c}
在保存终结符元素的non_ter[]数组查找c
if c是非终结符(c∈V N )
在所有产生式中查找c所在的产生式
if 产生式右部第一个字符为终结符或空(即c→a (a∈V T)或c→&) then 把a或&加进FIRST(c)
if 产生式右部第一个字符为非终结符then
if 产生式右部的第一个符号等于当前字符then
跳到下一条产生式进行查找
求当前非终结符在所有字符集中的位置
if 当前非终结符还没求其FIRST集then
查找它的FIRST集并标识此符号已求其FIRST集
求得结果并入到c的FIRST集.
if 当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符then
获取右部符号下一个字符在所有字符集中的位置
if 此字符的FIRST集还未查找then
找其FIRST集,并标其查找状态为1
把求得的FIRST集并入到c的FIRST集.
if当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为c→Y1Y2…
Y k,若对一切1<=i<=k，均有&∈FIRST(Y i)，则将&∈符号加进FIRST(c) ) then 把空字加入到当前字符c的FIRST集.
else
不能推出空字则结束循环
标识当前字符c已查找其FIRST集. }
3. 计算FOLLOW集
FOLLOW集的构造可用如下方法来求：
对于文法中的符号X V N ，其FOLLOW(A)集合可反复应用下列规则计算，直到FOLLOW(A)集合不再增大为止。
(1)对于文法开始符号S，因为S S，故#FOLLOW(S)；
(2)若A→B，其中B V N，(V T V N)*、(V T V N)+，则
FIRST()-{e}FOLLOW(B)；
(3)若A→B或A→B (e)，则
FOLLOW(A) FOLLOW(B)。
FOLLOW集的算法描述如下：
void FOLLOW(int i)
X为待求的非终结符
把当前字符放到一临时数组foll[]中,标识求已求其FOLLOW集.避免循环递归if X为开始符号then #∈FOLLOW(X)
对全部的产生式找一个右部含有当前字符X的产生式
注：比如求FOLLOW(B)则找A→αX或A→X(ε)的产生式
if X在产生式右部的最后(形如产生式A→X) then
查找非终结符A是否已经求过其FOLLOW集.避免循环递归
if 非终结符A已求过其FOLLOW集then
FOLLOW(A)∈FOLLOW(X)
继续查下一条产生式是否含有X
else
求A之FOLLOW集，并标识为A已求其FOLLOW集else if X不在产生式右部的最后(形如A→B) then
if右部X后面的符号串能推出空字 then
查找是否已经求过其FOLLOW集.避免循环递归
if 已求过的FOLLOW集then
FOLLOW(A)∈FOLLOW(B)
结束本次循环
else if 不能推出空字then
求FIRST()
把FIRST()中所有非空元素加入到FOLLOW(B)中
标识当前要求的非终结符X的FOLLOW集已求过
4.计算SELECT集
SELECT集的构造算法如下：
对所有的规则产生式A→x：
(1)若x不能推出空字e，则SELECT(A→x) = FIRST(x)；
(2)若x可推出空字e，则SELECT(A→x)=FIRST(x)–{} FOLLOW(A)。
算法描述如下：
for(i=0;i<=产生式总数-1;i++)
先把当前产生式右部的FIRST集(一切非空元素,不包括ε)放入到当前产生式的
SELECT(i);
if 产生式右部符号串可推出空字e then
把i指向的当前产生式左部的非终结符号的FOLLOW集并入到SELECT(i)中5.判断是否LL(1)文法
要判断是否为LL(1)文法，需要输入的文法G有如下要求：
具有相同左部的规则的SELECT集两两不相交，即：
SELECT(A→)∩ SELECT(A→)= ?
如果输入的文法都符合以上的要求，则该文法可以用LL(1)方法分析。
算法描述如下：
把第一条产生式的SELECT(0)集放到一个临时数组temp[]中
for(i=1;i<=产生式总数-1;i++)
求temp的长度length
if i指向的当前产生式的左部等于上一条产生式的左部then 把SELECT(i)并入到temp数组中
If temp的长度小于length加上SELECT (i)的长度
返回0
else
把temp清空
把SELECT (i)存放到temp中
结果返回1；
四、算法
#include
#include
#include
/*******************************************/
int count=0; //产生式的个数
int number; //所有终结符和非终结符的总数
char start; //开始符号
char termin[50]; //终结符号
char non_ter[50]; //非终结符号
char v[50]; //所有符号
char left[50]; //左部
char right[50][50]; //右部
char first[50][50],follow[50][50]; //各产生式右部的FIRST和左部的FOLLOW集合
char first1[50][50]; //所有单个符号的FIRST集合
char select[50][50]; //各个产生式的SELECT集合
char firstflag[50],followflag[50]; //记录各符号的FIRST和FOLLOW是否已求过
char empty[20]; //记录可推出&的符号
char nonempty[20]; //记录不可推出&的符号
char empt[20]; //求_emp()时使用
char TEMP[50]; //求FOLLOW时存放某一符号串的FIRST集合
int validity=1; //表示输入文法是否有效
int ll=1; //表示输入文法是否为LL(1)文法
int M[20][20]; //分析表
char choose; //用户输入时使用
char foll[20]; //求FOLLOW集合时使用
/*******************************************
判断一个字符c是否在指定字符串p中