compiler-construction - 这种语法在归约后的乔姆斯基分类是什么？我还是很困惑

Question

这是归约前的语法：

我的减少步骤是

1代

S -> 交流电

A -> bSca

C -> 广告

2-可达

S -> 交流电

C -> 广告

我仍然对这种语法的乔姆斯基分类感到困惑

标签： compiler-construction

Answer 1

关于乔姆斯基层次结构的维基百科文章提供了简单的定义。特别是，它说类型 2（无上下文）语法是：

由 A → α 形式的规则定义，其中 A 是非终结符，α 是一串终结符和/或非终结符。

和类型 3（常规）语法：

将其规则限制为左侧的单个非终结符和由单个终结符组成的右侧，可能后跟单个非终结符。

你的最终语法是：

S → aC
C → ad

严格来说，这不是第 3 类语法，因为 for 的产生C式不是“单个终结符后面可能跟着一个非终结符”；相反，它是一个单一的终端，然后是另一个单一的终端。但这可以简单地重写为

S → aC
C → aD
D → d

其中所有的产生式都服从第 3 类限制。这种简单的转换可以应用于任何包含一个或多个终端可能后跟一个非终端的产生式的语法，并且通常用作定义而不是维基百科中的定义，因为最终结果实际上是相同的.

我们可以看到，每个类型 3 文法也是一个类型 2 文法，因为类型 3 文法中允许的两个右手边也符合“一串终结符和/或非终结符”的描述。所以说你的最终文法是Type 2 并没有错，但是既然它也是Type 3，我们通常会把它描述为Type 3 文法。