Common Operation
===
---

###### tags: `Compiler`
本篇記載了在
- [SLR Parser](/4_i5WNEZRWuYKDuFI3a5fQ)
- [LR(1)](/sECVHL1FTuOuqN_GjSdX1w)

共同會使用到的一些 Operation

---

# First
1. Description
:::info
The set of terminals that begins the strings derived from α
:::
2. Pseudo Code

If X is a terminal
    FIRST(X) = {X}
If X → є is a production
    add є to FIRST(X)
If X → Y1 Y2 … Yk is a production
    if ∃i (1 ≤ i ≤ k) ∋ a ∈ FIRST(Yi) and 
       є ∈ FIRST(Yj) ∀j (1 ≤ i ≤ j)
        // 若從 Y1 ~ Yj 每個 Yi 的 FIRST 都有空字串є
        // 則將每個 Yi 的 FIRST 都加進 FIRST(X)
        Place a in FIRST(X)
    if ∀i (1 ≤ i ≤ k) є ∈ FIRST(Yi)
        Place є in FIRST(X)
        // 若 Y1 ~ Yk 的 FIRST 全都有є
        // 則還需要再加 є 進 FIRST(X)

# Follow
1. Description
:::info
The set of terminals a that can appear immediately to the right of A in some sentential form
a ∈ FOLLOW(A) if there exists a derivation S ⇒ αAaβ
:::

2. Pseudo Code

Place $ in FOLLOW(S)
If there is production A → αBβ
    add FIRST(β) − {є} to FOLLOW(B)
If there is production A → αB
    add FOLLOW(A) to FOLLOW(B)
If there is production A → αBβ and є ∈ FIRST(β)
    add FOLLOW(A) to FOLLOW(B)

3. Example

E → TE’
E’ → +TE’ | є
T → FT’
T’ → *FT’ | є
F → (E ) | id

FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
FIRST(E’) = {+, є}
FIRST(T’) = {*, є}
FOLLOW(E) = FOLLOW(E’) = {), $}
FOLLOW(T) = FOLLOW(T’) = {+, ), $}
FOLLOW(F) = = {+, *, ), $}