3.5.1 方向性

非定向性方法构建解析树，当以任何他们认为合适的顺序访问输入字符串时。当然这要求在解析之前，完整的输入字符串要存在内存之中。分别有自顶向下和自底向上两个版本。定向解析器会按照顺序一个接一个的访问输入字符串，持续访问直到更新完部分解析树。也有自顶向下和自底向上两个版本。

3.5.1.1 非定向方法

非定向性的自顶向下方法即简单又直接，可能已经被很多人独立发明出来了。据我们所知最早是Unger[12]在1968年提出的，但是在他的文章中的描述似乎这个方法当时已经存在了。这个方法在文献中一直不受重视，但却比人们所认为的要重要的多，因为它以不知名的方式被大量的解析器使用。我们应该称之为Unger方法；见4.1节。

非定向性的自底向上方法也被很多人独立发现，其中有Cocke (in Hays [3, Sect. 17.3.1]), Younger [10],和Kasami [13]；更早是Sakai [5]提出的。它是以三个最著名的发明家合称命名的CYK（或者说又是称为CYK）。它受到广泛的注意，因为其天生的执行性要比Unger方法更有效率。不过这两种方法的效率都还可以提升，达到大致相同的效果；见Sheil [20]。CYK方法将在4.2节中讲述。

非定向性方法通常首先构建一个数据结构，总结输入句子的语法结构。在第二阶段的时候，解析树就可以从这种数据结构中产生。

3.5.1.2 定向方法

定向方法一个符号一个符号的处理输入字符串，从左到右。（从右到左解析也是可能的，通过使用语法的镜像；这只是偶尔会有用）这样做的好处是，解析可以启动并且确实进行，在输入字符串的最后一个字符出现之前。定向方法全部都显示或隐式的基于解析自动机上，在3.4.3节中描述的，其中自顶向下方法执行预测和匹配，自底向上方法执行转换和缩减。

定向方法通常可以构建（部分）解析树，当它在处理输入字符串时，除非语法不明确或者需要一些后续处理。