RECOGNITION CAN BE HARDER THAN PARSING
RECOGNITION CAN BE HARDER THAN PARSING
复制标题
识别比解析更难
DOI：
10.1111/j.1467-8640.1994.tb00011.x
复制
发表时间：
1994
影响因子：
2.8
通讯作者：
B. Lang
中科院分区：
文献类型：
--
作者：
B. Lang
这里提出的工作试图提出一些基本概念，一些已知的解析算法，通常被称为图表或动态编程解析器，在指导设计类似的算法，可以被认为是描述语言的“表面”语法的其他形式主义的希望。关键思想是，图表解析本质上等价于语言（由其语法表示）与仅包含要解析的输入句子（由有限状态机表示）的正则集的交集的简单构造。这个交集的结果语法就是通常所说的共享森林：它代表了一个语法上有歧义的句子的所有解析。由于大多数处理病态输入的技术都可以通过考虑输入句子的非单例正则集来建模，因此我们可以期望将这些病态输入处理技术推广到所有可以用我们的方法描述的解析器。
The work presented here attempts to bring out some fundamental concepts that underlie some known parsing algorithms, usually called chart or dynamic programming parsers, in the hope of guiding the design of similar algorithms for other formalisms that could be considered for describing the “surface” syntax of languages. The key idea is that chart parsing is essentially equivalent to a simple construction of the intersection of the language (represented by its grammar) with a regular set containing only the input sentence to be parsed (represented by a finite state machine). The resulting grammar for that intersection is precisely what is usually called a shared forest: it represents all parses of a syntactically ambiguous sentence. Since most techniques for processing ill‐formed input can be modeled by considering a nonsingleton regular set of input sentences, we can expect to generalize these ill‐formed input processing techniques to all parsers describable with our approach.