自定義語言的實現——解釋器模式(二) – JAVA編程語言程序開發技術文章

18.2 文法規則和抽象語法樹
       解釋器模式描述瞭如何為簡單的語言定義一個文法,如何在該語言中表示一個句子,以及如何解釋這些句子。在正式分析解釋器模式結構之前,我們先來學習如何表示一個語言的文法規則以及如何構造一棵抽象語法樹。
       在前面所提到的加法/減法解釋器中,每一個輸入表達式,例如“1 + 2 + 3 – 4 + 1”,都包含瞭三個語言單位,可以使用如下文法規則來定義:
expression ::= value | operation
operation ::= expression '+' expression | expression '-'  expression
value ::= an integer //一個整數值
       該文法規則包含三條語句,第一條表示表達式的組成方式,其中value和operation是後面兩個語言單位的定義,每一條語句所定義的字符串如operation和value稱為語言構造成分或語言單位,符號“::=”表示“定義為”的意思,其左邊的語言單位通過右邊來進行說明和定義,語言單位對應終結符表達式和非終結符表達式。如本規則中的operation是非終結符表達式,它的組成元素仍然可以是表達式,可以進一步分解,而value是終結符表達式,它的組成元素是最基本的語言單位,不能再進行分解。
       在文法規則定義中可以使用一些符號來表示不同的含義,如使用“|”表示或,使用“{”和“}”表示組合,使用“*”表示出現0次或多次等,其中使用頻率最高的符號是表示“或”關系的“|”,如文法規則“boolValue ::= 0 | 1”表示終結符表達式boolValue的取值可以為0或者1。
       除瞭使用文法規則來定義一個語言,在解釋器模式中還可以通過一種稱之為抽象語法樹(Abstract Syntax Tree, AST)的圖形方式來直觀地表示語言的構成,每一棵抽象語法樹對應一個語言實例,如加法/減法表達式語言中的語句“1+ 2 + 3 – 4 + 1”,可以通過如圖18-2所示抽象語法樹來表示:
 

圖18-2  抽象語法樹示意圖
       在該抽象語法樹中,可以通過終結符表達式value和非終結符表達式operation組成復雜的語句,每個文法規則的語言實例都可以表示為一個抽象語法樹,即每一條具體的語句都可以用類似圖18-2所示的抽象語法樹來表示,在圖中終結符表達式類的實例作為樹的葉子節點,而非終結符表達式類的實例作為非葉子節點,它們可以將終結符表達式類的實例以及包含終結符和非終結符實例的子表達式作為其子節點。抽象語法樹描述瞭如何構成一個復雜的句子,通過對抽象語法樹的分析,可以識別出語言中的終結符類和非終結符類。
作者:劉偉

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。