java - 在不使用分词器状态的情况下消除分词歧义

Question

我无法让 JavaCC 通过标记在语法中的位置正确地消除它们的歧义。我有以下 JJTree 文件(我称之为 bug.jjt ):

options
{
  LOOKAHEAD = 3;
  CHOICE_AMBIGUITY_CHECK = 2;
  OTHER_AMBIGUITY_CHECK = 1;
  SANITY_CHECK = true;
  FORCE_LA_CHECK = true;
}
PARSER_BEGIN(MyParser)
import java.util.*;
public class MyParser {
    public static void main(String[] args) throws ParseException {
        MyParser parser = new MyParser(new java.io.StringReader(args[0]));
        SimpleNode root = parser.production();
        root.dump("");
    }
}
PARSER_END(MyParser)

SKIP:
{
    " "
}

TOKEN:
{
     <STATE:  ("state")>
     |<PROD_NAME: (["a"-"z"])+ >
}


SimpleNode production():
{}
{
    (
        <PROD_NAME>
        <STATE>
        <EOF>
    )
    {return jjtThis;}
}

使用以下代码生成解析器代码:

java -cp C:\path\to\javacc.jar jjtree bug.jjt
java -cp C:\path\to\javacc.jar javacc bug.jj

编译完之后，您可以从命令行运行 MyParser，并提供一个字符串作为参数进行解析。它打印出 production如果成功并在失败时喷出错误。

我尝试了两个简单的输入:foo state和 state state .第一个解析，但第二个不解析，因为两者都是 state字符串被标记为 <STATE> .当我设置 LOOKAHEAD到 3，我希望它使用语法并看到一个字符串 state必须是 <STATE>另一个必须是 <PROD_NAME .然而，没有这样的运气。我尝试更改各种前瞻参数无济于事。我也无法使用 tokenizer 状态(您在其中定义不同状态下允许的不同标记)，因为这个示例是一个更复杂的系统的一部分，该系统可能会有很多这些类型的歧义。

谁能告诉我如何让 JavaCC 在不使用标记器状态的情况下正确地消除这些标记的歧义？

Answer 1

这包含在 FAQ 中在问题 4.19 下。

那里概述了三种策略

在语法中添加选项。请参阅 Bart Kiers 的回答。

使用语义前瞻。对于这种方法，您可以摆脱定义 STATE 的产生式，并像这样编写语法

void SimpleNode production():
{}
{
    (
        <PROD_NAME>
        ( LOOKAHEAD({getToken(1).kind == PROD_NAME && getToken(1).image.equals("state")})
         <PROD_NAME>
         ...
        |
         ...other choices...
        )
    )
    {return jjtThis;}
}

如果没有其他选择，那么

void SimpleNode production():
{}
{
    (
        <PROD_NAME>
        ( LOOKAHEAD({getToken(1).kind == PROD_NAME && getToken(1).image.equals("state")})
         <PROD_NAME>
         ...
        |
         { int[][] expTokSeqs = new int[][] { new int[] {STATE } } ;
           throw new ParseException(token, expTokSeqs, tokenImage) ; }
        )
    )
    {return jjtThis;}
}

但是，在这种情况下，您需要一个 STATE 的产生式，正如在 expTokSeqs 的初始化中提到的那样。所以你需要制作。

< DUMMY > TOKEN : { < STATE : "state" > }

DUMMY 是一个永远不会到达的状态。

使用词法状态。OP 问题的标题表明他不想这样做，但没有说明原因。如果状态切换可以包含在 token 管理器中，则可以完成。假设一个文件是一系列作品，每个作品都像这样。

name state : "a" | "b" name ;

它以名称开头，然后是关键字“state”、冒号、一些标记，最后是分号。 (我只是编造这个，因为我不知道 OP 试图解析哪种语言。)然后你可以使用三种词法状态 DEFAULT、S0 和 S1。

• 在默认情况下，任何字母序列(包括“state”)都是 PROD_NAME。在 DEFAULT 中，识别 PROD_NAME 会将状态切换到 S0。
• 在 S0 中，除“state”之外的任何字母序列都是 PROD_NAME，而“state”是 STATE。在 S0 中，识别 STATE token 会导致 token 生成器切换到状态 S1。
• 在 S1 中，任何字母序列(包括“state”)都是 PROD_NAME。在 S1 中，识别分号会将状态切换为默认。

所以我们的例子是这样标记的

name  state  : "a" | "b" name ;
|__||______||_________________||_________
DEF-   S0             S1                    DEFAULT
AULT

作品是这样写的

<*> SKIP: { " " }

<S0> TOKEN: { <STATE: "state"> : S1 }

<DEFAULT> TOKEN:{ <PROD_NAME: (["a"-"z"])+ >  : S0 }
<S0,S1> TOKEN:{ <PROD_NAME: (["a"-"z"])+ >  }

<S1> TOKEN: { <SEMICOLON : ";" > : DEFAULT
<S0, DEFAULT> TOKEN : { <SEMICOLON : ";" > }

<*> TOKEN {
     COLON : ":"
|    ...etc...
}

解析器有可能将状态切换命令发送回分词器，但要让它正确且脆弱是很棘手的。请参阅常见问题解答的问题 3.12。