本節書摘來自華章社群《antlr 4權威指南》一書中的第2章，第2.4節使用文法分析樹來建構語言類應用程式，作者［美］ 特恩斯·帕爾（terence parr），更多章節内容可以通路雲栖社群“華章社群”公衆号檢視
2.4 使用文法分析樹來建構語言類應用程式
為了編寫一個語言類應用程式，我們必須對每個輸入的詞組或者子詞組執行一些适當的操作。進行這項工作最簡單的方式是操作文法分析器自動生成的文法分析樹。這種方式的優點在于，我們能夠重回我們所熟悉的java領域。這樣，在語言類應用程式進一步的建構過程中，我們就不需要再學習複雜的antlr文法了。
首先，我們來認識一下antlr在識别和建立文法分析樹的過程中使用的資料結構和類名。熟悉這些資料結構将為我們未來的讨論奠定基礎。
前已述及，詞法分析器處理字元序列并将生成的詞法符号提供給文法分析器，文法分析器随即根據這些資訊來檢查文法的正确性并建造出一棵文法分析樹。這個過程對應的antlr類是charstream、lexer、token、parser，以及parsetree。連接配接詞法分析器和文法分析器的“管道”就是tokenstream。圖2-2展示了這些類型的對象在記憶體中的互動方式。
antlr盡可能多地使用共享資料結構來節約記憶體。如圖2-2所示，文法分析樹中的葉子節點（詞法符号）僅僅是盛放詞法符号流中的詞法符号的容器。每個詞法符号都記錄了自己在字元序列中的開始位置和結束位置，而非儲存子字元串的拷貝。其中，不存在空白字元對應的詞法符号（索引為2和4的字元）的原因是，我們假定我們的詞法分析器會丢棄空白字元。
圖2-2中也顯示出，parsetree的子類rulenode和terminalnode，二者分别是子樹的根節點和葉子節點。rulenode有一些令人熟悉的方法，例如getchild()和getparent()，但是，對于一個特定的文法，rulenode并不是确定不變的。為了更好地支援對特定節點的元素的通路，antlr會為每條規則生成一個rulenode的子類。如圖2-3所示，在我們的指派語句的例子中，子樹根節點的類型實際上是statcontext、assigncontext以及exprcontext。
因為這些根節點包含了使用規則識别詞組過程中的全部資訊，它們被稱為上下文（context）對象。每個上下文對象都知道自己識别出的詞組中，開始和結束位置處的詞法符号，同時提供通路該詞組全部元素的途徑。例如，assigncontext類提供了方法id()和方法expr()來通路辨別符節點和代表表達式的子樹。
給定這些類型的具體實作，我們可以手工寫出對文法分析樹進行深度優先周遊的代碼。這樣，在通路其中的節點時，我們可以進行一切所需的操作。這個過程中的典型操作是諸如計算結果、更新資料結構或者産生輸出一類的事情。實際上，我們可以利用antlr自動生成并周遊樹的機制，而不需要每次都重複編寫周遊樹的代碼。
2.5 文法分析樹監聽器和通路器
antlr的運作庫提供了兩種周遊樹的機制。預設情況下，antlr使用内建的周遊器通路生成的文法分析樹，并為每個周遊時可能觸發的事件生成一個文法分析樹監聽器接口（parse-tree listener interface）。監聽器非常類似于xml解析器生成的sax文檔對象。sax監聽器接收類似startdocument()和enddocument()的事件通知。一個監聽器的方法實際上就是回調函數，正如我們在圖形界面程式中響應複選框點選事件一樣。除了監聽器的方式，我們還将介紹另外一種周遊文法分析樹的方式：通路者模式（vistor pattern）。
1.文法分析樹監聽器
為了将周遊樹時觸發的事件轉化為監聽器的調用，antlr運作庫提供了parsetree-
walker類。我們可以自行實作parsetreelistener接口，在其中填充自己的邏輯代碼（通常是調用程式的其他部分），進而建構出我們自己的語言類應用程式。
antlr為每個文法檔案生成一個parsetreelistener的子類，在該類中，文法中的每條規則都有對應的enter方法和exit方法。例如，當周遊器通路到assign規則對應的節點時，它就會調用enterassign()方法，然後将對應的文法分析樹節點——assigncontext的執行個體——當作參數傳遞給它。在周遊器通路了assign節點的全部子節點之後，它會調用exitassign()。圖2-4用粗虛線辨別了parsetreewalker對文法分析樹進行深度優先周遊的過程。
其中，粗虛線顯示了對文法分析樹進行深度優先周遊的過程。細虛線标示出通路器方法的調用順序。我們可以在自己的程式代碼中實作這個通路器接口，然後調用visit()方法來開始對文法分析樹的一次周遊。
antlr内部為通路者模式提供的支援代碼會在根節點處調用visitstat()方法。接下來，visitstat()方法的實作将會調用visit()方法，并将所有子節點當作參數傳遞給它，進而繼續周遊的過程。或者，visitmethod()方法可以顯式調用visitassign()方法等。
antlr會提供通路器接口和一個預設實作類，免去我們一切都要自行實作的麻煩。這樣，我們就可以專注于那些我們感興趣的方法，而無須覆寫接口中的方法。我們将在第7章中深入介紹通路器和監聽器。
與文法分析相關的術語
本章介紹了很多重要的與語言識别相關的術語。
語言 一門語言是一個有效語句的集合。語句由詞組組成，詞組由子詞組組成，子詞組又由更小的子詞組組成，依此類推。
文法 文法定義了語言的語義規則。文法中的每條規則定義了一種詞組結構。
語義樹或文法分析樹 代表了語句的結構，其中的每個子樹的根節點都使用一個抽象的名字給其包含的元素命名。即子樹的根節點對應了文法規則的名字。樹的葉子節點是語句中的符号或者詞法符号。
詞法符号 詞法符号就是一門語言的基本詞彙符号，它們可以代表像是“辨別符”這樣的一類符号，也可以代表一個單一的運算符，或者代表一個關鍵字。
詞法分析器或者詞法符号生成器 将輸入的字元序列分解成一系列詞法符号。一個詞法分析器負責分析詞法。
文法分析器 文法分析器通過檢查語句的結構是否符合文法規則的定義來驗證該語句在特定語言中是否合法。文法分析的過程好比是走迷宮，通過比較語句中和地闆上的單詞來從入口走到出口。antlr能夠生成被稱為all()的自頂向下的文法分析器，all()是指它可以利用剩餘的所有輸入文本來進行決策。自頂向下的文法分析器以結果為導向，首先比對最粗粒度的規則，這樣的規則通常命名為program或者inputfile。
遞歸下降的文法分析器 這是自頂向下的文法分析器的一種實作，每條規則都對應文法分析器中的一個函數。
前向預測 文法分析器使用前向預測來進行決策，具體方法是：将輸入的符号與每個備選分支的起始符号進行比較。
迄今為止，我們已經大體上了解了antlr的工作原理。在本章中，我們認識了從字元序列到文法分析樹的整個流程，學習了antlr運作庫的一些關鍵類。此外，我們還簡單了解了監聽器和通路器機制，它們是連接配接文法分析器和特定程式代碼的橋梁。在下一章中，我們将通過一個實際的例子來使大家加深對上述概念的了解。