为什么我在构造LL(1) table时得到的结果与龙书不同？

Question

第 224 页，算法 4.31。

构造LL(1)的方法table说：

For each production A -> alpha of the grammar, do the following.

For each terminal a in FIRST(A), add A -> alpha to M[A, a].

If eps is in FIRST(alpha), then for each terminal b in FOLLOW(A) add A -> alpha to M[A, b]. If eps is in FIRST(alpha) and $ is in FOLLOW(A), add A -> alpha to M[A, $] as well.

他们给出了以下语法和 table.

(1)  E  ->  T  E'
(2)  E' ->  +  T E'
(3)  E' ->  eps
(4)  T  ->   F  T'
(5)  T' ->  *  F  T'
(6)  T' ->  eps
(7)  F  ->  (  E  )
(8)  F  ->  id

   | id    +    *    (    )    $
---+-----------------------------
E  | 1               1
E' |       2              3    3
T  | 4               4
T' |       6    5         6    6      
F  | 8               7

供参考，有FIRST/FOLLOW组；摘自本书。

     FIRST    FOLLOW
E    ( id     ) $
E'   + eps    ) $
T    ( id     + ) $
T'   * eps    + ) $
F    ( id     + * ) $

当我运行算法（手动和使用我根据本书编写的实现）时，我得到以下结果。

   | id    +    *    (    )    $
---+-----------------------------
E  | 1               1
E' |       2|3            3    3
T  | 4               4
T' |       5|6  5         6    6      
F  | 7|8             7|8

不同的是我有一些书中避免的冲突。

这是我的工作，通过算法。前两步显然与他们相同，但我们在第三步分道扬镳。我的 table 中的其他冲突也是出于同样的原因出现的。

生产`(1) E -> T E'`

