Michael B. Kashket
ABSTRACT
Free-word order languages have long posed significant problems for standard parsing algorithms. This paper reports on an implemented parser, based on Government-Binding theory (GB) (Chomsky, 1981, 1982), for a particular free-word order language, Warlpiri, an aboriginal language of central Australia. The parser is explicitly designed to transparently mirror the principles of GB.The operation of this parsing system is quite different in character from that of a rule-based parsing system, e.g., a context-free parsing method. In this system, phrases are constructed via principles of selection, case-marking, case-assignment, and argument-linking, rather than by phrasal rules.The output of the parser for a sample Warlpiri sentence of four words in length is given. The parser was executed on each of the 23 other permutations of the sentence, and it output equivalent parses, thereby demonstrating its ability to correctly handle the highly scrambled sentences found in Warlpiri.
- Barton, G. Edward (1985). "The Computational Complexity of Two-level Morphology," A. I. Memo 856, Cambridge, MA: Massachusetts Institute of Technology.Google Scholar
- Chomsky, Noam (1981). Lectures on Government and Binding, the Pisa Lectures, Dordrecht, Holland: Foris Publications.Google Scholar
- Chomsky, Noam (1982). Some Concepts and Consequences of the Theory of Government and Binding, Cambridge, MA: MIT Press.Google Scholar
- Hale, Ken (1983). "Warlpiri and the Grammar of Non-configurational Languages," Natural Language and Linguistic Theory, pp. 5--47.Google Scholar
- Johnson, Mark (1985). "Parsing with Discontinuous Constituents," 23rd Annual Proceedings of the Association for Computational Linguistics, pp. 127--32. Google ScholarDigital Library
- Laughren, Mary (1978). "Directional Terminology in Warlpiri, a Central Australian Language," Working Papers in Language and Linguistics, Volume 8, pp. 1--16.Google Scholar
- Nash, David (1980). "Topics in Warlpiri Grammar," Ph.D. Thesis, M.I.T. Department of Linguistics and Philosophy.Google Scholar
- Parsing a free-word order language: warlpiri
Recommendations
LR(k)-parsing of Coupled-Context-Free Grammars
COLING '94: Proceedings of the 15th conference on Computational linguistics - Volume 1Coupled-Context-Free Grammars are a generalization of context-free grammars obtained by combining nonterminals to parentheses which can only be substituted simultaneously. Referring to the generative capacity of the grammars we obtain an infinite ...
LLLR parsing
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied ComputingThe idea of an LLLR parsing is presented. An LLLR(k) parser can be constructed for any LR(k) grammar but it produces the left parse of the input string in linear time (in respect to the length of the derivation) without backtracking. If used as a basis ...
An efficient augmented-context-free parsing algorithm
An efficient parsing algorithm for augmented context-free grammars is introduced, and its application to on-line natural language interfaces discussed. The algorithm is a generalized LR parsing algorithm, which precomputes an LR shift-reduce parsing ...
Comments