# Final
###### tags: `compiler` `note` `thu`
### 1.
#### `105` `106` `107`
Please draw a diagram to show the difference capacity among LL(1), LR(0), SLR(1), LR(1), and LALR(1).
#### ANS:
| Parsing Technique | Lookahead | Grammar Handling | Parsing Table Size | Computational Complexity |
|-------------------|-----------|-----------------|--------------------|--------------------------|
| LL(1) | 1 | Limited | Small | Low |
| LR(0) | 0 | Moderate | Moderate | Moderate |
| SLR(1) | 1 | Improved | Moderate | Moderate |
| LR(1) | 1 | Enhanced | Large | High |
| LALR(1) | 1 | Balanced | Small to Moderate | Moderate |
---
### 2.
#### `105` `106` `107` `108`
Please identify the following parsers, which parser are belonging to Top-down approach, and which are Bottom-up approach?
```
a. Operator Precedence
b. Recursive Descent
c. LR(0)
d. LR(1)
e. LL(1)
f. Shift-Reduce
g. SLR or SLR(1)
h. LALR(1)
```
#### ANS:
Top-down: b, e
Bottom-up: a, c, d, f, g, h
---
### 3.
#### `105` `106` `107` `108`
Give a grammar in the following, please use closure($I_0$) and each item sets to show **whether the grammar is LR(0) or SLR(1)**. If the grammar is SLR(1), Please construct the DFA and Shift-Reduce table and GOTO table, respectively. **Please construct a LL(1) table also**.
**(Hint: You should add an augment production and then find the first and follow symbols of grammar for SLR(1) and LR(1))**
```
1. E → E + T
2. E → T
3. T → T × F
4. T → F
5. F → ( E )
6. F → id
```
### 4.
#### `105` `106` `107` `108`
***(a)*** Please list the quadruple code for the following statement, you can use $T_i$ as temporary register, VARIANCE := SUMSQ/100 – MEAN*MEAN.
***(b)*** 假設所產生的組合語言如下，請問最佳化後的碼是會如何安排？
```
LDA SUMSQ
DIV #100
STA T1
LDA MEAN
MUL MEAN
STA T2
LDA T1
SUB T2
STA T3
LDA T3
STA VARIANCE
```
#### ANS:
```
(a)
(MUL, MEAN, MEAN, T1)
(DIV, SUMSQ, 100, T2)
(SUB, T2, T1, T3)
(ASSIGN, T3, VARIANCE)
(b)
LDA MEAN
MUL MEAN
STA T1
LDA SUMSQ
DIV #100
SUB T1
STA VARIANCE
```
---
### 5.
#### `105` `106` `107` `108` `109`
Please write the cost for each statement, if Define the cost of instruction= 1 + cost(*source*-mode) + cost(*destination*-mode)
| Mode | Form | Address | Added Cost |
| --- | -------- | -------- | -------- |
| Absolute (Direct) | $M$ | $M$| 1|
| Register | $R$ | $R$ | 0 |
| Indexed | $c(R)$ | $c^+contents(R)$| 1 |
| Indirect register | $*R$| $contents(contents(R))$ | 1 |
| Indirect indexed|$*cR$ |$contents(c^+contents(R))$| 2 |
| Literal (Imm) | #c | $N/A$ | 0 |
***以下是109年特殊選擇題:***
***$(a)$*** How many the cost for MOV R0, M
A. 1
B. 2
C. 3
D. 4
#### ANS: B
***$(b)$*** 承上題，How many the cost for MOV *4(R0), M
A. 1
B. 2
C. 3
D. 4
#### ANS: D
***$(c)$*** 承上題，How many the cost for ADD 4(R0), *8(R1)
A. 1
B. 2
C. 3
D. 4
#### ANS: D
### 6.
#### `105` `106` `107` `108`
**What are access link and control link for an activation record?** Please use the following example codes to draw **activation records** including block number, local variables, the access links, and control links, when executing sequences are **sort calls q, q calls q again, q calls p, p calls e**.
```
Program sort
var a: array[0..10] of int;
x: int;
procedure r
var i: int;
begin ... r
end
procedure e(i, j)
begin ... e
a[i] <-> a[j]
end
procedure q
var k,v: int;
procedure p
var i, j;
begin ... p
call e
end
begin ... q
call q or p
end
begin ... sort
call q
end
```
#### ANS:
### 7.
#### `106` `107`
When instructions are independent, their evaluation order can be changed, if the following statement
`a+b-(c+d)*e `
and will has the immediate codes are listed as below
```
t1:=a+b
t2:=c+d
t3:=e*t2
t4:=t1-t3
```
and the assembly codes are listed as below
```
MOV a,R0
ADD b,R0
MOV R0,t1
MOV c,R1
ADD d,R1
MOV e,R0
MUL R0,R1
MOV t1,R1
SUB R0,R1
MOV R1,t4
```
Please reorder the codes and get the new assembly code for code optimization.
#### ANS:
```
MOV a,R0
MOV c,R1
ADD b,R0
ADD d,R1
MUL e,R1
SUB R1,R0
MOV R0,t4
```
---
### 8.
#### `108`
Please describe the contents of an **Activation Record, what are access link and control link**?
#### ANS:
* Activation Record 包含:
1. Return address
1. Control Link
1. Access Link
1. Local Variables
1. Parameters
1. Temporary Variables
1. Return Value
* Access Link
存取連結（Access Link）是一個指向上一層活動記錄的指標，用於訪問外部或上層的變數和資源。
* Control Link
控制連結（Control Link）是一個指向呼叫者的活動記錄的指標，用於控制執行流程的轉移。
---
### 9.
#### `109`
下列敘述何者為對
A. LL(1), LR(1), SLR 皆是 Bottom-up parsing
B. LL(1), LALR, Operator-precedence 皆是 Top-down parsing
C. Shift-reduce, LR(0), SLR, LALR 皆是 Bottom-up parsing
D. Recursive-descent, Predictive, Operator-precedence 皆是 Top-down parsing
#### ANS: C
---
### 10.
#### `109`
下列哪一項不屬於 Activation Record 的內容
A. Optional Access Link
B. Optional Control Link
C. Return value
D. Global Data
#### ANS:D
---
### 11.
#### `109`
當有主程式呼叫副程式時，於 Activation Record 中哪兩項的內容，是被呼叫的副程式要負責填入？
A. Return address, Optional Control link
B. Optional Control link, Optional Access link
C. Optional Access link, Local data
D. Local data, Temporaries
#### ANS: D
---
### 12.
#### `109`
下列哪一種 Parsing 方法的能力最強大？
A. LL(1)
B. LALR
C. LR(1)
D. SLR
#### ANS: C
---
### 13.
#### `109`
請問下列文法可以用何種 Parsing 來處理？
```
1. S -> L = R
2. S -> R
3. L -> * R
4. L -> id
5. R -> L
```
A. LR(1)
B. SLR
C. LR(0)
D. LL(1)
#### ANS: A
---
### 14.
#### `109`
請問下列敘述何者正確？
A. 建置 SLR 時，不需要找出 First and Follow sets
B. 有些文法會造成 LR(1)與 LALR(1)有相同的能力
C. 建置 SLR 時，要先提出左因子
D. 建置 LR(0)時，要先消去左遞迴
#### ANS: B
---
### 15.
#### `109`
請問下列敘述何者不正確？
A. Shift-Reduce parsing 的動作是 Shift, Reduce, Accept, 與 Error
B. 使用 SLR parsing 時，會用到 Stack and Queue, 但不需要用到 Symbol Table.
C. 建置 SLR parsing table 時，要列出所有的 terminal symbols and non-terminal symbols
D. 建置 LR(1) parsing table 時，Table 的狀態數會比 SLR 多
#### ANS: B
---
### 16.
#### `109`
下列哪一項階段並非編譯器的前端部分
A. Lexical analysis
B. Syntax analysis
C. Sematic analysis
D. Code generation
#### ANS: D
---
### 17.
#### `109`
下列哪一項並非編譯器的中間碼使用形式
A. Abstract Syntax Tree (AST)
B. Prefix notation
C. Two address code
D. Three address code
#### ANS: B
---
### 18.
#### `109`
請問 Lex 工具是可以處理何種副檔名的檔案
A. *.c
B. *.y
C. *.l
D. *.py
#### ANS: C
---
### 19.
#### `109`
請問 Yacc 工具是可以處理何種副檔名的檔案
A. *.c
B. *.y
C. *.h
D. *.l
#### ANS: B
---
### 20.
#### `109`
請問 LLVM+Clang 在我們期末專案主要是為
A. 產生目的碼與碼的最佳化
B. 字彙分析
C. 文法分析
D. 語意分析
#### ANS: A
---
### 21.
#### `109`
請問 Cross Compiler 作業中，何者為非？
A. 了解 Tool-chain 運作過程
B. 使用 Binutils
C. 使用 Newlib
D. 只能產生 x86 組合語言
#### ANS: D
---
### 22.
#### `109`
語意分析中，我們會採用何種排序法來確認宣告？
A. Quick Sort
B. Heap Sort
C. Topological Sort
D. Merge Sort
#### ANS: C
---
### 23.
#### `109`
如果建置 SLR Table 後，發現到有 Shift-reduce conflict 現象，我們再來要如何處理？
A. 提出左因子
B. 消去左遞迴
C. 改用 LR(1)
D. 改用 LALR
#### ANS: D
---
### 24.
#### `109`
建置 LR(0), SLR, LR(1), LALR 的狀態過程中，哪一種方法的表格的狀態數會比較多？
A. LR(0)
B. SLR
C. LR(1)
D. LALR
#### ANS: C
---
### 25.
#### `109`
目的碼的最佳化的進行，何者為非？
A. 儘量用暫存器運算指令
B. 儘量用記憶體運算指令
C. 交換指令執行順序，但不改變運算邏輯
D. 以位移指令取代乘法
#### ANS: B
## 施工中
* 3
Sign in with Wallet
Connect another wallet