编译原理FIRST、FOLLOW、SELECT集の通俗解释

简介:

1.为什么要引入FIRST集的概念?

  • 因为有公共左因子的问题,公共左公因子是指在文法的产生式集合中,某个非终结符的多个候选式具有相同的前缀。
  • 一般来说,公共左公因子的产生式为 
    Aαβ1αβ2A→αβ1│αβ2
  • 如果有公共左因子的问题,那么只能采取试探的方法来分析每一个候选式,分析的过程很可能产生回溯,回溯分析法是一种不确定的方法。
  • 若所有候选式都没有公共左因子就可以选择惟一匹配的候选式,不会产生(公共左公因子引起的)回溯。
  • 为了消除回溯,对任何一个非终结符和当前的待匹配符号,期望 
    • 要么只有一个候选式可用
    • 要么没有候选式可用

因此引入以下FIRST集合的概念:

  • α(VTVN)α∈(VT⋃VN)∗,有 
    FIRST(α){a|αa,aVT}FIRST(α)={a|α⟹∗a⋅⋅⋅,a∈VT}

    特别地,若αεα⟹∗ε,则εFIRST(α)ε∈FIRST(α)

因此对于每一文法符号 XVTVNX∈VT⋃VN,构造FIRST(X)FIRST(X)的方法为: 
使用下列规则,直至每个FIRST集不再增大为止:

  • XVTX∈VT,则FIRST(X)={X}FIRST(X)={X}(意思是如果XX是终结符,则其FIRSTFIRST集合为其自身);
  • 若 XVNX∈VN,那么XX的产生式分以下三种情况:

    • XεX→ε
    • εFIRST(X)ε∈FIRST(X)
    • XaX→a⋅⋅⋅
    • aFIRST(X)a∈FIRST(X)
    • XYX→Y⋅⋅⋅,且YVNY∈VN
    • FIRST(Y){ε}FIRST(X)FIRST(Y)–{ε}⊆FIRST(X)

    • 特例: XY1Y2Yi1YiYkX→Y1Y2⋅⋅⋅Yi−1Yi⋅⋅⋅Yk 
      且 Y1,Y2,Yi1VNY1,Y2,⋅⋅⋅Yi−1∈VN 
      Y1,Y2,Yi1εY1,Y2,⋅⋅⋅Yi−1⟹∗ε

      • FIRST(Yj){ε}FIRST(X)(1ji1)FIRST(Yi)FIRST(X)FIRST(Yj)–{ε}⊆FIRST(X)(1≤j≤i−1),FIRST(Yi)⊆FIRST(X)
    • 特别地,当Y1Y2Yi1YiYkεY1Y2⋅⋅⋅Yi−1Yi⋅⋅⋅Yk⟹∗ε

      • 则 εFIRST(X)ε∈FIRST(X)

结论:针对无空产生式的文法G,同一非终结符的任两个产生式的右部符号串的FIRST集无交集,即可进行确定的自顶向下分析。

2.为什么要引入FOLLOW集的概念?

考虑文法G[S]: 
SaAS→aA 
SdS→d 
AbASA→bAS 
AεA→ε 
求得各终结符和符号串的FIRST集合如下: 
FIRST(S)={a,d}FIRST(S)={a,d} 
FIRST(A)={b,ε}FIRST(A)={b,ε} 
FIRST(aA)={a}FIRST(aA)={a} 
FIRST(d)={d}FIRST(d)={d} 
FIRST(bAS)={b}FIRST(bAS)={b} 
FIRST(ε)={ε}FIRST(ε)={ε} 
若输入串W=abdW=abd,则试图推导出abd串的推导过程为SaAabASabSabdS⇒aA⇒abAS⇒abS⇒abd 
从以上推导过程中可以看到,在第2步到第3步的推导中,即abASabSabAS⇒abS时,因为当前面临的输入符号为dd,但是最左非终结符AA的产生式右部的开始符号集都不包含dd,但有εε,因此对于dd的匹配自然认为只能依赖于在可能的推导过程中AA的后面的符号,所以这时候选用产生式AεA→ε向下推导。而当前AA后面的符号为SSSS产生式右部的开始符号集包含了dd,所以例子中可用SdS→d推导得到匹配。 
语法树如下所示: 
这里写图片描述 
很显然,我们从以上叙述中可以得出: 
当某一非终结符的产生式中含有空产生式时,它的非空产生式右部的开始符号集两两不相交,并与在推导过程中紧跟该非终结符右部可能出现的终结符集也不相交,则仍可构造确定的自顶向下分析。因此,引入了一个文法符号的后跟符号集合。 
引入以下FOLLOW集的概念:

  • AVNA∈VN,有 
    FOLLOW(A)={a|SAaaVT}FOLLOW(A)={a|S⟹∗⋅⋅⋅Aa⋅⋅⋅,a∈VT} 
    SAS⟹∗⋅⋅⋅A,则规定#FOLLOW(A)#∈FOLLOW(A) 
    这里用#作为输入串的结束符,也称为输入串括号。

