自上而下分析法.md

title	date	tags
自上而下分析法	2020-07-28 06:05:29 -0700

消除回溯

FIRST set(终结首符集)

​ **FIRST(α)={α|α=*>a..., a∈Vt} **

若α=*>ε ， 则规定ε∈FIRST(α)。

• FIRST集的构造方法

  If x is a terminal, then FIRST(x) = { ‘x’ }

  If x-> Є, is a production rule, then add Є to FIRST(x).

  If X->Y1 Y2 Y3….Yn is a production,

  1. FIRST(X) = FIRST(Y1)

  2. If FIRST(Y1) contains Є then FIRST(X) = { FIRST(Y1) – Є } U { FIRST(Y2) }

  3. If FIRST (Yi) contains Є for all i = 1 to n, then add Є to FIRST(X).

FOLLOW

FOLLOW（A）={a|S=*>...Aa..., a∈VT}

特别是，若S=*>...A, 规定#∈FOLLOW(A)

• FOLLOW 集的构造方法

FOLLOW(S) = { $ } // where S is the starting Non-Terminal

If A -> pBq is a production, where p, B and q are any grammar symbols,
   then everything in FIRST(q)  except Є is in FOLLOW(B).

If A->pB is a production, then everything in FOLLOW(A) is in FOLLOW(B).

If A->pBq is a production and FIRST(q) contains Є, 
   then FOLLOW(B) contains { FIRST(q) – Є } U FOLLOW(A) 

---

LL1

构造不带回溯的自上而下分析的条件：

​ **1.文法不含左递归 **

​ 2.若A->a1|a2|a3|...|an , 则FIRST(ai)∩FIRST(aj)=空 (i!=j)

​

​