从此示例确定LR（k）的k？

  • Z时代
  • 2024-01-10
  • 分类：问答

我准备了以下语法，该语法生成​​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？）

回答：

从唐纳德·克努斯（Donald

Knuths）谈抽象的语言从左到右，

结果表明，对于 某个k而言 ，语法是否为LR（k）的问题尚不确定，

换一种说法，

给定语法G，“ ∃k.G∊LR（k）”是不确定的。

因此， 一般而言 ， 我们能做的最好的事情是尝试为LR（0），然后为LR（1），LR（2）等构造一个解析器。有时，您将成功，或者当 k

时，您可能会放弃变大。

回答：

在这种情况下，我碰巧知道您给出的语法是LALR（1），这意味着它必须是LR（1）。我知道这是因为我已经为类似的语言编写了LALR解析器。出于显而易见的原因，它不能是LR（0）（语法{A->

x，A-> A + x}不是LR（0））。

以上是 从此示例确定LR（k）的k？ 的全部内容， 来源链接： utcz.com/qa/398775.html

回到顶部