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为例：

1. 从解析Type开始，Nat与Type2匹配。
2. 然后解析器看到->，因此它知道( ... )?内部的所有内容都应被解析而不是被忽略。现在，它尝试将Type与其余输入Bool -> Nat进行递归匹配。
3. 在此Type的递归解析中，首先，Bool与Type2匹配，然后解析器将看到->。因此，它再次尝试将Type与其余输入Nat进行递归匹配。
4. 在Type的第三次解析中，Nat与Type2匹配，但是解析器在其后看不到->，因此它决定忽略( ... )?并终止。

在上面的解析中，在步骤2〜4中将Bool -> Nat解析在一起，在步骤1〜4中将Nat -> (Bool -> Nat)解析在一起。这样就获得了正确的关联性。

对应的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; }
}