因此对于每一文法符号 AVNA∈VN,实际上求FOLLOW(A)FOLLOW(A) 
就是考察A在产生式右端的出现情况,哪些终结符号可以跟随在A后面?

使用下列规则,直至每个FOLLOW集不再增大为止:

  • 首先,设S为文法的开始符号,把{#}{#}加入FOLLOW(S)FOLLOW(S)中(这里#为句子括号)
  • BαAβB→αAβ是一个产生式,则 FIRST(β){ε}FOLLOW(A)FIRST(β)−{ε}⊆FOLLOW(A)
  • 如果BαAB→αA或者BαAβB→αAββεβ⟹∗ε,则 FOLLOW(B)FOLLOW(A)FOLLOW(B)⊆FOLLOW(A) 
    • 解释: 因为在推导过程中可能出现如下的句型序列:
    • Sα1Bβ1α1αAββ1α1αAβ1S⇒∗⋅⋅⋅α1Bβ1⋅⋅⋅⇒⋅⋅⋅α1αAββ1⋅⋅⋅⇒⋅⋅⋅α1αAβ1⋅⋅⋅

例题: 
ABCc | gDBA→BCc | gDB 
BbCDE | εB→bCDE | ε 
CDaB | caC→DaB | ca 
DdD | εD→dD | ε 
EgAf | cE→gAf | c

非终结符 FIRST FOLLOW
A {a, b, c, d, g} {f, #}
B {b, εε} {a, c, d, g, f, #}
C {a, c, d} {c, d, g}
D {d, εε} {a, b, c, g, f, #}
E {c, g} {a, c, d, g, f, #}

对于FIRST集合,解释其中的FIRST(A)的求解。

  • ABCcA→BCc属于上述产生式的特例情况,很显然BεCεB⇒∗ε,C⇏∗ε,因此 
    (FIRST(B){ε})FIRST(C)FIRST(A)(FIRST(B)−{ε})⋃FIRST(C)⊆FIRST(A)
  • AgDBA→gDB属于上述产生式的第二种情况,因此gFIRST(A)g∈FIRST(A)
  • 最后得出: 
    FIRST(A)=(FIRST(B){ε})FIRST(C){g}FIRST(A)=(FIRST(B)−{ε})⋃FIRST(C)⋃{g}
  • FIRST(B)={b,ε}FIRST(C)={a,c,d}FIRST(B)={b,ε},FIRST(C)={a,c,d}
  • FIRST(A)={a,b,c,d,g}FIRST(A)={a,b,c,d,g}

对于FOLLOW集合,有如下的计算情况:

FOLLOW(A)=(FIRST(f){ε}){#}={f,#}FOLLOW(A)=(FIRST(f)−{ε})⋃{#}={f,#}

FOLLOW(B)   =(FIRST(Cc){ε})FOLLOW(A)FOLLOW(C)={a,c,d}{f,#}FOLLOW(C)={a,c,d}{f,#}{c,d,g}={a,c,d,g,f,#}FOLLOW(B)=(FIRST(Cc)−{ε})⋃FOLLOW(A)⋃FOLLOW(C) ={a,c,d}⋃{f,#}⋃FOLLOW(C) ={a,c,d}⋃{f,#}⋃{c,d,g} ={a,c,d,g,f,#}

FOLLOW(C)  =(FIRST(c){ε})(FIRST(DE){ε})={c}(FIRST(D){ε})FIRST(E)={c,d,g}FOLLOW(C)=(FIRST(c)−{ε})⋃(FIRST(DE)−{ε}) ={c}⋃(FIRST(D)−{ε})⋃FIRST(E) ={c,d,g}

FOLLOW(D)  =(FIRST(B){ε})FOLLOW(A)(FIRST(E){ε})(FIRST(aB){ε})={b}{f,#}{c,g}{a}={a,b,c,g,f,#}FOLLOW(D)=(FIRST(B)−{ε})⋃FOLLOW(A)⋃(FIRST(E)−{ε})⋃(FIRST(aB)−{ε}) ={b}⋃{f,#}⋃{c,g}⋃{a} ={a,b,c,g,f,#}

FOLLOW(E) =FOLLOW(B)={a,c,d,g,f,#}FOLLOW(E)=FOLLOW(B) ={a,c,d,g,f,#}

3.为什么要引入SELECT集的概念?

由于从2中我们得出结论: 
当某一非终结符的产生式中含有空产生式时,它的非空产生式右部的开始符号集两两不相交,并与在推导过程中紧跟该非终结符右部可能出现的终结符集也不相交,则仍可构造确定的自顶向下分析。 
因此当文法中含有形如: 

AαAβA→αA→β

的产生式时,其中 AVN,αβVA∈VN,α、β∈V∗,若 ααββ不能同时推导出空,假定 αεβεα⇏∗ε,β⇒∗ε,则当 
FIRST(α)FOLLOW(A)= FIRST(β)FOLLOW(A)=FIRST(α)⋂FOLLOW(A)=∅ FIRST(β)⋂FOLLOW(A)=∅

也即是 FIRST(α)(FIRST(β)FOLLOW(A))=FIRST(α)⋂(FIRST(β)⋃FOLLOW(A))=∅时,对于非终结符A的替换仍可唯一地确定候选。为了表示和分析方便,因此引入了SELECT集合。 
SELECT集合定义如下:

  • 一个产生式的选择符号集SELECT。给定上下文无关文法的产生式Aα,AVN,αVA→α,A∈VN,α∈V∗,若αεα⇏∗ε,则SELECT(Aα)=FIRST(α)SELECT(A→α)=FIRST(α)

  • 如果αεα⇒∗ε,则SELECT(Aα)=(FIRST(α){ε})FOLLOW(A)SELECT(A→α)=(FIRST(α)−{ε})⋃FOLLOW(A)

因此一个上下文无关文法是LL(1)文法的充分必要条件是,对每个非终结符A的两个不同产生式,AαAβA→α,A→β,满足 

SELECT(Aα)SELECT(Aβ)=SELECT(A→α)⋂SELECT(A→β)=∅

其中 αβα、β不同时能 ε⇒∗ε

再次回到上述例题

ABCc | gDBA→BCc | gDB 
BbCDE | εB→bCDE | ε 
CDaB | caC→DaB | ca 
DdD | εD→dD | ε 
EgAf | cE→gAf | c


非终结符 FIRST FOLLOW
A {a, b, c, d, g} {f, #}
B {b, εε} {a, c, d, g, f, #}
C {a, c, d} {c, d, g}
D {d, εε} {a, b, c, g, f, #}
E {c, g} {a, c, d, g, f, #}


右部产生式 FIRST
BCc {a, b, c, d}
gDB { g }
bCDE { b }
εε {εε}
DaB {a, d}
ca { c }
dD { d }
gAf { g }
c { c }

  因此根据以上所求得的FIRST集和FOLLOW集,可求得各产生式的SELECT集合如下: 

         SELECT(ABCc)={a,b,c,d}SELECT(AgDB)={g}SELECT(BbCDE)={b}SELECT(Bε)={a,c,d,g,f,#}SELECT(CDaB)={a,d}SELECT(Cca)={c}SELECT(DdD)={d}SELECT(Dε)={a,b,c,g,f,#}SELECT(EgAf)={g}SELECT(Ec)={c}SELECT(A→BCc)={a,b,c,d} SELECT(A→gDB)={g} SELECT(B→bCDE)={b} SELECT(B→ε)={a,c,d,g,f,#} SELECT(C→DaB)={a,d} SELECT(C→ca)={c} SELECT(D→dD)={d} SELECT(D→ε)={a,b,c,g,f,#} SELECT(E→gAf)={g} SELECT(E→c)={c}

由上可知,有相同左部产生式的SELECT集合的交集为空,所以文法是LL(1)文法。

相关实践学习
阿里云图数据库GDB入门与应用
图数据库(Graph Database,简称GDB)是一种支持Property Graph图模型、用于处理高度连接数据查询与存储的实时、可靠的在线数据库服务。它支持Apache TinkerPop Gremlin查询语言,可以帮您快速构建基于高度连接的数据集的应用程序。GDB非常适合社交网络、欺诈检测、推荐引擎、实时图谱、网络/IT运营这类高度互连数据集的场景。 GDB由阿里云自主研发,具备如下优势: 标准图查询语言:支持属性图,高度兼容Gremlin图查询语言。 高度优化的自研引擎:高度优化的自研图计算层和存储层,云盘多副本保障数据超高可靠,支持ACID事务。 服务高可用:支持高可用实例,节点故障迅速转移,保障业务连续性。 易运维:提供备份恢复、自动升级、监控告警、故障切换等丰富的运维功能,大幅降低运维成本。 产品主页:https://www.aliyun.com/product/gdb
目录
相关文章
|
6月前
|
算法
lingo中的一些概念解释
lingo中的一些概念解释
|
C++
C++ Primer Plus 第八章答案 函数探幽
只有聪明人才能看见的摘要~( ̄▽ ̄~)~
86 0
|
C++
C++ Primer Plus 第五章答案 循环和关系表达式
只有聪明人才能看见的摘要~( ̄▽ ̄~)~
48 0
|
C++
C++ Primer Plus 第七章答案 函数——C++的编程模块
只有聪明人才能看见的摘要~( ̄▽ ̄~)~
64 0
|
存储 自然语言处理 C语言
C++ Primer Plus 第6版 读书笔记(5)第5章 循环和关系表达式
如本章前面所述,for 循环是一种处理数组的工具。下面进一步讨论如何使用嵌套 for 循环中来处理二 维数组。首先,介绍一下什么是二维数组。到目前为止,本章使用的数组都是一维数组,因为每个数组都可以看作是一行数据。二维数组更像是一个表格—既有数据行又有数据列。例如,可以用二维数组来表示 6 个不同地区每季度的销售额,每一个地区占一行数据。也可以用二维数组来表示 RoboDork 在计算机游戏板上的位置。
109 0
编译原理 first集 follow集 实例 解析
编译原理 first集 follow集 实例 解析
118 0
编译原理 first集 follow集 实例 解析
|
存储 JavaScript 前端开发
带你读书之“红宝书”:第三章 语法基础(中)之 数据类型中部分Number类型②
带你读书之“红宝书”:第三章 语法基础(中)之 数据类型中部分Number类型②
78 0
带你读书之“红宝书”:第三章 语法基础(中)之 数据类型中部分Number类型②
|
前端开发 JavaScript
带你读书之“红宝书”:第三章 语法基础(中)之 数据类型中部分Number类型③
带你读书之“红宝书”:第三章 语法基础(中)之 数据类型中部分Number类型③
76 0
带你读书之“红宝书”:第三章 语法基础(中)之 数据类型中部分Number类型③
|
存储 机器学习/深度学习 前端开发
带你读书之“红宝书”:第三章 语法基础(中)之 数据类型中部分Number类型①
带你读书之“红宝书”:第三章 语法基础(中)之 数据类型中部分Number类型①
66 0
带你读书之“红宝书”:第三章 语法基础(中)之 数据类型中部分Number类型①
|
存储 安全 程序员
Libra教程之:move语言的特点和例子
Libra教程之:move语言的特点和例子
Libra教程之:move语言的特点和例子