2.3.4 4型语法

我们现在应该谈到的在生成规则中的最后一条限制是:右侧不允许出现非终结符。这从机制上移除了所有的生成力,除了被选中的可选项。起始符号有一列(有限的)可选项,我们所允许的;这个在名称中有所展现,有限选项语法(FC语法)。

对语言t,d&h是没有FC语法的;然而,如果我们愿意将其限制在数量有限(例如不超过一百长度)的名字列表中,那就可以有一个FC语法了,因为可以枚举所有的组合。对于这显然在限制内的三个名字,我们就有了:

Ss ---> [tdh] | [tdh] & [tdh] | [tdh] , [tdh] & [tdh]

以上总计 3+3×3+3×3×3 = 39 条生成规则。

FC语法不是官方Chomsky层次结构的一部分,因为这不是Chomsky定义的。不过它们仍然非常有用,而且常在一些处理或推理中被要求使用。可以用FC语法来描述编程语言中的保留字段集(关键字)。虽然不是很多语法完全是FC,不过很多语法的一些规则是有限选项的。例如,我们第一个语法的第一条规则(图Fig 2.3)就是FC。另一个FC规则的例子是2.3.3节中介绍的宏。我们不需要宏机制,如果我们这样改改:

zero or more terminals

上述正则语法定义改为:

zero or more terminals or FC non-terminals

最后,FC非终结符只会引入有限的终结符。