编译原理实验七：LL(1)文法的判断

实验七：LL(1)文法的判断

一：要求

输入：任意的上下文无关文法。 输出：判断是否为LL（1）文法

二：实验目的

1． 掌握LL(1)的判断，掌握求first和follow集合的算法 2． 熟悉运用C/C++语言对求first和follow集合进行实现

三：实验原理

设α＝x1x2…xn，FIRST（α）可按下列方法求得： 令FIRST（α）＝Φ，i＝1；

（1） 若xi∈VT，则xi∈FIRST（α）； （2） 若xi∈VN； ① 若ε FIRST（xi），则FIRST（xi）∈FIRST（α）； ② 若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）； （3） i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若ε FIRST（xi）或i>n为止。

当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。

设文法G[S]＝（VN，VT，P，S），则

FOLLOW（A）＝{a | S … Aa …，a∈VT}。 若S …A，#∈FOLLOW（A）。

由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。

FOLLOW集可按下列方法求得：

（1） 对于文法G[S]的开始符号S，有#∈FOLLOW（S）；

（2） 若文法G[S]中有形如B→xAy的规则，其中x，y∈V *，则FIRST（y）－{ε}∈FOLLOW（A）；

（3） 若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V *，则FOLLOW（B）∈FOLLOW（A）；

四：数据结构与算法

typedef struct Chomsky //定义一个产生式结构体 {

string left; //定义产生式的左部 string right; //定义产生式的右部 }Chomsky;

void apart(Chomsky *p,int i) //分开产生式左右部，i代表产生式的编号 string is_empty(Chomsky *p)//判断某非终结符能否直接推出空，空用#代替 string isempty(Chomsky *p)//可以间接推出空的非终结符 void search(Chomsky *p,int n)//提取产生式中的非终结符

void First(Chomsky *p,int n,char m,int mm)//求文法中非终结符的First集

void Follow(Chomsky *p,int n,int m)//求文法的follow集 string erase(string s)//去First集及follow集中的重复字符

void select(string s1,string s2)//求产生式的select集,s1是产生式左部，s2是产生式右部

五：出错分析

1:select集计算不出，关键在于能产生空的非终结符没有求出来 2:单个符号的first集与一串符号的first集区别

3:实验最后没能输出select集，没能判断出来是否是LL(1)文法

2

六：实验结果与分析

3

七：源代码

#include #include

using namespace std; #define max 100

typedef struct Chomsky //定义一个产生式结构体 {

string left; //定义产生式的左部 string right; //定义产生式的右部 }Chomsky;

int n;//产生式总数

string strings;//存储产生式

string noend;//存放文法中的非终结符

string empty;//存放可以推出空的非终结符 string first[max];//存放非终结符的first集 string follow[max];//存放非终结符的follow集 string select[max];//存放产生式的select集

void apart(Chomsky *p,int i) //分开产生式左右部，i代表产生式的编号 { int j;

for(j=0;j

/*string is_empty(Chomsky *p)//判断某非终结符能否直接推出空，空用#代替 { //如果可以，返回1 //不可以，返回0 int i; string s; for(i=0;i

4

} } s=empty; return s;//s存放能直接推出空的非终结符 }

string isempty(Chomsky *p)//可以间接推出空的非终结符 { int i,j; string s1; for(i=0;i=0)//若此非终结符已经存在直接推出空那里，在此无需重复计算 { } else { for(j=0;j<(int)p[i].right.length();j++) { if(is_empty(p).find(p[i].right.[j])<0) { } } if(j==(int)p[i].right.length())//如果右部所有符号都在直接推出空那里，则此左部也可以推出空 { s1=s1+p[i].left[0]; } } } }*/

void search(Chomsky *p,int n)//提取产生式中的非终结符 { int i,j; for(i=0;i=0&&noend.find(p[i].left[0])

5

本文来源：https://www.bwwdw.com/article/56gh.html