回溯法和非回溯法有什麼區別？

帶回溯的自頂向下分析

在帶回溯的自頂向下分析中，解析器將嘗試多種規則或產生式，透過在推導的每一步回溯來發現與輸入字串的匹配。因此，如果使用的產生式沒有給出所需的輸入字串，或者它與所需的字串不匹配，則可以撤消該移位。

不帶回溯的自頂向下分析

由於回溯看起來更強大，我們可以選擇不同的備選方案。但是回溯在解析中不能輕易應用或實現。不帶回溯的自頂向下分析有兩種型別，如下所示：

遞迴下降分析器

實現一組遞迴過程來處理輸入而不回溯的自頂向下分析器稱為遞迴下降分析器，而解析稱為遞迴下降解析。如果用一種有效執行過程呼叫的語言編寫，則遞迴過程可以簡單地編寫並且足夠有效。

語法中每個非終結符都有一個過程。它可以考慮一個全域性變數前瞻，儲存當前的輸入標記，並且一個過程匹配（預期標記）是識別解析過程中下一個標記並推進輸入流指標的動作，使得前瞻指向要解析的下一個標記。Match() 有效地呼叫詞法分析器來獲取下一個標記。

預測分析器

預測分析器也稱為非遞迴預測分析。預測分析器是一種執行遞迴下降分析的有效方法，它顯式地處理啟用記錄的堆疊。預測分析器具有輸入、堆疊、分析表和輸出。輸入包括要解析的字串，後跟 $，即右端標記。

堆疊包含一系列語法符號，前面是 $，即堆疊底部標記。最初，堆疊包含語法開始符號，前面是 $。分析表是一個二維陣列 M[A, a]，其中 'A' 是一個非終結符，'a' 是一個終結符或符號 $。

讓我們看看帶回溯的自頂向下分析和不帶回溯的自頂向下分析之間的比較

帶回溯的自頂向下分析	不帶回溯的自頂向下分析
解析器可以按任意順序嘗試所有備選方案，直到成功解析字串。	解析器必須在每一步選擇正確的備選方案。
回溯需要大量時間，即指數時間來執行解析。	它花費更少的時間。
語法可以有左遞迴。	在進行解析之前將刪除左遞迴。
撤消操作時會有很多開銷。	它可以執行更少的開銷。
在回溯時，一旦插入的資訊將從符號表中刪除。	資訊不會被刪除。
可能難以找到實際發生錯誤的位置。	可以很容易地找到錯誤的位置。

Ginni

更新時間： 2021-11-01

2K+ 瀏覽量

完成課程獲得認證