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节中描述的,其中自顶向下方法执行预测和匹配,自底向上方法执行转换和缩减。

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

results matching ""

    No results matching ""