FIRST集合和FOLLOW集合求法

FIRSTFIRST集合求法

  1. 对于形如XaX \to a \dots,则将aa添加进FIRST(X)FIRST(X)
  2. 对于形如XεX \to \varepsilon,则将ε\varepsilon添加进FIRST(X)FIRST(X)
  3. 对于形如XBX \to B \dots,则将{FIRST(B){ε}}\{FIRST(B) - \{\varepsilon\}\}添加进FIRST(X)FIRST(X)

FOLLOWFOLLOW集合求法

  1. 对于文法的开始符号SS,将#放于FOLLOW(S)FOLLOW(S)
  2. 对于形如AαBβA \to \alpha B \beta的产生式
    1. {FIRST(β){ε}}\{FIRST(\beta) - \{\varepsilon \}\}放于FOLLOW(β)FOLLOW(\beta)
    2. 如果εϵFIRST(β)\varepsilon \epsilon FIRST(\beta),则把FOLLOW(A)FOLLOW(A)放入FOLLOW(B)FOLLOW(B)
  3. 对于形如AαBA \to \alpha B的产生式,把FOLLOW(A)FOLLOW(A)放入FOLLOW(B)FOLLOW(B)

即,如下图所示
FIRST集合和FOLLOW集合求法