LALR Parser
===
---

###### tags: `Compiler`

---

# Operation

部分 Operation 在
- [Common Operation](/3twRpw6BRemQVPCxrjmBGA)

## Closure
1. Description
:::info
整體與 SLR Closure(I) 的差別
在於 Item 結構多了一個 Lookahead symbol
在判斷式中 需將 FIRST(βa) 當作此 Item 的 Lookahead symbol
:::

2. Pseudo Code

function closure (I)
    J = I
    repeat
        for each item [A → α·Bβ, a] ∈ J &&
        each terminal b ∈ FIRST(βa) and
        each B → γ in G' ∋ [B → ·γ, b] ∉ J do
            add [B → ·γ, b] to J
    until no more items can be added to J
    return J
end

- FIRST(βa) 意思為
FIRST(βa) = FIRST(a) : 若 β 是空字串
FIRST(βa) = FIRST(β) : 若 β 不是空字串

3. Example

G' = {
    S' → S
    S → CC
    C → cC
    C → d
}

closure({[S' → ·S, $]}) = {
    [S' → ·S, $],
    [S → ·CC, $],
    [C → ·cC, c],
    [C → ·cC, d],
    [C → ·d, c],
    [C → ·d, d],
}

## Goto
1. Description
:::info
基本上與 SLR Goto 沒差
:::
2. Pseudo Code

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

3. Example

G' = {
    S' → S
    S → CC
    C → cC
    C → d
}

I0 = {
    [S' → ·S, $],
    [S → ·CC, $],
    [C → ·cC, c],
    [C → ·cC, d],
    [C → ·d, c],
    [C → ·d, d],
}

goto(I0, S) = closure({[S' → S·, $]}) = {
    [S' → S·, $]
}

## Items
1. Pseudo Code

procedure items (G')
    C = {closure({[S' → ·S, $]})}
    repeat
        for each set of item 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 sets of items can be added to C
end

2. Example

Example G' = 
S' → S
S → CC
C → cC
C → d
Start Symbol of G' = S'

I0 = closure({[S' → ·S, $]}) = {
    [S' → ·S, $],
    [S → ·CC, $],
    [C → ·cC, c],
    [C → ·cC, d],
    [C → ·d, c],
    [C → ·d, d]
}

I1 = goto(I0, S) = closure({[S' → S·, $]}) = {
    [S' → S·, $]
}
I2 = goto(I0, C) = closure({[S → C·C, $]}) = {
    [S → C·C, $],
    [C → ·cC, $],
    [C → ·d, $]
}
I3 = goto(I0, c) = closure({[C → c·C, c], [C → c·C, d]}) = {
    [C → c·C, c],
    [C → c·C, d],
    [C → ·cC, c],
    [C → ·cC, d],
    [C → ·d, c],
    [C → ·d, d]
}
I4 = goto(I0, d) = closure({[C → d·, c], [C → d·, d]}) = {
    [C → d·, c],
    [C → d·, d]
}

I5 = goto(I2, C) = closure({[S → CC·, $]}) = {
    [S → CC·, $]
}
I6 = goto(I2, c) = closure({[C → c·C, $]}) = {
    [C → c·C, $],
    [C → ·cC, $],
    [C → ·d, $]
}
I7 = goto(I2, d) = closure({[C → d·, $]}) = {
    [C → d·, $]
}

I8 = goto(I3, C) = closure({[C → cC·, c], [C → cC·, d]}) = {
    [C → cC·, c],
    [C → cC·, d]
}
goto(I3, c) = closure({[C → c·C, c], [C → c·C, d]}) = I3
goto(I3, d) = closure({[C → d·, c], [C → d·, d]}) = I4

I9 = goto(I6, C) = closure({[C → cC·, $]}) = {
    [C → cC·, $]
}
goto(I6, c) = closure({[C → c·C, $],}) = I6
goto(I6, d) = closure({[C → d·, $]}) = I7

# LR Parsing Table
建立 LR Parsing Table~~
與 SLR Parsing Table 不同的是
使用的是 LR(1) Item
1. Pseudo Code

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

# LALR Parsing Table
建立 LALR Parsing Table~~
與 LR Parsing Table 比較
多了狀態合併的部分
1. Pseudo Code

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

## Merge_State():
將每個 Item 中
[A → core, b]
core 相同的合併