LL(1)解析冲突

Question

我正在为一个非常简单的语法编写一个LL(1)解析器。然而，我在尝试构建解析表时发现了冲突。

我很惊讶，因为语法看起来很简单。我不知道是解析器有问题，还是我对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)。您的跟随集计算不正确，这很容易验证:不存在list或listPrime后跟EOF以外的令牌的派生。