语法分析器的设计实验报告 一、实验内容 语法分析程序用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）分析方法。
该程序可分为如下几步： （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、求能推出空的非终结符集 I、实例中求直接推出空的 empty集的算法描述如下：
void emp（char c）{ 参数 c 为空符号
char temp[10]; 定义临时数组 int i;
for（i=0;i<=count-1;i++） 从文法的第一个产生式开始查找 { if 产生式右部第一个符号是空符号并且右部长度为 1, then 将该条产生式左部符号保存在临
时数组 temp 中 将临时数组中的元素合并到记录可推出 & 符号的数组 empty 中。 } U、求某一符号能否推出&
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€ VT ), then FIRST(c)={c} 在保存终结符元素的 non_ter[] 数组查找 c if c是非终结符(c € VN ) 在所有产生式中查找 c 所在的产生式 if 产生式右部第一个字符为终结符或空 (即cTa (a€ VT)或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 当前右部符号串可推出空且是右部符号串的最后一个字符 (即产生式为 ct Y1Y2…Yk,若对一切 1<=i<=k，均有 & € FIRST(Y i)，则将& €符号加进 FIRST(c)) the n 把空字加入到当前字符 c的FIRST集.
else 不能推出空字则结束循环 标识当前字符c已查找其FIRST集.}
3. 计算 FOLLOW FOLLOW集的构造可用如下方法来求： 对于文法中的符号 X • VN ,其FOLLOW(A)集合可反复应用下列规则计算，直到 FOLLOW(A)集合不再增大为止。 (1) 对于文法开始符号 S,因为S S,故# FOLLOW(S); (2) 若 Ar B 一：，其中 B VN^.三(VT VN)*、“(VT VN)+,贝V FIRST( -)-{ } FOLLOW(B); (3) 若 AT :• B 或 AT :• B 1 (「丄• 3，贝U FOLLOW(A) FOLLOW(B)。 FOLLOW集的算法描述如下： void FOLLOW(i nt i) X为待求的非终结符
把当前字符放到一临时数组 fo叩中,标识求已求其FOLLOW集.避免循环递归 if X 为开始符号 then # € FOLLOW(X) 对全部的产生式找一个右部含有当前字符 X的产生式 注：比如求 FOLLOW(B)则找AT a X或AT X £
)的产生式
if X在产生式右部的最后(形如产生式AT ： X) then 查找非终结符A是否已经求过其 FOLLOW集.避免循环递归 if 非终结符 A已求过其 FOLLOW集 then FOLLOW(A) € FOLLOW(X) 继续查下一条产生式是否含有 X else 求A之FOLLOW 集，并标识为 A已求其FOLLOW 集
else if X不在产生式右部的最后(形如AT.^B ：) then if右部X后面的符号串［能推出空字；then 查找P是否已经求过其 FOLLOW集.避免循环递归 if 已求过［的FOLLOW 集then
FOLLOW(A) € FOLLOW(B) 结束本次循环 else if :不能推出空字 then 求 FIRST(-) 把FIRST( 1)中所有非空元素加入到 FOLLOW(B)中 标识当前要求的非终结符 X的FOLLOW集已求过
4. 计算 SELECT! SELECT集的构造算法如下： 对所有的规则产生式 ATx : (1)若 x 不能推出空字 ，贝y SELECT(A Tx) = FIRST(x); ⑵若 x 可推出空字 ，贝y SELECT(A Tx)=FIRST(x) - { } FOLLOW(A)。 算法描述如下： for(i=0;i<=产生式总数-1;i++) 先把当前产生式右部的 FIRST集(一切非空元素，不包括&放入到当前产生式的 SELECT(i); if 产生式右部符号串可推出空字 ；then 把i指向的当前产生式左部的非终结符号的 FOLLOW集并入到SELECT(i)中
5. 判断是否LL(1)文法 要判断是否为LL(1)文法，需要输入的文法 G有如下要求： 具有相同左部的规则的 SELECT集两两不相交，即： SELECT(A T ： ) ASELECT(A T 1)=. 如果输入的文法都符合以上的要求，则该文法可以用 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; 四、算法 #in clude #in clude #in clude
char first[50][50],follow[50][50]; 〃各产生式右部的 FIRST 和左部的 FOLLOW 集合 char first1[50][50]; char select[50][50]; II所有单个符号的FIRST集合
//各个产生式的 SELECT集合 char firstflag[50],followflag[50]; //记录各符号的 FIRST 和 FOLLOW 是否已求过 char empty[20]; //记录可推出&的符号
int coun t=0; int nu mber; char start; char term in[ 50]; char non _ter[50]; char v[50]; char left[50]; char right[50][50];
//产生式的个数 //所有终结符和非终结符的总数 〃开始符号 //终结符号 //非终结符号 //所有符号 //左部 〃右部
***************************************