SLR Parser
===
---

###### tags: `Compiler`

本篇記錄 SLR Parser 詳細實作方式

---

# Intro
~~這裡比較不重要 略過ㄅ~~
- Q: What is SLR
A: Simple LR is a type of LR Parser, Accurately, LR(0) Parser

- Q: So, What is LR Parser
A: LR parsers are a type of bottom-up parser that efficiently read deterministic context-free languages

好了啦先這樣，先往下看啦

# Operation
在後面的演算法中會運用到的一些 function~
部分 Operation 在
- [Common Operation](/3twRpw6BRemQVPCxrjmBGA)

## Closure
1. Description
:::info
If I is a set of items, then closure (I) is the set of items
constructed from I:
- Initially, every item in I is added to closure (I)
- If A → α⋅B β is in closure (I) and B → γ is a production, then
- add the item B → ⋅γ to closure (I)
- Repeat until no more new items can be added
:::

2. Pseudo Code

function closure (I)
    J = I // J 是一個集合
    repeat
        for each item A → α·Bβ ∈ J && 
        each B → γ in G' ∋ B → ·γ ∉ J do
            add B → ·γ to J
    until no more items can be added to J
    return J
end

3. Example

E’ → E
E → E + T
E → T
T → T * F
T → F
F → (E)
F → id

closure({E’ → E}) = {
    E’ → ⋅ E
    E → ⋅ E + T
    E → ⋅ T
    T → ⋅ T * F
    T → ⋅ F
    F → ⋅ (E)
    F → ⋅ id
}

## Goto
1. Description
:::info
If I is a set of items and X is a grammar symbol,
then goto (I, X) is the set of items that:
- Initially, C is a empty set of item
- for every A → α⋅X β is in I
- Add A → αX ⋅β into C
- return the closure of C
:::
2. Pseudo Code

function goto(I, X)
    J = set of items [A → αX·β] ∋ [A → α·Xβ] ∈ I
    return closure(J)
end

3. Example

E’ → E
E → E + T
E → T
T → T * F
T → F
F → (E)
F → id

goto({E’ → E ⋅, E → E ⋅ + T }, +) = 
closure({E → E + ⋅ T}) = {
    E → E + ⋅ T
    T → ⋅ T * F
    T → ⋅ F
    F → ⋅ (E)
    F → ⋅ id
}

## items
Set-of-Items Construction
1. Pseudo Code

procedure items (G’)
    C = {closure {S’→ ⋅S}}
    repeat
        for each set of items I ∈ C and each grammar symbol X do
        if (goto(I, X) is not empty and ∉ C)
            add goto (I, X) to C
    until no more set of items can be added to C
    return C
end

2. Example

Example G' =
E’ → E
E → E + T
E → T
T → T * F
T → F
F → (E )
F → id
Start Symbol of G'= E'

I0 = closure({E' -> ⋅ E}) = {
    E’ → ⋅ E
    E → ⋅ E + T
    E → ⋅ T
    T → ⋅ T * F
    T → ⋅ F
    F → ⋅(E )
    F → ⋅ id
}

I1 = goto(I0, E) = closure({E’ → E ⋅, E → E ⋅ + T}) = {
    E’ → E ⋅
    E → E ⋅ + T
}
I2 = goto(I0, T) = closure({E → T ⋅, T → T ⋅ * F}) = {
    E → T ⋅
    T → T ⋅ * F
}
I3 = goto(I0, F) = closure({T → F ⋅ }) = {
    T → F ⋅ 
}
I4 = goto(I0, '(') = closure({F → ( ⋅ E)}) = {
    F → ( ⋅ E)
    E → ⋅ E + T
    E → ⋅ T
    T → ⋅ T * F
    T → ⋅ F
    F → ⋅(E )
    F → ⋅ id
}
I5 = goto(I0, id) = closure({F → id ⋅ }) = {
    F → id ⋅ 
}

I6 = goto(I1, +) = closure({E → E + ⋅ T}) = {
    E → E + ⋅ T
    T → ⋅ T * F
    T → ⋅ F
    F → ⋅(E )
    F → ⋅ id
}

I7 = goto(I2, *) = closure({T → T * ⋅ F}) = {
    T → T * ⋅ F
    F → ⋅(E )
    F → ⋅ id
}

I8 = goto(I4, E) = closure({F → (E ⋅ ), E → E ⋅ + T}) = {
    F → (E ⋅ )
    E → E ⋅ + T
}
goto(I4, T) = closure({E → T ⋅, T → T ⋅ * F}) = I2
goto(I4, F) = closure({T → F ⋅ }) = I3
goto(I4, '(') = closure({F → ( ⋅ E )}) = I4
goto(I4, id) = closure({F → id ⋅ }) = I5

I9 = goto(I6, T) = closure({E → E + T ⋅, T → T ⋅ * F}) = {
    E → E + T ⋅
    T → T ⋅ * F
}
goto(I6, F) = closure({T → F ⋅ }) = I3
goto(I6, '(') = closure({F → ( ⋅ E )}) = I4
goto(I6, id) = closure({F → id ⋅ }) = I5

I10 = goto(I7, F) = closure({T → T * F ⋅ }) = {
    T → T * F ⋅ 
}
goto(I7, '(') = closure({F → ( ⋅ E )}) = I4
goto(I7, id) = closure({F → id ⋅ }) = I5

goto(I8, ')') = closure({F → (E ) ⋅ }) = {
    F → (E ) ⋅ 
}
goto(I8, +) = closure({E → E + ⋅ T}) = I6

goto(I9, *) = closure({T → T * ⋅ F}) = I7

items(G') = {
    I0, I1, I2, I3, I4, I5, I6, I7, I8, I9, I10
}

# LR(k) Item
LR(k) Item meaning:
:::info
L: Scanning the input from left to right
R: Producing a rightmost derivation in reverse
k: The number of input symbols of lookahead
:::
# SLR Parsing Table
建立 SLR Parsing Table~~
1. Pseudo Code

// Set-of-Items Construction
// The set of LR(0) items containing S’ → ·S is the initial state
C = items(G')
State i is constructed from Ii. Actions for state i
    If A → α·aβ ∈ Ii and goto(Ii, a) = Ij
        action[i, a] = shift j
    If A → α· ∈ Ii
        action[i, a] = reduce A → α ∀a ∈ FOLLOW(A)
    If S’ → S· ∈ Ii
        action[i, $] = accept
If goto(Ii , A) = Ij
    goto[i, A] = j

2. Example

**注意 :**
- sx 是指 shift 到 "x-th **State**"
- rx 是指用 "x-th **Rule**" 做 reduce

# LR Parsing Algorithm
1. Pseudo Code

set ip to point to the first symbol of w$
repeat forever
    let s be the state on stack top
    let a be the symbol pointed by ip
    if action[s, a] = shift s’
        push a and s’ onto the stack and advance the ip
    else if action[s, a] = reduce A → β
        pop 2*|β| symbols from the stack 
        and now s’ is the top state
        push A and then goto[s’ , A] on top of the stack
        output A → β
    else if action[s, a] = accept
        return
    else
        error()
end

2. Example

# **BUT... Sometimes... It will go wrong!**
GG