3.4.1 时间要求

当解析一个包含几个符号的字符串时，对于解析器的时间要求有些想法是很重要的，即解析输入字符串的一些符号的依赖项所需要的时间。预期的输入长度范围从上千万（自然语言种的句子）到数万（大型计算机程序）之间；一些输入字符串的长度甚至可能是几乎无限长的（一台咖啡售货机再其使用寿命之间的按钮按动序列）。输入长度的依赖项的时间要求也称为时间复杂度。

有几个特征属性让时间依赖项能被识别。一个时间依赖项是指数分布的，如果接下来的每一个输入符号所需的时间都乘以一个常量因子，也就是：每一个额外的输入符号需要双倍的解析时间。指数分布的时间依赖项被写作O(C ⁿ)，其中C是增加的常量因子。指数依赖关系，来自于著名的棋盘上每一个各自上的谷物数量都是前一个格子的两倍这个故事；这种方式意味着破产。

一个时间依赖项是线性分布的，如果接下来的每一个输入符号需要花费的处理时间有一个固定的增量；输入长度增加一倍则处理时间增加一倍。这种行为是我们希望在解析器中看到的；解析所需要的时间与读取输入所需的时间成正比。所谓的实时解析器表现的甚至更好：它们可以在读取完成最后一个符号的恒定的时间内生成解析树；如果计算机运行足够快速，它们能跟上以恒定速率输入的无限输入流。请注意，这不一定是真正的线性时间解析器；原则上它们可以读取有n个符号的完整字符串，然后花费与n成正比的时间来生成解析树。

线性时间依赖被写作O(n)。一个时间依赖项被称为二次曲线式的，如果处理时间与输入长度的平方成正比（写作O(n²)），以及立方式的如果与长度的三次方成正比（写作O(n³)）。总之，一个依赖项与n的任意次幂成正比则被称为多项式（写作O(n^p)）。