3.5.7 广义线性方法

当我们构建一个确定性控制机制的试图失败,并留给我们非确定性的但是又几乎是确定性的机制时,我们还不需要感到绝望:我们可以回到广度优先搜索,在试验期间内解决留下的非确定性问题。我们原本的方法越好,遗留的不确定性就越少,需要用到广度优先搜索的就越少,那解析器的效率就越高。这种解析器被称为“广义解析器”;对大多数自底向上和自顶向下确定性方法,广义解析器已经设计出来了。在第11章中有介绍。广义LR(或GLR)(Tomita [162])是现今可用的最佳通用CF解析器之一。

当然,重新引入广度优先搜索是我们的一个冒险。语法和输入有可能会使每个输入中隐藏不确定性,这样会导致我们的解析器再次具有时间依赖性。然而在实践中,从来没有发生过这种情况,这样的解析器非常有用。