ANTLR - 树中的隐式 AND 标记

Question

我正在尝试构建一种语法来解释用户输入的文本，搜索引擎风格。它将支持 AND、OR、NOT 和 ANDNOT bool 运算符。我几乎所有东西都在工作，但我想添加一个规则，将引用字符串之外的两个相邻关键字隐式地视为 AND 子句。例如:

奶酪和 cookies =奶酪和 cookies

(上下)或(左右)=(上下)或(左右)

cat dog “potbelly pig” = cat AND dog AND “potbelly pig”

我在最后一个问题上遇到了麻烦，我希望有人能指出我正确的方向。到目前为止，这是我的 *.g 文件，请注意，我的 ANTLR 体验不到一个工作日:

grammar SearchEngine;

options { language = CSharp2; output = AST; }

@lexer::namespace { Demo.SearchEngine }
@parser::namespace { Demo.SearchEngine }

LPARENTHESIS : '(';
RPARENTHESIS : ')';

AND    : ('A'|'a')('N'|'n')('D'|'d');
OR     : ('O'|'o')('R'|'r');
ANDNOT : ('A'|'a')('N'|'n')('D'|'d')('N'|'n')('O'|'o')('T'|'t');
NOT    : ('N'|'n')('O'|'o')('T'|'t');

fragment CHARACTER : ('a'..'z'|'A'..'Z'|'0'..'9');
fragment QUOTE     : ('"');
fragment SPACE     : (' '|'\n'|'\r'|'\t'|'\u000C');

WS     : (SPACE) { $channel=HIDDEN; };
PHRASE : (QUOTE)(CHARACTER)+((SPACE)+(CHARACTER)+)+(QUOTE);
WORD   : (CHARACTER)+;

startExpression  : andExpression;
andExpression    : andnotExpression (AND^ andnotExpression)*;
andnotExpression : orExpression (ANDNOT^ orExpression)*;
orExpression     : notExpression (OR^ notExpression)*;
notExpression    : (NOT^)? atomicExpression;
atomicExpression : PHRASE | WORD | LPARENTHESIS! andExpression RPARENTHESIS!;

Answer 1

由于您的 AND 规则具有可选的 AND 关键字，因此您应该创建一个虚构的 AND 标记并使用重写规则将该标记“注入(inject)”到您的树中。在这种情况下，您不能使用 ANTLR 的简写 ^根运算符(operator)。您必须使用 ->重写运算符。

您的 andExpression应该看起来像:

andExpression
  :  (andnotExpression        -> andnotExpression)
     (AND? a=andnotExpression -> ^(AndNode $andExpression $a))* 
  ;

在第 7 章的 节中给出了这个(可能是神秘的)符号的详细描述。重写子规则中的规则 ，第 173-174 页，共 The Definitive ANTLR Reference由特伦斯帕尔。

我进行了快速测试，看看语法是否使用新的 andExpression 生成正确的 AST。规则。解析字符串后 cat dog "potbelly and pig" and FOO ，生成的解析器产生以下 AST:

alt text http://img580.imageshack.us/img580/7370/andtree.png

请注意 AndNode和 Root是 imaginary tokens .

如果您想知道如何创建上面的 AST 图片，请参阅此线程: Visualizing an AST created with ANTLR (in a .Net environment)

编辑

当同时解析 one two three和 (one two) three ，创建以下 AST:

alt text http://img203.imageshack.us/img203/2558/69551879.png

并且在解析 (one two) OR three 时，创建以下 AST:

alt text http://img340.imageshack.us/img340/8779/73390353.png

这似乎是所有情况下的正确方法。