文档介绍:语法分析器实验报告
语法分析器的设计实验报告
一、实验内容
语法分析程序用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所示。
开始
读入文法
有效?
判断句型
报错
结束
语法分析程序流程图
是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、求能推出空的非终结符集
Ⅰ、实例中求直接推出空的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且右部第一个字符在
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 产生式右部第一个字符为终结符或空(即c→a (a∈VT)或c→&) then
把a或&加进FIRST(c)
if 产生式右部第一个字符为非终结符 then
if 产生式右部的第一个符号等于当前字符 then
跳到下一条产生式进行查找
求当前非终结符在所有字符集中的位置
if 当前非终结符还没求其FIRST集 then
查找它的FIRST集并标识此符号已求其FIRST集
求得结