資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究語法樹和解析樹有什麼區別？
解析樹
解析樹是一種分層結構，它定義了語法推導產生輸入字串的過程。在解析過程中，字串是使用開始符號推匯出來的。解析樹的根節點就是該開始符號。它是符號的圖形描述，這些符號可以是終結符或非終結符。解析樹遵循運算子的優先順序。最深的子樹首先被遍歷。因此，父節點中的運算子優先順序低於子樹中的運算子。
對於一個上下文無關文法 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 中的一個產生式。
語法樹
語法樹是一棵樹，它顯示程式的語法結構，同時忽略解析樹中存在的無關分析。因此，語法樹只不過是解析樹的簡化形式。解析樹中的運算子和關鍵位元組點被移到其父節點，並且一組單獨的產生式被單個連結替換。例如，對於給定字串 id + id * id 的解析樹。
該表示式的語法樹如下：
示例 - 構造
解析樹
語法樹
使用您知道的任何語法為輸入字串 1 * 2 + 3 註釋完整的解析樹。
解決方案
讓我們看看解析樹和語法樹之間的比較。
| 解析樹 | 語法樹 |
|---|---|
| 它可以在樹的任何節點（即內部節點或葉子節點）包含運算子和運算元。 | 它在葉子節點包含運算元，在樹的內部節點包含運算子。 |
| 它包含重複或冗餘資訊。 | 它不包含任何冗餘資料。 |
| 透過消除冗餘（即透過壓縮）可以將解析樹更改為語法樹。 | 語法樹不能更改為解析樹。 |
| 示例 - 1 *2 + 3。 | 示例 - 1 *2 + 3。 |
更新於： 2021年11月5日
23K+ 瀏覽量
廣告