Using Restriction to Extend Parsing Algorithms for Complex-Feature-Based Formalisms
Using Restriction to Extend Parsing Algorithms for Complex-Feature-Based Formalisms
复制标题
使用限制来扩展基于复杂特征的形式主义的解析算法
DOI：
10.3115/981210.981228
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
Stuart M. Shieber
中科院分区：
文献类型：
--
作者：
Stuart M. Shieber
基于复值特征系统中语法信息编码的语法形式化在语言学和自然语言处理研究中都得到了广泛的应用。通过与上下文无关文法的类比，这种形式化可以被认为是将非终端符号的概念从原子元素的有限域推广到特定类型的有向图结构的可能无限域。不幸的是，在转向无限非终结域的过程中，标准的解析方法可能不再适用于形式主义。通常，问题本身表现为算法的严重低效甚至不终止。在这篇文章中，我们讨论了将解析算法扩展到可能具有无限非终止域的形式的问题的解决方案，该解决方案基于一种称为限制的通用技术。作为这种扩展的一个具体例子，我们给出了Earley算法的一个完整的、正确的、终止的扩展，它使用限制来执行自上而下的过滤。我们对该算法的实现演示了可以通过该技术实现的图表边缘的彻底消除。最后，我们描述了该技术的进一步用途-包括分析其他语法形式，包括定子句语法；扩展其他分析算法，包括LR方法和句法偏好建模算法；以及有效的索引。
Grammar formalisms based on the encoding of grammatical information in complex-valued feature systems enjoy some currency both in linguistics and natural-language-processing research. Such formalisms can be thought of by analogy to context-free grammars as generalizing the notion of nonterminal symbol from a finite domain of atomic elements to a possibly infinite domain of directed graph structures of a certain sort. Unfortunately, in moving to an infinite nonterminal domain, standard methods of parsing may no longer be applicable to the formalism. Typically, the problem manifests itself as gross inefficiency or even nontermination of the algorithms. In this paper, we discuss a solution to the problem of extending parsing algorithms to formalisms with possibly infinite nonterminal domains, a solution based on a general technique we call restriction. As a particular example of such an extension, we present a complete, correct, terminating extension of Earley's algorithm that uses restriction to perform top-down filtering. Our implementation of this algorithm demonstrates the drastic elimination of chart edges that can be achieved by this technique. Finally, we describe further uses for the technique---including parsing other grammar formalisms, including definite-clause grammars; extending other parsing algorithms, including LR methods and syntactic preference modeling algorithms; and efficient indexing.