資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究什麼是 FIRST 和 FOLLOW 以及如何計算它們？
FIRST 和 FOLLOW 是與語法相關的兩個函式，它們幫助我們填充 M 表的條目。
FIRST ()− 它是一個函式，給出從產生式規則匯出的字串開頭的終結符集。
當且僅當 α ⇒ cβ 對某些語法符號序列 β 成立時，符號 c 位於 FIRST (α) 中。
當且僅當存在從語法的開始符號 S 的推導，使得 S ⇒ αNαβ，其中 α 和 β 是語法符號的（可能為空的）序列時，終結符 a 位於 FOLLOW (N) 中。換句話說，如果在推導的某個時刻 c 可以跟隨 N，則終結符 c 位於 FOLLOW (N) 中。
FIRST ( ) 和 FOLLOW ( ) 的好處
它可用於證明語法的 LL (K) 特性。
它可用於促進預測分析表的構建。
它為遞迴下降解析器提供選擇資訊。
FIRST 的計算
FIRST (α) 定義為從 α 匯出的字串的第一個字母的終結符集合。
FIRST (α) = {α |α →∗ αβ 對於某個字串 β }
如果 X 是語法符號，則 First (X) 將為 −
- 如果 X 是終結符，則 FIRST(X) = {X}
- 如果 X → ε，則 FIRST(X) = {ε}
- 如果 X 是非終結符 & X → a α，則 FIRST (X) = {a}
- 如果 X → Y1, Y2, Y3，則 FIRST (X) 將為
(a) 如果 Y 是終結符，則
FIRST (X) = FIRST (Y1, Y2, Y3) = {Y1}
(b) 如果 Y1 是非終結符並且
如果 Y1 不能推匯出空字串，即如果 FIRST (Y1) 不包含 ε，則 FIRST (X) = FIRST (Y1, Y2, Y3) = FIRST(Y1)
(c) 如果 FIRST (Y1) 包含 ε，則。
FIRST (X) = FIRST (Y1, Y2, Y3) = FIRST(Y1) − {ε} ∪ FIRST(Y2, Y3)
類似地，FIRST (Y2, Y3) = {Y2}，如果 Y2 是終結符，否則如果 Y2 是非終結符，則
FIRST (Y2, Y3) = FIRST (Y2)，如果 FIRST (Y2) 不包含 ε。
如果 FIRST (Y2) 包含 ε，則
FIRST (Y2, Y3) = FIRST (Y2) − {ε} ∪ FIRST (Y3)
類似地，此方法將對後續語法符號重複，即對於 Y4, Y5, Y6 … . YK。
FOLLOW 的計算
Follow (A) 定義為直接出現在 A 右側的終結符集合。
FOLLOW(A) = {a|S ⇒* αAaβ 其中 α、β 可以是任何字串}
查詢 FOLLOW 的規則
如果 S 是開始符號，則 FOLLOW (S) ={$}
如果產生式形式為 A → α B β，β ≠ ε。
(a) 如果 FIRST (β) 不包含 ε，則 FOLLOW (B) = {FIRST (β)}
或者
(b) 如果 FIRST (β) 包含 ε（即 β ⇒* ε），則
FOLLOW (B) = FIRST (β) − {ε} ∪ FOLLOW (A)
∵ 當 β 推匯出 ε 時，A 之後的終結符將跟隨 B。
- 如果產生式形式為 A → αB，則 Follow (B) ={FOLLOW (A)}。
54K+ 瀏覽量
