編譯器設計——解析型別

語法分析器遵循無上下文文法定義的產生規則。產生規則的實現方式（匯出）將解析分為兩種型別：自頂向下解析和自底向上解析。

自頂向下解析

如果解析器開始使用起始符構建解析樹，然後嘗試將起始符轉換為輸入，則稱之為自頂向下解析。

• 遞迴下降解析：這是自頂向下解析的一種常見形式。它被稱為遞迴，因為它使用遞迴過程來處理輸入。遞迴下降解析會回溯。

• 回溯：這意味著，如果某個產生規則的匯出失敗，語法分析器會使用同一產生規則的不同規則重新開始這一過程。此技巧可能會多次處理輸入字串以確定正確的產生規則。

自底向上解析

顧名思義，自底向上解析從輸入符開始，嘗試構建直到起始符的解析樹。

示例

輸入字串：a + b * c

產生規則

S → E
E → E + T
E → E * T
E → T
T → id

讓我們開始自底向上解析

a + b * c

讀取輸入並檢查是否有任何產生規則與該輸入匹配

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S