用于布尔逻辑的 Antlr4 解析器

Question

我是 Antlr4/CFG 的新手，正在尝试为

形式的布尔查询 DSL 编写解析器

(id AND id AND ID (OR id OR id OR id))

逻辑也可以采用

的形式

(id OR id OR (id AND id AND id))

一个更复杂的例子可能是：

(((id AND id AND (id OR id OR (id AND id))))) (enclosed in an arbitrary amount of parentheses)

我试过两件事。首先，我做了一个非常简单的解析器，它最终解析了从左到右的所有内容：

grammar filter;

filter: expression EOF;

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

atom 
    : INT;

我得到了以下用于输入的解析树：

( 60 ) AND ( 55 ) AND ( 53 ) AND ( 3337 OR 2830 OR 23)

这 "works"，但理想情况下我希望能够将我的 AND 和 OR 块分开。试图将这些块分成单独的语法会导致左递归。其次，我希望将我的 AND 和 OR 块组合在一起，而不是从左到右阅读，例如，在输入 (id AND id AND id) 时，我要：

(and id id id)

不是

(and id (and id (and id)))

目前的情况。

我尝试的第二件事是使 OR 块直接成为 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 标签的使用...这些 "alternative labels" 将导致您生成的侦听器或访问者各自具有单独的方法，从而使您可以在您的语义和句法上的代码。也许这就是您要找的东西？

我最喜欢这个，因为它是最简单和清晰的递归，并为 AND 和 OR 提供了特定的代码替代方案。

用于布尔逻辑的 Antlr4 解析器

Antlr4 parser for boolean logic

grammar

parsing

antlr

context-free-grammar

antlr4