Título: | Direct parsing of ID/LP grammars |
Autores: | Shieber, Stuart |
Fecha: |
2008-08-22 1984 |
Publicador: | Springer |
Fuente: |
Ver documento |
Tipo: | Journal Article |
Tema: |
computer science natural-language processing computational linguistics |
Descripción: |
The Immediate Dominance/Linear Precedence (ID/LP) formalism is a recent
extension of Generalized Phrase Structure Grammar (GPSG) designed to
perform some of the tasks previously assigned to metarules--for example,
modeling the word-order characteristics of so-called free-word-order
languages. It allows a simple specification of classes of rules that
differ only in constituent order. ID/LP grammars (as well as metarule
grammars) have been proposed for use in parsing by expanding them into
equivalent context-free grammars. We develop a parsing algorithm, based
on the algorithm of Earley, for parsing ID/LP grammars directly,
circumventing the initial expansion phase. A proof of correctness is
supplied. We also discuss some aspects of the time complexity of the
algorithm and some formal properties associated with ID/LP grammars and
their relationship to context-free grammars. Engineering and Applied Sciences |
Idioma: | Inglés |
1 Synchronous grammars as tree transducers por Shieber, Stuart | 6 Ellipsis and higher-order unification por Pereira, Fernando C. N.,Dalrymple, Mary,Shieber, Stuart |
2 Automatic yellow-pages pagination and layout por Marks, Joe,Shieber, Stuart,Johari, Ramesh,Partovi, Ali | 7 Generation and synchronous tree-adjoining grammars por Shieber, Stuart,Schabes, Yves |
3 Evidence against the context-freeness of natural language por Shieber, Stuart | 8 The Research Library in the Digital Age por Darnton, Robert |
4 An algorithm for generating quantifier scopings por Hobbs, Jerry,Shieber, Stuart | 9 The Turing test as interactive proof por Shieber, Stuart |
5 Semantic-head-driven generation por Moore, Robert C.,Pereira, Fernando C. N.,van Noord, Gertjan,Shieber, Stuart | 10 Abbreviated text input using language modeling. por Shieber, Stuart,Nelken, Rani |