資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究什麼是推導？
推導是指用產生式規則的右側替換給定字串的非終結符。從開始符號生成完整終結符字串的規則應用序列稱為推導。
它可以從開始符號開始推匯出終結符字串，透過重複地用某個產生式替換變數。CFG 的語言是我們能夠推匯出的終結符集合。這種語言稱為上下文無關語言。
推導用 ⇒ 表示。
例如，考慮一個語法。
G=({S},{a,b},P,S)，其中，P 包含以下產生式 -
P={S→aSa |bSb | ∈}
在上面，S 可以被替換為 aSa 或 bSb 或 ∈。
推導型別
推導有兩種型別，如下所示 -
- 最左推導
如果我們在每一步都只對最左邊的變數使用產生式，則推導 A⇒*w 被稱為最左推導。這裡，* 表示 0、1、2、……n 個推導。
- 最右推導
如果我們在每一步都只對最右邊的變數使用產生式，則推導 A⇒*w 是最右推導。它也稱為**規範推導**。
**示例 1** - 令 G 為一個具有產生式的 CFG。
S → AA A → αB B → b B → ε
找到 (1) 最左
- 字串**abab**的最右推導。
解決方案
- 最左推導 -
S ⇒lm A $\underline{A}$
⇒lm a $\underline{B}$ A
⇒lm a b $\underline{A}$
⇒lm a b a $\underline{B}$
⇒lm a b a b
- 最右推導
S ⇒rm A $\underline{A}$
⇒rm A a $\underline{B}$
⇒rm $\underline{A}$ a b
⇒rm a $\underline{B}$ a b
⇒rm a b a b
**示例 2** - 為迴文語言編寫上下文無關語法。
L={w c wR| w ∈ {a,b}*} 具有中間符號 c。這裡 R 表示字串的反轉。
解決方案
語言表示一個具有中間符號“c”的迴文。
∴ **語法 G**=(V,∑,P,S) 將具有產生式。
S → a S a S → b S b S → c
例如，要生成迴文 a b c b a，推導為
S ⇒ a $\underline{S}$ a
⇒ a b $\underline{S}$ b a
⇒ a b c b a
**示例 3** - 為生成二進位制數字迴文的語言編寫 CFG。
解決方案
S → 0 S 0 | 1 S 1 S → 0 | 1 | ε
例如，要生成字串 0 1 1 0，推導為
S ⇒ 0 S 0 ⇒ 0 1 S 1 0 ⇒ 0 1 ε 1 0 ⇒ 0 1 1 0
**示例 4** - 考慮下面給出的語法 -
E → E+E|E * E|id
查詢
- 最左
- 字串的最右推導。
解決方案
- 最左推導
E ⇒ $\underline{E}$+E
⇒ $\underline{E}$+E+E
⇒ id+E+E
⇒ id+id+E
⇒ id+id+id
- 最右推導
E ⇒ E+$\underline{E}$
⇒ E+E+$\underline{E}$
⇒ E+E+id
⇒ E+id+id
⇒ id+id+id
3K+ 次檢視
