1993 · 92 citations · 17 references
ComputingComputer ScienceAlgorithmsComputational LinguisticsSyntaxContext-free LanguagesGrammarParsingSyntactic ParsingSyntax AnalysisSyntax ParsingCocke-younger-kasami AlgorithmContext-free Grammar ParsingContext-free GrammarsGrammar FormalismsLanguage ParsingParsing AlgorithmsPolynomial-time AlgorithmsTree-adjoining Grammar
In this paper we present a scheme to extend a recognition algorithm for Context-Free Gram- mars (CFG) that can be used to derive polynomial-time recognition algorithms for a set of formalisms that generate a superset of languages generated by CFG. We describe the scheme by developing a Cocke-Kasami-Younger (CKY)-like pure bottom-up recognition algorithm for Linear Indexed Grammars and show how it can be adapted to give algorithms for Tree Adjoining Grammars and Combinatory Categorial Grammars. This is the only polynomial-time recognition algorithm for Combinatory Categorial Grammars that we are aware of. The main contribution of this paper is the general scheme we propose for parsing a variety of formalisms whose derivation process is controlled by an explicit or implicit stack. The ideas presented here can be suitably modified for other parsing styles or used in the generalized framework set out by Lang (1990).
17
Generalized Phrase Structure Grammar.
Scott Soames, Gerald Gazdar, Ewan Klein et al. · The Philosophical Review · 1989 · 1.8K citations
Aravind K. Joshi, Leon S. Levy, Masako Takahashi · Journal of Computer and System Sciences · 1975 · 774 citations
Indexed Grammars—An Extension of Context-Free Grammars
Alfred V. Aho · Journal of the ACM · 1968 · 441 citations · Full text