什麼是自頂向下分析？

在自頂向下分析中，語法樹是從上到下生成的，即從根到葉，並展開直到生成所有葉節點。

它生成以語法起始符為根的語法樹。它從語法的起始符開始推導，並在每一步執行最左推導。

自頂向下分析的缺點

• 自頂向下分析試圖為輸入字串ω識別最左推導，這類似於為從根開始的輸入字串ω生成語法樹，並按預定義順序生成節點。

• 自頂向下分析遵循輸入字串ω的最左推導而不是最右推導的原因是，解析器從左到右逐個符號/標記掃描輸入字串ω。最左推導按從左到右的順序生成語法樹的葉節點，這與輸入掃描順序相連線。

• 在自頂向下分析中，由語法的多個產生式（已預測）生成的每個終結符都與字串標記指向的輸入字串符號連線。如果匹配成功，解析器可以繼續。如果發生不匹配，則預測是錯誤的。

• 在此階段，必須拒絕之前的預測。導致終結符不匹配的預測被拒絕，並且字串標記（指標）重置到做出拒絕產生式時的先前位置。這稱為回溯。

• 回溯是自頂向下分析的主要缺點。

自頂向下分析的型別

自頂向下分析有兩種型別，如下所示：

• 帶回溯的自頂向下分析

在回溯中，解析器可以對輸入進行重複掃描。如果透過應用一個產生式規則無法獲得所需的輸入字串，則可以在每一步應用另一個產生式規則以獲得所需的字串。

• 不帶回溯的自頂向下分析

一旦應用了產生式規則，就不能撤消。

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

**遞迴下降分析器** - 一種實現一組遞迴過程以在不回溯的情況下處理輸入的自頂向下分析器稱為遞迴下降分析器，分析稱為遞迴下降分析。

Ginni

更新於：2021年10月29日

11K+ 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習