5

我准备了以下生成 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?)

4

2 回答 2

2

示例文法(几乎)是运算符优先文法,或弗洛伊德文法(FG)。要使其成为 FG,您必须对右侧仅由单个终端组成的非终端进行宏扩展,因为运算符优先级语法必须是运算符语法,并且运算符语法具有没有右-手边有两个连续的非终结符。

所有运算符优先级文法都是LR(1). 显示运算符语法是否具有优先级属性也是微不足道的,特别是在每个终端恰好出现在右侧的情况下,就像在您的语法中一样。每个终结符恰好出现在右侧的运算符文法始终是运算符优先文法 [1],因此始终是LR(1).

FG 是一大类语法,其中一些甚至有用(例如,Algol 60 由 FG 描述),因此很容易回答关于它们是LR(k)for some的问题k,因为答案总是“是的,有K == 1”。只是为了精确,这里是属性。我们使用常规约定,其中语法G是 4 元组 (N, Σ, P, S),其中N是一组非终结符;Σ是一组终端,P是一组产生式,S是开始符号。我们VN ⋃ Σ. 在任何语法中,我们都有:

N ⋂ Σ = ∅
S ∈ N
P ⊂ V+ × V*

“无上下文”要求受到限制P,因此每个左侧都是一个非终端:

P ⊂ Σ × V*

在操作符文法中,P进一步限制:没有右边是空的,也没有右边有两个连续的非终结符:

P ⊂ Σ × (V+ − V*ΣΣV*)

在运算符优先语法中,我们定义了三个优先关系,⋖、⋗和≐。这些是根据关系LeadsTrails[2] 定义的,其中 `

T Leads V iff T is the first terminal in some string derived from V
T Trails V iff T is the last terminal in some string derived from V

然后:

t1 ⋖ t2 iff ∃v ϶ t2 Leads v ∧ N→V*t1vV* ∈ P
t1 ⋗ t2 iff ∃v ϶ t1 Trails v ∧ N→V*vt2V* ∈ P
t1 ≐ t2 iff N→V*t1t2V* ∈ P ∨ N→V*t1V't2V* ∈ P

考虑这些关系的一种直观方式是:通常当我们进行推导时,我们只是将 RHS 替换为 LHS,但假设我们⋖ RHS ⋗改为替换。然后我们可以通过删除非终结符并将连续的 ⋖ 和 ⋗ 字符串折叠为单个符号来修改推导,最后在没有中间运算符的任意两个连续终结符之间添加 ≐。从那里,我们只是读出了关系。

现在,我们可以在任何运算符文法上执行该计算,但没有什么可以强制上述关系是排他的。如果这三个关系是互斥的,那么运算符文法就是 Floyd 文法。

验证运算符语法是否具有互斥优先关系是直截了当的;Leads并且Trails需要对 and 进行传递闭包FirstLast大致是(它实际上是非终结符的数量和产生的数量的乘积);从那里,可以通过对语法中的所有产生式进行一次线性扫描来计算优先关系,即.O(|G|2)O(|G|)

于 2012-12-21T01:59:38.103 回答
1

摘自 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))。

于 2012-12-20T19:59:16.417 回答