資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學什麼是預測分析演算法，並計算以下文法的FIRST和FOLLOW集？\nS → L = R\nS → R\nL →* R\nL → id\nR → L
解答
FIRST集的計算
- S → L = R
∵ L不能匯出ε。根據FIRST規則(4b)
∴ FIRST(S) = {FIRST(L)} (1)
- S → R
∵ R不能匯出ε。根據FIRST規則(4b)
∴ FIRST(S) = {FIRST(R)} (2)
- L →* R
應用FIRST規則(3)
FIRST(L) = {*} (3)
- L → id
應用FIRST規則(3)
FIRST(L) = {id} (4)
- R → L
應用FIRST規則(4b)
FIRST(R) = {FIRST(L)} (5)
合併(1)到(5)的結果
FIRST(L) = {*, id}
FIRST(S) = {FIRST(L)}
FIRST(R) = {FIRST(L)}
FIRST(S) = {FIRST(R)}
∴ FIRST(L) = FIRST(S) = FIRST(R) = {*, id}
FOLLOW集的計算
S → L = R
S → R
L →∗ R
L → id
R → L
應用FOLLOW規則(1)
FOLLOW (S) ={$} (1)
S → L = R
應用FOLLOW規則(2)
| S → | ε | L | = R |
| A → | α | B | β |
∵ FIRST(β) = FIRST(= R) = {=}不包含ε。
∴ **FOLLOW規則(2a)**
∴ FOLLOW(L) = {=} (2)
應用FOLLOW規則(3)
| S → | L = | R |
| A → | α | B |
∴ FOLLOW(R) = {FOLLOW(S)} (3)
- S → R
由於A → 𝛼 B β與S → R不匹配，因此無法在此產生式上應用規則(2)。
應用規則(3)
| S → | ε | R |
| A → | α | B |
∴ FOLLOW(R) = {FOLLOW(S)} (4)
- L →* R
規則(2)不適用於此產生式
應用規則(3)
| L → | * | R |
| A → | α | B |
∴ FOLLOW(R) = {FOLLOW(L)} (5)
- R → L
規則(2)無法應用。
∴ 應用規則(3)
| R → | ε | l |
| A → | α | B |
∴ FOLLOW(L) = {FOLLOW(R)} (6)
合併(1)到(6)的結果
FOLLOW(S) = {$} (1)
FOLLOW(L) = {=} (2)
FOLLOW(R) = {FOLLOW(S)} (3)
FOLLOW(R) = {FOLLOW(S)} (4)
FOLLOW(R) = {FOLLOW(L)} (5)
FOLLOW(L) = {FOLLOW(R)} (6)
∴ FOLLOW(S) = {$}
FOLLOW(L) = FOLLOW(R) = {$, =}
預測分析演算法
**輸入** − 待解析的字串和文法的解析表'M'。
**輸出** − 棧將變為空，或者給出錯誤。
方法
While Stack is not empty do
{
Let X be top symbol on Stack
Let a be next input symbol
If X is Terminal or $ then
If X = a then
Pop X form stack & remove a from input
else error ( );
else
If M [X, a] = A → Y1Y2 … … . . Yn
Pop X and Push Yn Yn−1 … . . Y1 onto stack
else error ( );
}
1K+ 次瀏覽
