如何处理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]

所以，首先我试着写一个语法表达式()是这样定义的

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);
}
}

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

注:我有一个选项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

这是一个关于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是项

输入expression时，首先解析一个术语、一个操作符和一个术语。现在堆栈将包含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)

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

Answer 2

这样如何:

void Expression(): {} {
Expression1() (<OR> Expression1())*
}
void Expression1(): {} {
Term() (<AND> Term())*
}
void Term(): {} {
(<NOT>)? Term1()
| <LROUND> Expression() <RROUND>
}
void Term1(): {} {
KeyPhrase() <LSQUARE> Field() <RSQUARE>
}