1

我有这样的规则语法

A -> pq
B -> pr

Block -> { Astar Bstar }

Astar -> Astar A
       | epsilon

Bstar -> Bstar B
       | epsilon

有没有办法把这个语法变成 LALR(1)？据我所知，如果解析器p在块内看到，则存在移位/导出冲突。

4

2 回答 2

4

你的语言是正则的，相当于正则表达式\{(pq)*(pr)*\}。问题是任何简单的语法转换都需要两个字符的前瞻来查看是否有 aq或r之后p

现在你已经标记了这两者yacc，parsing所以不清楚你是在寻找“你如何用 yacc 处理这个问题”的实际答案还是“这种语言是否有 LALR(1) 语法”的理论答案。

对于实际的答案，解决方案是下注——将识别移到词法分析器中A，B在词法分析器中识别字符序列pq 并pr作为标记A和B. 由于 lex/flex 使用 DFA 并回溯到最长匹配的标记，因此它们在这里的任意前瞻没有问题。

对于理论上的答案，您需要转换语法以消除对前瞻的需要。有问题的构造是(pq)*(pr)*（大括号无关紧要），这相当于p(qp)*(rp)*r | p(qp)*q | epsilon建议如下语法：

Block -> { p Astar Bstar r }
       | { p Astar q }
       | { }
A -> q p
B -> r p
Astar -> Astar A | epsilon
Bstar -> Bstar B | epsilon

另一种方法是分解star规则以使它们不匹配空字符串：

Block -> { Aplus Bplus }
       | { Aplus }
       | { Bplus }
       | { }
A -> p q
B -> p r
Aplus -> Aplus A | A
Bplus -> Bplus B | B

为同一种语言提供两种截然不同的 LALR(1) 语法。

于 2013-05-01T17:54:18.177 回答
3

让我们从确切了解为什么会出现 LALR(1) 冲突开始，然后看看我们是否可以修改语法以使其成为 LALR(1)。

要了解为什么文法不是 LALR(1)，让我们从计算文法的 LR(1) 配置集开始：

(1)
S'     -> .Block [$]
Block  -> .{ Astar Bstar } [$]

(2)
S'     -> Block. [$]

(3)
Block -> { . Astar Bstar } [$]
Astar -> .Astar A [ }p ]
Astar -> .epsilon [ }p ]

(4)
Block -> { Astar . Bstar } [$]
Astar -> Astar .A [ }p]
A     -> .pq [}p]
Bstar -> .epsilon [ }p ]
Bstar -> . Bstar B [ }p ]

在这一点上，我们可以停下来，因为我们在符号 p 上的状态 (4) 中有一个移位/减少冲突：你是把 p 移位A -> .pq [ {p ]还是减少BStar -> .epsilon [ }p ]？由于 LR(1) 语法中存在移位/归约冲突，因此该语法根本不是 LR(1)，这意味着它不可能是 LALR(1)（因为每个 LALR(1) 语法也是一个 LR (1) 语法)。

从根本上说，问题在于，当解析器看到 a 时p，它无法判断它是否正在查看 a 的开头A（意味着它需要移动它）或者是否没有更多A的 ' 并且它正在查看a B（意味着它需要减少Bstar -> epsilon）。

为了解决这个问题，让我们看看如果我们做一个小调整会发生什么。p我们遇到的问题是解析器需要在看到是否移位或减少时立即确定。如果我们给它时间通过查看p和 后续字符来延迟决定呢？为此，让我们通过重写来稍微改变你的语法

Bstar -> epsilon
Bstar -> Bstar B

作为

Bstar -> epsilon
Bstar -> B Bstar

现在，解析器在决定做什么之前可以查看更多的标记。如果它在看pq，它就知道它没有在看任何与 B 相关的东西。如果它看到pr，它就知道它在看一个 B，因此可以开始进行第二类的制作。让我们看看如果我们这样做，我们的 LR(1) 状态会发生什么：

(1)
S'     -> .Block [$]
Block  -> .{ Astar Bstar } [$]

(2)
S'     -> Block. [$]

(3)
Block -> { . Astar Bstar } [$]
Astar -> .Astar A [ }p ]
Astar -> .epsilon [ }p ]

(4)
Block -> { Astar . Bstar } [$]
Astar -> Astar .A [ }p]
A     -> .pq [}p]
Bstar -> .epsilon [ } ]
Bstar -> . B Bstar [ } ]
B     -> .pr [}]

(5)
Block -> { Astar Bstar . } [$]

(6)
Block -> { Astar Bstar } . [$]

(7)
A     -> p.q [}p]
B     -> p.r [}]

(8)
A     -> .pq [}p]

(9)
B     -> pr. [}]

(10)
Bstar -> B . Bstar [ } ]
Bstar -> . B Bstar [ } ]
B     -> .pr [}]

(11)
B     -> p.r [}]

请注意，我们原来的移位/归约冲突已经消失，并且这个新语法根本不再有任何移位/归约冲突。此外，由于没有任何具有相同核心的状态对，因此上述状态集也是我们的 LALR(1) 表中的状态集。因此，上面的语法确实是LALR(1)，我们根本没有改变语法的意思。

希望这可以帮助！

于 2013-05-01T18:28:44.527 回答