对于此语法，我如何处理 JavaCC 中所有运算符的左关联？

Question

你能帮我找到解决这个问题的方法吗？

我正在用 JavaCC 实现一个解析器，它能够读取并放入树结构中这种搜索表达式

(keyphrase1[field1] AND (keyphrase2[field2] OR keyphrase3[field3])) OR (keyphrase4 AND keyphrase5*[field5])

当我有这种歧义时，我需要将优先级设置在左边，例如在这种情况下

keyphrase[field] AND keyphrase[field] OR keyphrase[field]

我想获得一棵对应

的树

(keyphrase[field] AND keyphrase[field]) OR keyphrase[field]

所以，首先我尝试编写一个语法，其中 Expression() 是这样定义的

void Expression(): {} {
  <LROUND> Expression() <RROUND>
| Expression() Operator() Expression()
| Term()
}

但是 JavaCC 要求左递归，所以我试图改变它。这是我现在实现的语法规则。

SKIP : {
  " "
| "\n"
| "\r"
| "\t"
}

TOKEN : {
  <LROUND: "(">
| <RROUND: ")">
| <KEYWORD: ( ["a"-"z","0"-"9"] )+>
| <WILDCARD: "*">
| <LSQUARE: "[">
| <RSQUARE: "]">
| <AND: "AND">
| <OR: "OR">
| <NOT: "NOT">
}

ASTStart Start(): {} {
  Expression() <EOF>
  { return jjtThis; }
}

void Expression(): {} {
  <LROUND> Expression() <RROUND> (Operator() Expression())*
| Term() (Operator() Expression())*
}

void Term(): {} {
  KeyPhrase() [Field()]
}

void KeyPhrase(): 
{
  Token k;
  Token w;
  String keyPhrase = "";
} 
{
  (k=<KEYWORD> {keyPhrase += (keyPhrase.equals("") ? "" : " ") + k.image;})+ [w=<WILDCARD> {keyPhrase += w.image;}] 
  {jjtThis.jjtSetValue(keyPhrase);}
}

void Field():
{
  Token f;
} 
{
    <LSQUARE> f=<KEYWORD> {jjtThis.jjtSetValue(f.image);} <RSQUARE>
}

void Operator(): 
{
  Token op;
} 
{
  op=<AND>
  {
    jjtThis.jjtSetValue(op.image);
  }
  | op=<OR>
  {
    jjtThis.jjtSetValue(op.image);
  }
  | op=<NOT>
  {
    jjtThis.jjtSetValue(op.image);
  }
}

问题是这个设置的优先级在出现歧义的情况下，我该如何解决？

P.S。我有选项 LOOKAHEAD=2

编辑：我也尝试过这种方式，先重复，但解析器在最后一个表达式之后尝试查找运算符时遇到 EOF

ASTStart Start(): {} {
  Expression() <EOF>
  { return jjtThis; }
}

void Expression(): {} {
  (Operand() Operator())* Operand()
}

void Operand(): {} {
  ParenthesizedExpression()
| Term()
}

void ParenthesizedExpression(): {} {
  <LROUND> Expression() <RROUND>
}

void Term(): {} {
  KeyPhrase() [Field()]
}

Answer 1

这样的事情怎么样：

void Expression(): {} {
    Expression1() (<OR> Expression1())*
}

void Expression1(): {} {
    Term() (<AND> Term())*
}

void Term(): {} {
    (<NOT>)? Term1()
    | <LROUND> Expression() <RROUND>
}

void Term1(): {} {
    KeyPhrase() <LSQUARE> Field() <RSQUARE>
}

Answer 2

这真是一道JJTree题。诀窍是使用 确定节点 。 ( https://javacc.github.io/javacc/documentation/jjtree.html#introduction .)

void Expression() #void :
{ }
{
   SimpleExpression()
   (
       Operator()
       SimpleExpression() 
       #BinOp(3)
   )*
}

void SimpleExpression() #void :
{ }
{
   Term()
|
   "(" Expression() ")"
}

为什么我认为这会起作用：假设您有输入

W OR X AND Y NOT Z

其中 W、X、Y 和 Z 是项

当输入表达式时，它首先解析一个术语、一个运算符和一个术语。现在堆栈将包含 3 个节点：

  (top)   X   OR   W  (bottom)

当遇到 BinOp(3) 时，弹出这 3 个节点并推送新节点。现在堆栈是

(top)  BinOp(W, OR, X)  (bottom)

循环重新开始，另外两个节点将被推送。堆栈现在

(top) Y   AND   BinOp(W, OR, X)  (bottom)

遇到 BinOp(3)。它弹出3个节点并推一个给

(top) BinOp(BinOp(W, OR, X), AND, Y) (bottom)

另一个运算符和术语被解析，所以堆栈是

(top) Z   NOT   BinOp(BinOp(W, OR, X), AND, Y) (bottom)

再次遇到 BinOp(3)，我们得到

(top)   BinOp( BinOp(BinOp(W, OR, X), AND, Y), NOT, Z)  (bottom)

在 https://github.com/theodore-norvell/the-teaching-machine-and-webwriter/blob/master/trunk/tm/src/tm/javaLang/parser/JavaParser.jjt 上查看我的 Java 解析器以获得完整示例。从第 1155 行开始，还要查看顶部的选项。

对于此语法，我如何处理 JavaCC 中所有运算符的左关联？

How can I handle left association for all operator in JavaCC for this grammar?

java

grammar

parsing

javacc

ebnf