LL(1) 解析冲突

Question

我正在为一个非常简单的语法编写一个 LL(1) 解析器。然而，我在尝试构建解析 table.

时发现了冲突

我很惊讶，因为语法看起来很简单。我不知道是解析器有问题还是我对 LL(1) 解析的理解有问题。可能文法最后不是LL(1)

语法是：

1: S         -> begin list
2: list      -> id    listPrime
3: listPrime -> id    listPrime
4:            | ε

我的代码遇到了两个冲突，一个是推导 listPrime，一个是终端符号 id，另一个是 EOF。在这两种情况下，规则 3 都与规则 4 冲突。

我计算的 FIRST 和 FOLLOW 集是：

first:
   { S: Set { 'begin' },
     list: Set { 'id' },
     listPrime: Set { 'id', 'eps' } },

follow:
   { S: Set { 'EOF' },
     list: Set { 'EOF', 'id' },
     listPrime: Set { 'EOF', 'id' } } }

Answer 1

语法是 LL(1)。您的 FOLLOW 集计算不正确，这很容易验证：没有 list 或 listPrime 后跟 EOF.

以外的标记的推导

LL(1) 解析冲突

LL(1) parsing conflict

parsing

ll