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提供特定的代码替代方案。