3.3.2 构建控制机制

构建一个解析器的控制机制是一件相当不同的事情。一些控制机制是独立于语法的,一些定期从语法中查询,一些使用语法预计算的巨大的表格,还有一些甚至使用输入字符串计算的表格。我们应该看到这些的单独的例子:这部分开头就表明的“手动控制”,属于“定期从语法中查询”的类别,回溯解析器通常使用语法独立控制,LL和LR解析器使用语法派生的预计算的表格,CYK解析器使用输入字符串派生的表格,以及Early和GLR解析器使用少数的几个由语法和输入字符串派生的表格。

从语法中构建控制机制,包括表,几乎都是由程序完成的。这种程序被称为解析器生成器;这足够了,语法和也许是终结符号的描述,并且生成一个程序就是解析器。解析器通常由一个驱动和一个或多个表组成,这种情况下被称为表驱动。其中的表可以是具有相当规模并且及其复杂的。

由输入字符串派生的表必须被解析器的一个例行程序计算。应该指出的是,这反映了典型配置,大量不同的输入字符串被根据同一个相对静止不变的语法解析。反面例子是很容易想象的:许多语法被用来试图解释一个给定的输入字符串,例如事件的一个观测序列。