FIRST集、FOLLOW集、SELECT集

FIRST集、FOLLOW集、SELECT集

【预备知识】

FIRST集、FOLLOW集、SELECT集的异同:

同:求终结符的结合

异:FIRST集、FOLLOW集的对象是非终结符;SELECT的对象是产生式

【详细说明】

FIRST集:非终结符前面的终结符—组成的集合(非终结符能取ε时,ε也算)

FOLLOW集:非终结符后面紧跟着的终结符—组成的集合(如有ε,要写成#,代表停止)

SELECT集:产生式右端的第一个终结符组成的集合(如果是终结符,则直接写。如果是非终结符,一般为非终结符的FIRST集;若非终结符能取到ε,则ε后的第一个终结符也包括在内)

【例题】

考虑文法

G[S]:S → aSAb | Ab

A → cA | ε

(1)求出该文法的每个非终结符的FIRST集、FOLLOW集

FIRST(S) = {a, c, ε} FOLLOW(S) = {c, b, ε} (说明,由于S的后面没有终结符,只有非终结符A,所以先将A的first集算入,即c;而且A能取到ε,则先将ε算进来,然后将A → ε代入到S的两个产生式中,代入后S后面紧跟着的终结符就变成了b,所以b也算入S的FOLLOW集)

FIRST(A) = {c, ε} FOLLOW(A) = {b, #}(说明,在S的产生式中,A后面跟着b,所以b算入其中,A能取到ε的情况,所以ε也算入其中,由于存在A → ε时,程序停止,所以在FOLLOW集中要将ε写成#,表示停止)

(2)求出各个产生式的SELECT集

SELECT(S → aSAb) = {a}

SELECT(S → Ab) = (A能推出ε) FIRST(A) - {ε} + FOLLOW(A) = {b, c}

SELECT( A → cA) = {c}

SELECT( A → ε) = (直接取FOLLOW,并且去掉#) {b}

(3)证明该文法是LL(1)文法

其实,我们求FIRST集、FOLLOW集、SELECT集的的目的就是为了判断文法是否是LL(1)文法

LL(1)文法的含义:

第一个L表明自顶向下分析是从左向右扫描输入串;

第二个L表示分析过程中将用最左推导,

1表示只需向右看一个符号便可决定选择哪个产生式进行推导。

所以,若存在一个产生式,向右看一个符号还不能决定选择哪个产生式的时候,该文法不是LL(1)文法。

在此题中,由于SELECT(S → aSAb) ∩ SELECT(S → Ab) = {a} ∩ {b, c} = ∅,

SELECT( A → cA) ∩ SELECT( A → ε) = {c} ∩ {b} = ∅,即向右看一个符号就能决定选择哪个产生式,所以是LL(1)文法。

相关推荐

一结尾的成语
beat365在线

一结尾的成语

📅 09-04 👁️ 728
《派派》抓跟班技巧分享
beat365在线

《派派》抓跟班技巧分享

📅 09-11 👁️ 260
lol(2023年英雄联盟)代练接单平台排行榜一览
365提款会被冻结卡吗

lol(2023年英雄联盟)代练接单平台排行榜一览

📅 08-27 👁️ 8010