3.4.5 4型语法

有限选择语法(FC)不包含生成树,并且对一个FC语法语言的一个给定输入字符串的成员关系可以由简单的查找来决定。这种查找方式通常不认为是“解析”,但仍然在这里提及有两个原因。第一,它可以受益于解析技术,第二,在解析环境中通常需要它。自然语言中有一些单词类别,只包含数量非常有限的成员;例如代词、介词和连词。通常快速的决定一个给定单词是否属于这些有限选择类别之一或者是需要在进一步的分析是至关重要的。这同样适用于编程语言中的保留字段。

一种方法是将FC语言作为正则语法来考虑,并应用第5章的技术。这通常是及其有效的。

另一个经常使用的方法是使用一个哈希表。见任何一本关于算法的书,例如Cormen et al. [415], 或者 Goodrich and Tamassia [416]。