编译原理问题解答文法

Question

已知文法G(S):S→aS|bS|c
(1)列出这个文法的所有LR(0)项目
(2)计算项目集规范族并构造识别活前缀的D
（3）构造LR(0)分析表。

Answer 1

(1) LR(0) 项目是指形如 [A → α·β] 的项，其中 A 是文法符号，α 和 β 是文法串。在这个文法 G(S): S → aS | bS | c 中，我们有以下的 LR(0) 项目：

I0:
[S' → ·S]
[S → ·aS]
[S → ·bS]
[S → ·c]

I1:
[S' → S·]

I2:
[S → a·S]
[S → ·aS]
[S → ·bS]
[S → ·c]

I3:
[S → b·S]
[S → ·aS]
[S → ·bS]
[S → ·c]

I4:
[S → c·]
[S → ·aS]
[S → ·bS]
[S → ·c]

(2) 接下来，我们需要构造这个文法的 LR(0) 项集规范族，并且基于这个规范族构造 DFA。构造项集规范族的过程如下：

I0:
[S' → ·S]
[S → ·aS]
[S → ·bS]
[S → ·c]

I1:
[S' → S·]

I2:
[S → a·S]
[S → ·aS]
[S → ·bS]
[S → ·c]

I3:
[S → b·S]
[S → ·aS]
[S → ·bS]
[S → ·c]

I4:
[S → c·]
[S → ·aS]
[S → ·bS]
[S → ·c]

I5:
[S → aS·]
[S → ·aS]
[S → ·bS]
[S → ·c]

I6:
[S → bS·]
[S → ·aS]
[S → ·bS]
[S → ·c]

I7:
[S → aS·]
[S → ·aS]
[S → ·bS]
[S → ·c]

I8:
[S → bS·]
[S → ·aS]
[S → ·bS]
[S → ·c]

I9:
[S → c·]
[S → aS·]
[S → ·aS]
[S → bS·]
[S → ·bS]
[S → ·c]

I10:
[S → aS·]
[S → ·aS]
[S → ·bS]
[S → ·c]

I11:
[S → bS·]
[S → ·aS]
[S → ·bS]
[S → ·c]

I12:
[S → aS·]
[S → ·aS]
[S → ·bS]
[S → ·c]

I13:
[S → bS·]
[S → ·aS]
[S → ·bS]
[S → ·c]

I14:
[S → c·]
[S → aS·]
[S → ·aS]
[S → bS·]
[S → ·bS]
[S → ·c]

在这里，我们可以使用以下的 DFA 来识别输入的活前缀：

   +---a--+               +---b--+
   |      |               |      |
   v      v               v      v
=>(I0)---a-->(I2)---a--->(I5)---ε-->(I10)*
   |                |             |
   b                b             c
   |                |             |
   v                v             v
  (I3)             (I6)          (I4)*
   |                |             |
   a                a             a