计算first集follow集 下载本文

标准文档

编译原理实验报告

实验名称 计算first集合和follow集合

实验时间 2016年6月8日

院 系 计算机科学与技术

班 级 计算机科学与技术(1)班

学 号

姓 名

实用文案

标准文档

1.试验目的:

输入:任意的上下文无关文法。

输出:所输入的上下文无关文法一切非终结符的first集合和follow集合。

2.实验原理:

设文法G[S]=(VN,VT,P,S),则首字符集为:

* FIRST(α)={a | α?aβ,a∈VT,α,β∈V *}。

*若α?ε,ε∈FIRST(α)。

由定义可以看出,FIRST(α)是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。

设α=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);

3.实验代码与结果:

输入格式:

每行输入一个产生式,左部右部中间的→用空格代替。 非终结符等价于大写字母 ^ 表示 空

输入到文件结束,或用 0 0 结尾。

以编译原理(清华大学第二版)5.6典型例题及答案中的例题一为例(96页):

#include #include #include #include #include using namespace std; char l;

实用文案