parsing - Javacc 无法访问语句

Question

在我的语法中，有最初包含间接左递归的表达式和片段的产生规则。这是我删除了递归之后的规则。

String expression() #Expression : {String number; Token t;}
{
    number = fragment()
    (
        (t = <Mult_Sign> number = fragment())
    )
    {return number;}
}

String fragment() #void : {String t;}
{
    t = identifier() {return t;}
    | t = number() {return t;}
    | (<PLUS> | <MINUS> ) fragment()
    | <LBR> expression() <RBR>
}

这些产生式规则在尝试解析语法中的条件时使用。然而，产生式规则的排序要么有它，所以只接受表达式。但它应该接受像 while (x <= 10) 这样的东西。如果我的产生式规则与语法中最初所述的相反顺序。当我尝试使用 javac 编译 java 文件时。我收到一条错误，告诉我identifier() 是一个无法访问的语句。这是条件产生规则:

void condition() #void : {Token t;}
{
    <NOT> expression()
    | expression (<EQUALS>|<NOTEQUALS>|<LT>|<GT>|<LTE>|<GTE>|<AND>|<OR>) expression()
    | identifier()
}

如果有人可以帮助告诉我为什么会出现此问题，那将会非常有帮助。

Answer 1

你有

void condition() #void : {Token t;}
{
/*a*/     <NOT> expression()
/*b*/     | expression (<EQUALS>|<NOTEQUALS>|<LT>|<GT>|<LTE>|<GTE>|<AND>|<OR>) expression()
/*c*/     | identifier()
}

如果解析器正在寻找条件，它将尝试根据下一个输入标记在三个选项之间进行选择。如果该标记是标识符，则存在问题，因为替代方案 (b) 或替代方案 (c) 都可以工作。面对选择冲突，JavaCC更倾向于第一个，因此会选择(b)。如果下一个标记不是标识符，则不会选择方案 (c)。因此，无论哪种方式，都不会达到替代方案 (c)。

<小时/>

那是你的问题。对此应该做什么？这是通常的解决方案。

如果您想在表达式中允许使用更多运算符，请使用更多非终结符来表示更多优先级。例如

condition --> expression
expression --> disjunct (OR expression)?
disjunct --> conjunct (AND disjunct)?
conjunct --> comparand ((EQ|NEQ|LT|GT|LE|GE) comparand)?
comparand --> term ((PLUS|MINUS) term)*
term --> fragment ((TIMES | DIVIDE) fragment)*
fragment --> identifier | number | LBR expression RBR | (PLUS|MINUS|NOT) fragment

这个语法将接受你想要的一切，甚至可能更多。例如，如果您有

statement --> WHILE condition DO statement

你的解析器将接受例如“当 a+b 执行 a:=b 时”。在许多语言中，这是通过类型检查来处理的； Java就是这样做的。在其他语言中，它是通过允许各种事物作为条件来处理的； LISP 就是这样做的。

<小时/>

关于 NOT 优先级的说明

大多数语言都将 NOT 的优先级视为非常高，如本答案的第二部分所示。由于语法是 LL(1)，因此这具有消除所有选择警告的良好效果。

但是，如果您希望一元运算符具有较低的优先级，那么如果您使用 JavaCC，那么实际上没有什么可以阻止您。例如。您可以将片段更改为

fragment --> identifier | number | LBR expression RBR | (PLUS|MINUS) fragment | NOT conjunct

现在语法不是 LL(1)(它甚至不是明确的)。所以JavaCC会给出一些选择冲突的警告。但它实际上会解析例如“NOT a LT b”为“NOT (a LT b)”

<小时/>

几乎没有语言所做的正是我认为您正在尝试做的，即限制语法，以便只有看起来像条件​​的表达式才允许作为条件。如果这确实是您想要的，那么您可以使用 JavaCC 使用语法前瞻来实现。以下是具体操作方法。

从这样的语法开始。 (这本质上是您的想法，更多地关注优先级。)

condition --> disjunct (OR condition)?
disjunct --> conjunct (AND disjunct)?
conjunct --> expression (EQ|NEQ|LT|GT|LE|GE) expression
           | LBR condition RBR
           | NOT conjunct
           | identifier

expression --> term ((PLUS|MINUS) term)*
term --> fragment ((TIMES | DIVIDE) fragment)*
fragment --> identifier | number | LBR expression RBR | (PLUS|MINUS) fragment

这是一个明确的条件语法。然而，当下一个标记是标识符或 LBR 时，它会同时出现选择冲突。为了解决这种选择冲突，您可以使用语法先行来查找比较运算符

void conjunct() : { } {
    LOOKAHEAD( expression() (<EQ>|<NEQ>|<LT>|<GT>|<LE>|<GE>) )
    expression() (<EQ>|<NEQ>|<LT>|<GT>|<LE>|<GE>) expression()
|   LBR condition() RBR
|   NOT conjunct()
|   identifier() {

那么为什么(几乎)没有编程语言这样做呢？大多数语言都有 bool 类型的变量，因此，像您一样，允许标识符作为条件。因此，您仍然需要进行类型检查以排除“WHILE i DO ...”，其中“i”不是 bool 类型。另外，赋值语法应该使用什么？你需要

statement --> identifier := (expression | condition) | ...

即使是语法前瞻也不会告诉您哪个选择适合“x := y”。这是一个有歧义的语法。

如果在两个选项都解析的情况下任一选项都是可接受的，那么您也可以在此处使用语法前瞻。

void statement() : {} {
    identifier <BECOMES> (LOOKAHEAD(condition()) condition()) | expression())
| ...
}

这会将“x:=y”中的“y”解析为条件，即使它是数字。如果您意识到这一点并设计编译器的其余部分，以便一切仍然有效，则不会造成任何损害。

这种方法的另一个缺点是理论上解析时间是二次方。我认为这不是一个严重的问题。