A Tabulation-Based Parsing Method that Reduces Copying
A Tabulation-Based Parsing Method that Reduces Copying
复制标题
一种减少复制的基于表格的解析方法
DOI：
10.3115/1075096.1075122
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Cosmin Munteanu
中科院分区：
文献类型：
--
作者：
Gerald Penn;Cosmin Munteanu
本文提出了一种新的自底向上的Prolog图分析算法，沿着与编译过程，减少了在运行时的复制量为一个常数（2）每边。它的应用程序，以统一为基础的语法非常大的偏序类别，其中复制是昂贵的，并可以方便地使用更复杂的索引策略检索这些类别，否则可能会被淹没的成本，这样的复制。它还提供了一个关于“快速检查”和相关知识的新视角，这似乎证实了迫使早期失败（而不是寻求早期成功的保证）实际上是最好的方法。还提供了其性能的初步经验评价。
This paper presents a new bottom-up chart parsing algorithm for Prolog along with a compilation procedure that reduces the amount of copying at run-time to a constant number (2) per edge. It has applications to unification-based grammars with very large partially ordered categories, in which copying is expensive, and can facilitate the use of more sophisticated indexing strategies for retrieving such categories that may otherwise be overwhelmed by the cost of such copying. It also provides a new perspective on "quick-checking" and related heuristics, which seems to confirm that forcing an early failure (as opposed to seeking an early guarantee of success) is in fact the best approach to use. A preliminary empirical evaluation of its performance is also provided.