淺談分析器細節
目錄
- Parcel的定義
- Parse Tree的生成方式
- Parcel的分類
- Top-Down Parsers
- 帶有Backtracking的Top-Down Parsers
- 不帶有Backtracking的Top-Down Parsers
- Bottom-Up Parsers
- Operator Precedence Parsers
- LR Parsers
Parcel - 綜合本章內容
送交經過詞彙分析器處理的程式碼將變成一個字串,然後這個字串會被分析器所生成的Parcel程式所處理。Parcel的任務是根據底層語法生成解析樹。解析樹只有在字串可以由底層語法生成時才能被生成。因此,Parcel將接受字串作為輸入,並根據底層語法生成相應的解析樹。
Parcel的生成方式可以分為自上而下和自下而上兩種方法。
自上而下生成解析樹
在自上而下的方法中,我們從起始符號開始。首先,我們將選擇起始符號。觀察到在這個示例中,起始符號S可以被推導為小寫字母a接著是大寫字母A接著是大寫字母B最後是小寫字母e。這樣,我們從起始符號開始生成了以下推導過程:小寫字母a+大寫字母A+大寫字母B+小寫字母e。在這個過程中,我們不斷擴展最左邊的非終端符號,這被稱為最左推導。
自下而上生成解析樹
在自下而上的方法中,我們將直接使用字串作為起點,並使用產生規則來將字串進行縮減,直到回到起始符號。舉例來說,我們從字串a開始,根據產生規則,將a縮減為A。然後我們將abc縮減為A,最後將所有元素縮減回起始符號S。在這個過程中,我們從字串開始,不斷應用還原操作,直到回到起始符號,這被稱為最右邊推導。
分析器的分類
根據生成解析樹的方法,分析器可以分為兩個大類:自上而下和自下而上。
自上而下分析器
自上而下分析器可以進一步分為帶有回溯和不帶回溯的兩種類型。
帶有回溯的自上而下分析器
帶有回溯的自上而下分析器利用了CFG中的非確定性。這種分析器的一個例子是強制使用回溯的Brute-Force語法分析器。
不帶回溯的自上而下分析器
不帶回溯的自上而下分析器可以進一步區分為遞迴下降分析器和預測分析器。
遞迴下降分析器和預測分析器的一些例子分別是LL(1)和LL(k)。
自下而上分析器
自下而上分析器也稱為移位-歸約分析器。根據如何移位和歸約,這些分析器可以分為運算符順序分析器和LR分析器。
LR分析器可以進一步分為LR(0),SLR(1),LLR(1)和CLR(1)。
除了運算符順序分析器外,其他所有分析器都無法處理模糊的語法。
這就是分析器的分類。
在本章中,我們將重點介紹自上而下分析器中的自上而下分析器,並在下一章中介紹所有自下而上分析器的詳細內容。希望在下一節中見到您!謝謝!