javacc 中的右结合运算符

Question

我需要编写一个程序来检查 F1 类型系统的类型，但我不知道如何制定使关联运算符正确的规则。

我需要的是，如果我解析像 Nat -> Nat -> Nat 这样的东西，那应该被解析为 Nat -> (Nat -> Nat)，而不是 (Nat -> Nat) -> Nat (我想构建一个 AST 并在其上做一些事情）

我现在拥有的是：

Node Type2() {Node t1;}
{
    "Nat" { return Node("Nat", null, null);}
    |
    "Bool" { return Node("Bool", null, null);}
    |
    "(" t1=Type() ")" {return t1;}
}
Node Type() {Node t1; Node t2;}
{
    t1 = Type2() (" -> " t2 = Type2() { return Node("->", t1, t2); }
}

但是它是左结合的，我怎样才能让它正确？

语法是：

type              = "Bool" | "Nat" | type, "->", type | "(", type, ")";
lambda_expression = variable
              | "\", variable, ":", type, ".", lambda_expression
              | lambda_expression, " ", lambda_expression
              | "(", lambda_expression, ")";
type_context      = variable, ":", type, { ",", variable, ":", type };
expression        = [ type_context ], "|-", lambda_expression, ":", type;

谢谢

Answer 1

使用循环代替递归

Node Type() :
{Node t1; Node t2;}
{
    t1 = Type2()
    (   " -> "
        t2 = Type2() 
        { t1 =  Node("->", t1, t2); }
    )*
    {return t1 ; }
}

或者——其实是一样的——使用正确的递归。

Node Type() :
{Node t1;}
{
    t1 = Type2()
    t1 = MoreType( t1 ) ;
    {return t1 ; }
}

Node MoreType(Node t1) :
{Node t2;}
{
    " -> " t2 = Type2() t1 = MoreType( new Node( "->", t1, t2 ) ) {return t1; }
|
    {return t1; }
}

Answer 2

这里有一个直接使用LL(1)文法的解决方案：

Type2 =
| "Nat"
| "Bool"
| "(" Type ")"

Type =
| Type2 ( "->" Type )?

以解析Nat -> Bool -> Nat为例：

从解析Type开始，Nat匹配Type2。
然后解析器看到 ->，所以它知道 ( ... )? 中的所有内容都应该被解析而不是被忽略。现在它尝试递归匹配 Type 与剩余输入，即 Bool -> Nat.
在Type的这个递归解析中，首先，Bool被Type2匹配，然后解析器看到->。因此，它再次尝试递归匹配 Type 与剩余输入，即 Nat.
在Type的第三次解析中，Nat被Type2匹配，但是解析器没有看到后面的->，所以它决定忽略( ... )? 并终止。

在上面的解析中，Bool -> Nat在第2~4步一起解析，Nat -> (Bool -> Nat)在第1~4步一起解析。这样我们就得到了正确的结合律。

对应的JavaCC代码：

Node Type2() :
{ Node t1; }
{
  "Nat" { return new Node("Nat", null, null); }
| "Bool" { return new Node("Bool", null, null); }
| "(" t1=Type() ")" { return t1; }
}

Node Type() :
{ Node t1; Node t2; }
{
  t1=Type2() ( " -> " t2=Type() { return new Node("->", t1, t2); } )? { return t1; }
}

javacc 中的右结合运算符

right associative operator in javacc

javacc