如何在Java中表示一種上下文無關文法？

Question

我有一個簡單的語法：

R --> R and R | R or R | atom 

我們唯一的終端是原子。 這是一個遞歸語法，因爲每個R可以被嵌套R. 由我所面臨的問題是：

1. 如何處理遞歸？
2. 如何構建一個可以通過3條規則之一解決的java類R？

您如何用Java類表示這種語法？

Answer 1

最簡單的方法是將所有規則標準化爲單個選項，然後將它們表示爲數組數組。

首先，我們爲語法中的每個「原子」（標記）分配一個唯一的代碼。

然後，規則都應該被歸爲

LHS --> RHS1 RHS2 ... RHSn 

e.g，規則由：甲 - >乙| c應該被規範化爲兩個規則，a - > b和a - > c。如果您有其他奇特的符號EBNF設備，例如kleene start或plus，您也可以對它們進行標準化。

現在你有K規則;你可以定義一個有K個插槽的陣列，每個插槽都有一個規則。規則槽包含一對：LHS和該規則的大小爲n的數組。 （更簡單一點：規則插槽包含大小爲n + 1的數組，最左邊的元素索引0保存LHS，索引1保存RHS1等）。

現在，您已經有了用Java表示的語法。

[遞歸語法的語義特性，而不是它的代表性。]

另：如果你建立一個經典的解析器BNF（畢竟，（E）BNF有一個語法，太），你可以使用解析器解析您的BNF，併爲此構建一棵樹。這顯然也是一種表現形式。作爲要處理的數組數組並不方便。