parsing - LR(0) 解析器冲突

Question

我对 lr(0) 解析器有疑问。例如，我有以下语法：

S -> S N
   | 

N -> terminalsymbol

如果我尝试构造 lr0 自动机的第一个状态，我会得到以下第一个状态：

S ' -> . S $ 

S -> . S N
S -> .

所以在我看来，这是一个愚蠢的怀疑。因为我有“S ->”。在第一种状态下，这是 lr0 解析器中移位/减少的情况吗？导致解析器可以通过非终结符 S 转移动作，或者通过空转换减少动作（我认为）。

我已经在网上搜索了一个带有空转换的示例，但我没有找到。

score 1 · Accepted Answer

如果您从增强语法开始，这不是冲突。

在初始状态下，没有可能的 shift 动作，只有一个 reduce 动作。因此必须无条件地执行 reduce 操作。

一旦减少 S，您最终会处于以下状态：

S' -> S . $
S  -> S . N
N  -> . nonterminal

这将移动输入结束标记或以下非终端。假设它是非终端，我们最终得到：

N  -> nonterminal .

这是另一个强制归约，它导致我们

S  -> S N .

然后我们回到：

S' -> . S $
S  -> . S N
S  -> .

但是，原始的未增广文法不是 LR(0)。（包含空字符串和其他一些字符串的语言都不能是 LR(0)。）

1 回答 1