資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學求解下列文法的FIRST集合和FOLLOW集合：
E → E + T|T
T → T ∗ F|F
F → (E)|id
解答
FIRST集合的計算
E → E + T|T
由於FIRST(E)不包含ε。
∴ FIRST(E) = FIRST(E + T) = FIRST(E)
因為 E → T
∴ FIRST(E) = {FIRST(T)} (1)
T → T ∗ F|F
由於FIRST(T)不包含ε，或者T不能推匯出ε。
∴ FIRST(T) = FIRST(T ∗ F) = {FIRST(T)}
因為 T → F (FIRST(T) = {FIRST(F)} (2)
F → (E)|id
∴ 根據FIRST的規則(3)
FIRST(F) = {(, id} (3)
由(1)，(2)和(3)
FIRST(F) = {(, id} (3)
FIRST(T) = {FIRST(F)} (2)
FIRST(E) = {FIRST(T)} (1)
∴ FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
FOLLOW集合的計算
E → E + T|T
T → T ∗ F|F
F → (E) |id
應用規則(1) FOLLOW(E) = {$} (1)
- E → E + T|T
應用FOLLOW的規則(2)
| E → | ε | E | + | T |
| A → | α | B | β |
α = ε, B = E, β = +T
由於FIRST(β) = FIRST(+T) = {+}不包含ε
∴ FOLLOW的規則(2a)
∴ FOLLOW(E) = FIRST(+T) = {+}
∴ FOLLOW(E) = {+} (2)
應用FOLLOW的規則(3)
| E → | E + | T |
| A → | α | B |
FOLLOW(T) = {FOLLOW(E)} (3)
- T → T * F
應用規則(2)
| T → | ε | T | *F |
| A → | α | B | β |
∴ A = T, α = ε, B = T, β = *F
由於FIRST(β) = {∗}不包含ε。
∴ FOLLOW的規則(2a)
∴ FOLLOW(T) = FIRST(* F)
∴ FOLLOW(T) = {∗} (4)
應用規則(3)
| T → | T* | F |
| A → | α | B |
FOLLOW(F) = {FOLLOW(T)} (5)
- F → (E)
應用規則(2)
| F → | ( | E | ) |
| A → | α | B | β |
由於FIRST(β) = {)}不包含ε。
∴ FOLLOW的規則(2a)
∴ FOLLOW(E) = FIRST())。
∴ FOLLOW(E) = {)} (6)
規則(3)不能應用於此產生式
它在右端有 )。
但在規則(3)中，我們應該在右端有一個非終結符。
即，我們不能將A → αB與F → (E)進行比較。
結合所有6個語句，我們得到
FOLLOW(E) = {$} (1)
FOLLOW(E) = {+} (2)
FOLLOW(T) = {FOLLOW(E)} (3)
FOLLOW(T) = {∗} (4)
FOLLOW(F) = {FOLLOW(T)} (5)
FOLLOW(E) = {)} (6)
∴ 由規則(1)，(2)和(6)
FOLLOW(E) = {$, +, )}
∴ 由規則(3)，(4)和(5)
FOLLOW(T) = FOLLOW(F) = {$, +, ),∗}
8K+ 瀏覽量
