資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學什麼是語法樹（推導樹）？
推導是指用產生式右邊的式子替換給定字串的非終結符。從開始符號生成完整的終結符字串的規則應用序列稱為推導。語法樹是推導的圖形表示。因此，它也稱為推導樹。推導樹獨立於產生式使用的順序。
語法樹是一個有序樹，其中節點用產生式的左邊標記，節點的子節點定義其等效的右邊。語法樹也稱為語法樹、生成樹或產生式樹。
對於 CFG G =(V,∑, P,S)，語法樹是一個滿足以下條件的樹：
根節點的標籤為 S，其中 S 是開始符號。
語法樹的每個頂點都有一個標籤，可以是變數 (V)、終結符 (Σ) 或 ε。
如果 A → C1,C2…….Cn 是一個產生式，那麼 C1,C2…….Cn 是標記為 A 的節點的子節點。
葉子節點是終結符 (Σ)，內部節點是變數 (V)。
內部頂點的標籤始終是變數。
如果頂點 A 有 k 個子節點，其標籤為 A1,A2…….Ak，則 A →
A1,A2…….Ak 將是上下文無關文法 G 中的產生式。
產出 (Yield) − 推導樹的產出是從左到右對葉子節點標籤的串聯。
示例 1 − 如果 CFG 有產生式。
S → a A S | a S → Sb A | SS | ba
證明 S ⇒ *aa bb aa 並構造產出為 aa bb aa 的語法樹。
解答
S ⇒lm lm a $\underline{A}$ S
⇒ a $\underline{S\:b}$ A S
⇒ aa b $\underline{A}$ S
⇒ aa bba $\underline{S}$
∴ S ⇒ * aa bb aa
推導樹
產出 = 葉子節點從左到右的順序 = aa bb aa
示例 2
考慮 CFG
S → bB | aA A → b | bS | aAA B → a |aS | bBB
找到 (a) 最左
字串 b aa baba 的最右推導。也找到推導樹。
解答
- 最左推導
S⇒b $\underline{B}$
⇒ bb $\underline{B}$B
⇒ bba$\underline{B}$
⇒ bbaa$\underline{S}$
⇒ bb aa$\underline{bB}$
⇒ bb aa b $\underline{aS}$
⇒ bb aa bab $\underline{B}$
⇒ bb aa ba ba
- 最右推導
S ⇒ b$\underline{B}$
⇒ bb B$\underline{B}$
⇒ bbBa$\underline{S}$
⇒ bbBab$\underline{B}$
⇒ bbBaba$\underline{S}$
⇒ bbBabab$\underline{B}$
⇒ bb$\underline{B}$abab a
⇒ bbaababa
示例 3 − 考慮以下給出的語法：
E⇒ E+E|E $\ast$ 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
13K+ 瀏覽量
