Antlr4解析器布爾邏輯

Question

我是新來Antlr4/CFG，我試圖寫一個解析器形式的布爾查詢DSL

（ID和ID和ID（或ID號或ID ））

所述邏輯還可以採取的形式

（ID或ID，或（ID和ID和ID））

一個更復雜的例子可以是：

（（（ID和ID和（ID或ID，或（ID和ID））））） （括在括號中的任意量）

我試過兩件事。首先，我做了一個非常簡單的語法分析器，它結束瞭解析一切左至右：

grammar filter; 

filter: expression EOF; 

expression 
    : LPAREN expression RPAREN 
    | expression (AND expression)+ 
    | expression (OR expression)+ 
    | atom; 

atom 
    : INT; 

我輸入下面的解析樹：

（60）和（55）和（53 ）和

這個 「作品」，但理想的我希望能夠到我的AND和OR塊分離（3337或2830或23）。試圖將這些塊分離成單獨的語法會導致左遞歸。其次，我想我的AND和OR塊組合在一起，而不是讀左到右，例如，在輸入（ID和ID和ID）， 我想：

（和ID號ID）

不

（和id（和id（和id）））

，因爲它目前是。

我試過的第二件事情是直接創建AND塊的後代（即第一種情況）。

grammar filter; 

filter: expression EOF; 

expression 
    : LPAREN expression RPAREN 
    | and_expr; 

and_expr 
    : term (AND term)* ; 

term 
    : LPAREN or_expr RPAREN 
    | LPAREN atom RPAREN ; 

or_expr 
    : atom (OR atom)+; 

atom: INT ; 

對於相同的輸入，我得到下面的解析樹，它是沿着什麼我正在尋找，但有一個主要問題的線路更多：沒有一個實際的層次結構，或和與塊在DSL中，所以這不適用於第二種情況。這種做法似乎也有點不好，因爲我正在努力做。

什麼是前進的最好方法是什麼？再一次，我對解析和CFG不太熟悉，所以一些指導會很棒。

Answer 1

兩者在解析您的示例輸入方面的能力是等同的。如果通過刪除不必要的括號簡化你的輸入，這種語法的輸出看起來也相當不錯：

grammar filter; 
filter: expression EOF; 
expression 
    : LPAREN expression RPAREN 
    | expression (AND expression)+ 
    | expression (OR expression)+ 
    | atom; 
atom : INT; 
INT: DIGITS; 
DIGITS : [0-9]+; 
AND : 'AND'; 
OR : 'OR'; 
LPAREN : '('; 
RPAREN : ')'; 
WS: [ \t\r\n]+ -> skip; 

這是我懷疑你的第一個語法看起來像其整體。

你的第二個需要太多的括號（我主要在term），而將AND和OR分解成單獨的規則而不是替代方案對我來說似乎並不乾淨。

可以簡化甚至更多，但：

grammar filter; 
filter: expression EOF; 
expression 
    : LPAREN expression RPAREN # ParenExp 
    | expression AND expression # AndBlock 
    | expression OR expression # OrBlock 
    | atom      # AtomExp 
    ; 
atom : INT; 
INT: DIGITS; 
DIGITS : [0-9]+; 
AND : 'AND'; 
OR : 'OR'; 
LPAREN : '('; 
RPAREN : ')'; 
WS: [ \t\r\n]+ -> skip; 

這給具有不同形狀的樹，但仍相當。並注意使用# AndBlock和# OrBlock標籤......這些「替代標籤」將使您的生成的偵聽器或訪問者爲每個標籤分別設置不同的方法，從而使您可以在語義和語法上將這兩者完全分開。也許這就是你想要的？

我最喜歡這個，因爲它是最簡單和最清晰的遞歸，併爲AND和OR提供特定的代碼替代方案。