站点图标

编译原理 04 Select集和LL(1)文法


  &nbsp 在前面我们已经介绍了《First集与Follow集》,下面我们将介绍Select集,以及它和LL(1)型文法的关系。

一、Select集的构造

    给定文法 G,对于产生式 A→α,α ∈ V*,则可选集 SELECT(A→α) 有:

    第 1 条是,当 α ≠ ε,且通过1次或多次推不出 ε,SELECT(A→α) = FIRST(α)
    第 2 条是,当 α ≠ ε,但 α 经有限步可推出 ε,SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)(注意是一个 α,一个 A)
    第 3 条是,当 α = ε,SELECT 集就等于左部 A 的 FOLLOW 集

1.1 下面来看一个例子:

A → BCc | gDB
B → bCDE | ε
C → DaB | ca
D → dD | ε
E → 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 }

    根据上表,可求出Select集如下:
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)型文法

2.1 LL(1)型文法的判定

    如果有相同左部的Select集交集为空,则是LL(1)型文法。

2.2 使用Select集构建LL(1)分析表

    构造方法:

  1. 若 a∈SELECT(A→α),则把 A→α 加至 M[A, a] 中。
  2. 把所有无定义的 M[A, a] 标上“出错标志”。为了使表简化,表中空白处为出错。

    下面看另一个例子:
G[S]: S → aH
H → aMd
H → d
M → Ab
M → ε
A → aM
A → e

产生式 First Follow Select
S → aH { a } FOLLOW(S) = { # } SELECT(S→aH) = FIRST(aH) = { a }
H → aMd { a } FOLLOW(H) = { # } SELECT(H→aMd) = FIRST(aMd) = { a }
H → d { d } SELECT(H→d) = FIRST(d) = { d }
M → Ab { a, e } FOLLOW(M) = { b, d } SELECT(M→Ab) = FIRST(Ad) = { a, e }
M → ε { ε } SELECT(M→ε) = FOLLOW(M) ={ d, b }
A → aM { a } FOLLOW(A) = { b } SELECT(A→aM) = FIRST(aM) = { a }
A → e { e } SELECT(A→e) = FIRST(e) = { e }

    根据上面求出的Select集,就可以写出LL(1)分析表:

a b d d
S S → aH
H H → aMd H → d
M M → Ab M → ε M → ε M → Ab
A A → aM A → e
退出移动版