从这个例子中确定LR(k)的k？

Question

我准备了以下语法,生成C逻辑和整数算术表达式的子集:

Expression:
    LogicalOrExpression
    LogicalOrExpression ? Expression : LogicalOrExpression

LogicalOrExpression:
    LogicalAndExpression
    LogicalOrExpression || LogicalAndExpression

LogicalAndExpression:
    EqualityExpression
    LogicalAndExpression && RelationalExpression

EqualityExpression:
    RelationalExpression
    EqualityExpression EqualityOperator RelationalExpression

EqualityOperator:
    ==
    !=

RelationalExpression:
    AdditiveExpression
    RelationalExpression RelationalOperator AdditiveExpression

RelationalOperator:
    <
    >
    <=
    >=

AdditiveExpression:
    MultiplicativeExpression
    AdditiveExpression AdditiveOperator MultiplicativeExpression

AdditiveOperator:
    +
    -

MultiplicativeExpression:
    UnaryExpression
    MultiplicativeExpression MultiplicativeOperator UnaryExpression

MultiplicativeOperator:
    *
    /
    %

UnaryExpression:
    PrimaryExpression
    UnaryOperator UnaryExpression

UnaryOperator:
    +
    -
    !

PrimaryExpression:
    BoolLiteral    // TERMINAL
    IntegerLiteral // TERMINAL
    Identifier     // TERMINAL
    ( Expression )

我想尝试使用shift/reduce解析,因此想知道这个语法是LR(k)的最小k(如果有的话)是什么？(更一般地说,如果可能的话,如何从任意语法中确定k？)

Answer 1

从唐纳德·高德纳 (Donald Knuths) 的《论从左到右的语言翻译》中，抽象地说，

\n\n

\n

结果表明，对于某些 k，文法是否是 LR(k) 的问题是不可判定的，

\n

\n\n

换句话说，

\n\n

\n

给定文法 G，“\xe2\x88\x83k.G \xe2\x88\x8a LR(k)”是不可判定的。

\n

\n\n

因此，我们通常能做的最好的事情就是尝试为 LR(0) 构造一个解析器，然后为 LR(1)、LR(2) 等构造一个解析器。在某些时候您会成功，或者您可能在某个时候放弃k变大。

\n\n

这个具体语法

\n\n

在这种特定情况下，我碰巧知道您给出的语法是 LALR(1)，这意味着它必须是 LR(1)。我知道这一点是因为我为类似的语言编写了 LALR 解析器。由于显而易见的原因，它不可能是 LR(0)（语法 {A -> x, A -> A + x} 不是 LR(0)）。

\n