对于FIRST(E) = { (, id }中的每个终端x，将(1)添加到M[E, x]。

   | id    +    *    (    )    $
---+-----------------------------
E  | 1               1
E' |
T  |
T' |
F  |

如果 eps 在 FIRST(T E') = { (, id }... 它不是。

生产`(2) E' -> + T E'`

对于FIRST(E') = { +, eps }中的每个终端x，将(2)添加到M[E', x]。

   | id    +    *    (    )    $
---+-----------------------------
E  | 1               1
E' |       2
T  |
T' |
F  |

如果 eps 在 FIRST(+ T E') = { + }... 它不是。

生产`(3) E' -> eps`

对于FIRST(E') = { +, eps }中的每个终端x，将(3)添加到M[E', x]。

   | id    +    *    (    )    $
---+-----------------------------
E  | 1               1
E' |       2|3
T  |
T' |
F  |

冲突就在这里。

书上说：

Since FOLLOW(E') = { ), $ }, production (3) E' -> eps is added to M[E', )] and M[E', $].

我们同意这一点：这也是我下一步要做的。但在此之前，第一步说：

For each terminal a in FIRST(A), add A -> alpha to M[A, a].

应用到这个规则，FIRST(E')就是{ +, eps }。所以 M[E', +] 应该得到 (3) E' -> eps.

您可以在接下来的两行中看到相同的图案。在最后一行，产生式 (7) F -> ( E ) 和 (8) F -> id 都将具有相同的 FIRST(F) = { (, id }，因此 M[F, id] 和 M[F, (] 都将得到 (7)和 (8).

书中给出的算法隐含了什么我遗漏了？

此外，这是我的实施所提供内容的日志。我手工做算法的时候也是这个道理，所以请不要索要代码。我在寻找算法解释中的错误，而不是实现中的错误。

#########
## Log ##
#########
Looking at rule Expression -> Term Expression_.
  Adding "Expression -> Term Expression_" to M[Expression, OpenParen] due to step 1.
  Adding "Expression -> Term Expression_" to M[Expression, Identifier] due to step 1.
Looking at rule Expression_ -> Plus Term Expression_.
  Adding "Expression_ -> Plus Term Expression_" to M[Expression_, Plus] due to step 1.
Looking at rule Expression_ -> ε.
  Adding "Expression_ -> ε" to M[Expression_, Plus] due to step 1.
  Adding "Expression_ -> ε" to M[Expression_, CloseParen] due to step 2a.
  Adding "Expression_ -> ε" to M[Expression_, $] due to step 2b.
Looking at rule Term -> Factor Term_.
  Adding "Term -> Factor Term_" to M[Term, OpenParen] due to step 1.
  Adding "Term -> Factor Term_" to M[Term, Identifier] due to step 1.
Looking at rule Term_ -> Times Factor Term_.
  Adding "Term_ -> Times Factor Term_" to M[Term_, Times] due to step 1.
Looking at rule Term_ -> ε.
  Adding "Term_ -> ε" to M[Term_, Times] due to step 1.
  Adding "Term_ -> ε" to M[Term_, Plus] due to step 2a.
  Adding "Term_ -> ε" to M[Term_, CloseParen] due to step 2a.
  Adding "Term_ -> ε" to M[Term_, $] due to step 2b.
Looking at rule Factor -> OpenParen Expression CloseParen.
  Adding "Factor -> OpenParen Expression CloseParen" to M[Factor, OpenParen] due to step 1.
  Adding "Factor -> OpenParen Expression CloseParen" to M[Factor, Identifier] due to step 1.
Looking at rule Factor -> Identifier.
  Adding "Factor -> Identifier" to M[Factor, OpenParen] due to step 1.
  Adding "Factor -> Identifier" to M[Factor, Identifier] due to step 1.


#################
## Final table ##
#################
Expression + OpenParen => { Expression -> Term Expression_ }
Expression + Identifier => { Expression -> Term Expression_ }
Expression_ + Plus => { Expression_ -> Plus Term Expression_ , Expression_ -> ε }
Expression_ + CloseParen => { Expression_ -> ε }
Expression_ + Symbol($) => { Expression_ -> ε }
Term + OpenParen => { Term -> Factor Term_ }
Term + Identifier => { Term -> Factor Term_ }
Term_ + Times => { Term_ -> Times Factor Term_ , Term_ -> ε }
Term_ + Plus => { Term_ -> ε }
Term_ + CloseParen => { Term_ -> ε }
Term_ + Symbol($) => { Term_ -> ε }
Factor + OpenParen => { Factor -> OpenParen Expression CloseParen , Factor -> Identifier }
Factor + Identifier => { Factor -> OpenParen Expression CloseParen , Factor -> Identifier }

Answer 1

这看起来像是书中的错误。

For each terminal a in FIRST(A), add A -> alpha to M[A, a].

应该是 FIRST(alpha)，而不是 FIRST(A)。事实上，如果你看到 F -> (E)，你需要将这条规则添加到 M[F, '(']，如果你看到 F -> id，则将这条规则添加到 M[F,id]。它使 no将这两个规则添加到两个状态是有意义的。

这里是书上固定的算法（重点是改动的部分）：

For each production A -> alpha of the grammar, do the following.

For each terminal a in FIRST(alpha), add A -> alpha to M[A, a].

If eps is in FIRST(alpha), then for each terminal b in FOLLOW(A) add A -> alpha to M[A, b]. If eps is in FIRST(alpha) and $ is in FOLLOW(A), add A -> alpha to M[A, $] as well.

这是创建 table 的正确顺序：

Looking at rule Expression -> Term Expression_.
  Adding "Expression -> Term Expression_" to M[Expression, OpenParen] due to step 1.
  Adding "Expression -> Term Expression_" to M[Expression, Identifier] due to step 1.
Looking at rule Expression_ -> Plus Term Expression_.
  Adding "Expression_ -> Plus Term Expression_" to M[Expression_, Plus] due to step 1.
Looking at rule Expression_ -> ε.
  Adding "Expression_ -> ε" to M[Expression_, CloseParen] due to step 2a.
  Adding "Expression_ -> ε" to M[Expression_, $] due to step 2b.
Looking at rule Term -> Factor Term_.
  Adding "Term -> Factor Term_" to M[Term, OpenParen] due to step 1.
  Adding "Term -> Factor Term_" to M[Term, Identifier] due to step 1.
Looking at rule Term_ -> Times Factor Term_.
  Adding "Term_ -> Times Factor Term_" to M[Term_, Times] due to step 1.
Looking at rule Term_ -> ε.
  Adding "Term_ -> ε" to M[Term_, Plus] due to step 2a.
  Adding "Term_ -> ε" to M[Term_, CloseParen] due to step 2a.
  Adding "Term_ -> ε" to M[Term_, $] due to step 2b.
Looking at rule Factor -> OpenParen Expression CloseParen.
  Adding "Factor -> OpenParen Expression CloseParen" to M[Factor, OpenParen] due to step 1.
Looking at rule Factor -> Identifier.
  Adding "Factor -> Identifier" to M[Factor, Identifier] due to step 1.

为什么我在构造LL(1) table时得到的结果与龙书不同？

Why am I getting different results from the Dragon Book when constructing LL(1) table?

algorithm

parsing

ll

生产`(1) E -> T E'`

生产`(2) E' -> + T E'`

生产`(3) E' -> eps`

为什么我在构造LL(1) table时得到的结果与龙书不同？

Why am I getting different results from the Dragon Book when constructing LL(1) table?

algorithm

parsing

ll

生产(1) E -> T E'

生产(2) E' -> + T E'

生产(3) E' -> eps

生产`(1) E -> T E'`

生产`(2) E' -> + T E'`

生产`(3) E' -> eps`