什麼是編譯器設計中無回溯的自頂向下分析？

有兩種無回溯的自頂向下分析方法，如下所示：

  • 遞迴下降分析器

  • 預測分析器

遞迴下降分析器

遞迴下降分析器是一種自頂向下分析器，它實現一組遞迴過程來處理輸入而無需回溯。如果用一種有效執行過程呼叫的語言編寫，則遞迴過程易於編寫且效率足夠高。

語法中的每個非終結符都有一個對應的過程。它可以考慮一個全域性變數“展望”（lookahead），它影響當前輸入標記，而過程`match(預期標記)`的作用是識別解析過程中的下一個標記並推進輸入流指標，使得“展望”指向下一個要解析的標記。`match()`實際上是對詞法分析器的呼叫，以獲取下一個標記。

預測分析器

預測分析器也稱為非遞迴預測分析。預測分析器是透過顯式地處理啟用記錄棧來實現遞迴下降分析的一種有效方法。預測分析器具有輸入、棧、分析表和輸出。輸入包括要解析的字串，後跟$（右端標記）。

棧包括一系列語法符號，前面是$（棧底標記）。最初，棧包含語法的開始符號，前面是$。分析表是一個二維陣列M[A, a]，其中‘A’是非終結符，‘a’是終結符或符號$。

分析器由執行以下操作的程式控制：程式確定棧頂符號X和當前輸入符號‘a’。這兩個符號決定了分析器的動作。

有三種可能性：

  • 如果X = a = $，則分析器終止並宣告解析成功。
  • 如果X = a ≠ $，則分析器將X從棧中彈出，並將輸入指標推進到下一個輸入符號。
  • 如果X是非終結符，則程式查閱分析表M中的M[X, a]項。此項將是語法的X-產生式或錯誤項。如果M[X, a] = [X→ UVW]，則分析器將棧頂的X替換為UVW（U位於頂部）。作為輸出，語法執行與此產生式相關的語義動作，目前可以假設它只是列印所使用的產生式。如果M[X, a] = error，則分析器呼叫錯誤恢復例程。

更新於：2021年10月30日

1K+ 次瀏覽

啟動你的職業生涯

完成課程獲得認證

開始學習
廣告