---
title: Adv Compilers(10/20)W6#6 - Bottom-Up Parsing
tags: 111-1, AdvCompiler
---

[TOC]

<style>
.blue {
color: blue;
}
.red {
color: red;
}
.green {
color: green;
}
.purple {
color: purple;
}
</style>

###### 2022/10/20
# Botton Parsing
- <span class="red">LR(k) is more powerful than LL(k)</span>.
⬢ **Postpone the decision** until it has seen input tokens corresponding to the entire righthand side of the production.
- An <span class="red">LR parser</span> has a **stack**, an input, of which **k tokens** are look-ahead, and **2 kinds of actions.**
⬢ **Shift**: push(token), get next token.
⬢ **Reduce**: pop RHS out of stack, push(LHS)
從右邊 pop 出，左邊 push 入(like stck)。

## LR Parsing
<span class="red">**＜寫碩士論文時，用簡單的圖示(model)，並用此model實際製作並執行出來＞**</span>
- According to an LR parsing table, a LR parsing engine performs **4 kinds of action**.
1. <span class="blue">**s**</span>*n*: <span class="blue">shift</span> into *state n*
＜n 代表狀態號碼＞
2. <span class="blue">**g**</span>*n*: <span class="blue">goto</span> *state n*
＜n 代表狀態號碼＞
3. <span class="blue">**r**</span>*k*: <span class="blue">reduce</span> by *rule k*
＜跟狀態無關，和 stack 的 n 做區別。＞
4. <span class="blue">**a**</span>: <span class="blue">**accept**</span>
＜確定input 符合文法時，才進入 accept 狀態＞
- : error
### Example:
#### Rule
#### Parsing Table

## LR(0) Parsing
- Too weak to be useful
- 只看**堆疊(top of the stack)** 就可以做決定。
###### Can be parsed looking only at the stack
### Example
#### Rule
- rule 0 為 LR parsing 時另外加入的 rule，用 dollar sign($) 表示結束。

#### LR(0) Transition Diagram
- 如何做出 parsing table __ By Transition Diagram
- (1) 用 . 表示當前位置
- (2) 在 . 的左方表示已經塞入堆疊(stack)，等同於已經走到哪了
- (3) . 的右手邊：
- 遇到不同的 nonterminal 時，要在此 state 繼續展開遇到的 nonterminal，而根據該 nonterminal 使用到的 rule 產生一個路徑(一條線path)。
- 遇到不同的 terminal 時，則每個 terminal 展開的 rule 就代表一條路徑(一個線path)。


#### Parsing Table
- 用上方 Transition Diagram 的方法產生的 parse table。

## SLR(1) Parsing
- 改進 LR(0) 一遇到 reduce 就直接 reduce 的規則，以增加其適用於其他 parsing 之能力。(improvement)

## Conflicts
### Shift-reduce conflict
- Violation of the first rule
- Usually use shift over reduce

通常可接受用此方法解決，讓非 SLR(1) 的文法用 SLR(1)處理。
### Reduce-reduce conflict
- Violation of the second rule
- Usually absolutely forbidden
- SLR 是完全不允許此 conflict 存在
### why no Shift-shift conflict?
- 除非自己畫錯，把 shift 移動時產生路徑的 state 搞錯。

## Solusion to conflictions
- By Fisrt and Follow Sets

### First Set
- First(A) 的定義：
- 按照文法規則做 reduce ，照常理都會變成 token string
- 最長會根據 nonterminal 做他的 first。
### Follow Set
- Follow(A) 的定義：

## LR(1) Parsing
- Canonical(典型的) LR(1)
- Use the Follow set to decide if a reduction should be performed.
(比LR(0)多這件事而已)
- **Powerful enough** to parse almost all commonly occurring language constructs.
### Example

## LALR(1) Parsing
- powerful : <LR(1), >SLR(1)
（比SLR(1)能力強一些，仍較LR(1)弱）
- **most popularly used** parsing algorithm.
大部分 parsing 的方法都適用此演算法解決之。
- Merge the states in LR(1) that are identical except for look-ahead sets.

## Hierarchy of Grammar Classes
- LL(1) 包含 LL(0)
- LR(0) 包含 LL(1)
- 0變1包含可處理的東西變多
- 這三個(LL(1)&LL(0)&LR(0))都被 SLR 包含。

## QUIZ
只有數字就按照第 k個規則 做 ruduce
有框框就 shift 和 goto

Q: input 只有兩個 c和$