当前位置：首页 > 编程日记 > 正文

FIRST集与FOLLOW集构造步骤

编程日记 2024-09-15 06:50:00

首先，这两个集主语是候选式，是V*中的一个终结符/非终结符。
由于FOLLOW集的定义和构造步骤里面都涉及FIRST集，故先介绍FIRST集。

一.FIRST集的定义如下：
FIRST(α)={a|α=>aβ, a∈Vt, α, β∈V*},若α=>(*)ε则规定ε∈FRIST(α)。
先看这个定义的主干部分，首符集里面的组成元素都是终结符，什么样的终结符？产生式右边第一个位置上的终结符，它会被纳入产生式左边的非终结符的首符集。
这个定义的补充部分意思是，如果非终结符可经多步推到得到ε，那么ε也纳入它的首符集。

二. FIRST集的构造步骤如下：
1.若X ∈Vt，则FIRST(X)={X}

2.若X∈Vn，且有产生式X→a…，则把a加入到FIRST(X)中；
若X→ɛ也是一个产生式，则把ɛ也加到FIRST(X)中。

3.若X→Y…是一个产生式且Y∈Vn，则把FIRST(Y)中的所有非ɛ元素都加到FIRST(X)中；若X → Y1Y2…YK 是一个产生式，Y1,Y2,…,Y(i-1)都是非终结符，而且，对于任何j,1≤j ≤i-1, FIRST(Yj)都含有ɛ (即Y1…Y(i-1) =>(*)ɛ)，则把 FIRST(Yj)中的所有非ɛ元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj , j=1,2,…,K)均含有ɛ，则把 ɛ 加到FRIST(X)中。

三. FOLLOW集的定义如下：
FOLLOW(A)={a | S=>()μ A β且a ∈ FRIST(β)，μ ∈V，β∈V+ }
若S=>()u A β ，且β=>()ε，则#∈FOLLOW(A)
同样，我们先看这个定义的主干部分，FOLLOW集里面的元素都来自首符集，说明也都是非终结符，与首符集不同的是，A的FOLLOW集，A出现在产生式的右侧，而不是左侧。
这个定义的补充部分意思是，如果一个产生式经过多部推导后得到u A β，而跟在A后面的β又能够经过多步推导得到ε，则把#加到FOLLOW(A)。

四．FOLLOW集的构造步骤如下：
1 对于文法的开始符号S，置#于FOLLOW(S) 中。
2 若A→α B β是一个产生式，则把FIRST(β)中的所有非ɛ元素加至FOLLOW(B)中，把FIRST(β)中的ε换成#加至FOLLOW(B)。
3 若A→α B是一个产生式，或A→ αBβ是一个产生式而β=>(*)ɛ (即 ɛ∈FIRST(β))，则把FOLLOW(A)加至FOLLOW(B)中。

五.举个例子
G[ E]:
(1) E → TE’
(2) E’ → +TE’
(3) E’→ ɛ
(4) T → FT’
(5) T’→ *FT’
(6) T’ → ɛ
(7) F → (E)
(8) F → i
试找出文法G的FIRST集and FOLLOW集
（请拿出纸笔按照上面的步骤走一遍哦~）
在这里插入图片描述

一起看一下答案吧~
各非终结符的FIRST集合如下：
FIRST(E)=｛(,i｝
FIRST(E’)=｛+,ε｝
FIRST(T)=｛(,i｝
FIRST(T’)=｛*,ε｝
FIRST(F)=｛(,i｝

各非终结符的FOLLOW集合为：
FOLLOW(E)=｛),＃｝
FOLLOW(E’)=｛) ,＃｝
FOLLOW(T)=｛＋,) ,＃｝
FOLLOW(T’)=｛＋,) ,#}
FOLLOW(F)=｛*,＋,),#}

提示：注意那些会推导出ε的候选式引发的连锁效应。

https://www.dkcj.cn/info/18797.html

FIRST集与FOLLOW集构造步骤

相关文章：

Bossie Awards 2013:最佳开源数据中心和云软件

Laravel开启跨域的方法

【组队学习】【33期】动手学数据分析

LL(1)预测分析表的构造

新的sublime text已经上传网盘，地址写在下面

WebAssembly Studio：Mozilla提供的WASM工具

【组队学习】【33期】3. 李宏毅机器学习（含深度学习）

Linux 引导和系统启动

【数据结构】支持四则混合运算的计算器(转)

TypeScript学习笔记之接口（Interface）

【组队学习】【33期】数据可视化（Matplotlib）

布尔定理及证明（完整版）

创建DLL动态链接库——声明导出法

【组队学习】【33期】Scratch（一级）

Bzoj2780: [Spoj]8093 Sevenk Love Oimaster

LR分析法从理解到运用

Android 判断SD卡是否存在及容量查询

Spring Boot 教程（三）： Spring Boot 整合Mybatis

电子学会软件编程（图形化）一级训练营

win10 安装 python报错-已安装这个产品的另一版本

POJ1276Cash Machine

Python中处理时间 —— time模块

学编程必看：逻辑思维测试

explicit specialization of ‘Race‘ after instantiation ，implicit instantiation first required here。

（转载）Linux usbtouchscreen驱动分析

关于事务隔离级别

Datawhale组队学习周报（第047周）

讲座记录：从码农到架构师（精简版）

Enterprise Library 4 数据访问应用程序块

虚拟货币市值回调到4100亿整数关口，EOS逆势站上100关口