資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究什麼是編譯器設計中的自頂向下回溯分析？
在自頂向下回溯分析中，分析器將嘗試使用多個規則或產生式來識別輸入字串的匹配項，並在推導的每一步都進行回溯。因此，如果應用的產生式沒有得到所需的輸入字串，或者與所需的字串不匹配，則可以撤消該移位。
示例 1 - 考慮以下語法
S → a A d
A → b c | b
為字串 a bd 建立語法樹。此外，當選擇錯誤的備選方案時，顯示需要回溯時的語法樹。
解決方案
字串 abd 的推導將是 -
S ⇒ a A d ⇒ abd（所需字串）
如果將bc替換為非終結符 A，則獲得的字串將是 abcd。
S ⇒ a A d ⇒ abcd（錯誤的備選方案）
圖 (a) 表示 S → aAd
圖 (b) 表示使用產生式 A → bc 擴充套件樹，該產生式生成字串 abcd，該字串與字串 abd 不匹配。因此，它回溯並選擇另一個備選方案，即圖 (c) 中的 A → b，該方案與 abd 匹配。
回溯演算法
示例 2 - 為以下語法的自頂向下回溯分析編寫演算法。
S → a A d
A → bc| b
解決方案
在以下演算法中，每個非終結符 S 和 A 都有一個過程。語法中的終結符 a、b、c、d 是分析器要讀取的輸入符號或前瞻符號。
advance( ) - 它是一個用於將輸入指標移動到下一個輸入符號的函式。
自頂向下回溯分析的侷限性
以下是自頂向下回溯分析中出現的一些問題。
回溯 - 回溯看起來非常簡單易於實現，但選擇不同的備選方案會導致很多問題，如下所示 -
撤消語義操作需要大量開銷。
在分析期間在符號表中建立的條目必須在回溯時刪除。
由於這些原因，回溯不用於實際編譯器。
左遞迴 - 如果語法具有以下形式的產生式，則該語法是左遞迴的。
A → Aα|β
這會導致分析器進入無限迴圈。
選擇正確的產生式 - 測試備選方案的順序可以改變接受的語言。
難以定位錯誤 - 發生故障時，很難知道錯誤發生在哪裡。
8K+ 次瀏覽
