LL(1)语法分析器设计要求及实现(C)

语法分析器的设计

一． 要求：

建立一个针对LL(1)文法编译器的自动生成器。要完成此编译器的生成器需对源文件进行两遍处理：第一遍词法分析，第二遍语法分析。语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析)，然后建立词法分析器，包括词法分析主程序、扫描器部分、关键字表等。经词法分析后分别计算所输入的文法的每个非终结符号的FIRST集合，

每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT集的交集是不是都为空，如果是则输入文法符合LL(1)文法则可以进行分析。 二． 语法分析器实现

语法分析是编译过程的核心部分，它的主要任务按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。

语法分析程序的流程图如图5-4所示。

开始 读入文法 有效？ 是LL(1) 文法？ 判断句型 结束 报错 语法分析程序流程图

1.计算FIRST集

对于文法G的任意一个符号串?=X1X2…Xn可按下列步骤构造其FIRST(?)

集合：

令FIRST(?)=?，i=1；

(1) 若 Xi?VT，则Xi?FIRST(?)； (2) 若Xi?VN：

①若?FIRST(Xi)，则FIRST(Xi) ?FIRST(?)； ②若??FIRST(Xi)，则FIRST(Xi)-{?} ?FIRST(?)；

i=i+1；

重复(1)(2)，直到(Xi?VT(i=2,3,…,n)或Xi?VN 且?FIRST(Xi)或i>n为止)。 (3)若对于一切1≤i≤n，??FIRST(Xi)，则将?符号加进FIRST(?)。 实例中求单个符号的FIRST集的算法描述如下： void findSingleFIRST(int i){

参数i为符号在所有输入符号中的序号

X等于指示器i所指向的符号

在保存终结符元素的terSymbol[]数组查找X

if X为终结符(X∈VT )，then

FIRST(X)={X}

在保存终结符元素的non_ter[]数组查找X if X是非终结符(X∈VN )

在所有产生式中查找X所在的产生式

if 产生式右部第一个字符为终结符或空(即X→a (a∈VT)或X→ε) then

把a或ε加进FIRST(X)

if 产生式右部第一个字符为非终结符 then

if 产生式右部的第一个符号等于当前字符 then 跳到下一条产生式进行查找

求当前非终结符在所有字符集中的位置 if 当前非终结符还没求其FIRST集 then

查找它的FIRST集并标识此符号已求其FIRST集

求得结果并入到X的FIRST集.

if 当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符 then

获取右部符号下一个字符在所有字符集中的位置 if 此字符的FIRST集还未查找 then 找其FIRST集,并标其查找状态为1

把求得的FIRST集并入到X的FIRST集.

if当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为X→Y1Y2…Yk,若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε∈符号加进FIRST(X) ) then

把空字加入到当前字符X的FIRST集.

else

不能推出空字则结束循环

标识当前字符X已查找其FIRST集. }

2. 计算FOLLOW集

FOLLOW集的构造可用如下方法来求：

对于文法中的符号X ?VN ，其FOLLOW(A)集合可反复应用下列规则计算，直到FOLLOW(A)集合不再增大为止。

(1)对于文法开始符号S，因为SS，故#?FOLLOW(S)； (2)若A→??B?，其中B?VN，??(VT ?VN)*、??(VT ?VN)+，则

FIRST(?)-{?}?FOLLOW(B)；

(3)若A→??B或A→??B? (????)，则

FOLLOW(A) ?FOLLOW(B)。

FOLLOW集的算法描述如下： void FOLLOW(int i) X为待求的非终结符

把当前字符放到一临时数组tempFOLLOW[]中,标识求已求其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集已求过

3.计算SELECT集

SELECT集的构造算法如下： 对所有的规则产生式A→x：

(1)若x不能推出空字?，则SELECT(A→x) = FIRST(x)；

(2)若x可推出空字?，则SELECT(A→x)=FIRST(x)–{?} ? FOLLOW(A)。 算法描述如下：

for(i=0;i<=产生式总数-1;i++)

先把当前产生式右部的FIRST集(一切非空元素,不包括ε)放入到当前产生式的SELECT(i); if 产生式右部符号串可推出空字? then

把i指向的当前产生式左部的非终结符号的FOLLOW集并入到SELECT(i)中

4.判断是否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；

源码

/*************************************************** LL(1)parsing grammar

25/4/2007

***************************************************/ #include #include #include #include #include using namespace std;

/**************************************************/ //用于指向输入输出文件的指针 FILE *inparse,*outparse,*inscan; //用于接收输入输出文件名

char inparsefile[300],outparsefile[300],inscanfile[300]; /**************************************************/

/***************定义产生式的语法集结构*************/ typedef struct { char formula[200]; //产生式 }grammarElement;

grammarElement gramOldSet[200];//原始文法的产生式集

grammarElement gramNewSet[200];//消除左递归后文法的产生式集

/*********************变量定义*********************/ int grammarNum=0; //原始的产生式数目 int Pcount=0; //分解的产生式的个数 char startSymbol; //开始符号 char terSymbol[200]; //终结符号