NEWCAT: Parsing natural language using left-associative grammar (Q1085987)

The book presents a new approach to natural language (NL) parsing. It is based on a Left-Associative Grammar (LAG). The author sees in LAG a step towards dissolving a mystery of NL parsing. A system based on LAG analyzes a sentence from left to right. The notion of possible continuations is a fundamental one. The linguistic analysis of a left- associative parse (LAP) is a structured list which represents the history of the computation. Each history segment (there are n-1 history segments if the input sentence is n words long) characterizes the combination of a sentence start with a next word. The last combination of a successful LAP results in a sentence start without a next word. The linguistic content is encoded in rule packages, rules, and categories. It is obvious that a continuous text is analyzed by LAG like any other well formed string of NL. LAG is a substantial departure from contemporary linguistic analysis. The lack of substantial progress in NL parsing during the last 25 years the author attributes to the dominance of constituent structure analysis in theoretical and computational linguistics. LAG prefers the dependency grammar and the categorial grammar approaches to the phrase structure grammar approach. However, the two-dimensional hierarchical representation of sentences and defining dependency relations between individual words is abandoned. Dependencies are defined solely between the sentence start and the next word. The basic ideas of LAP were implemented in LISP. NEWCAT and DCAT are German parsers, ECAT an English parser and LOGCAT a parser for propositional logic. LAG is a general approach, applicable to different NL as well as to formal languages. The book contains 320 pages of appendices. By documenting LAG as completely as possible the author hopes to provide a solid foundation for future team efforts.