Catalogue of Artificial Intelligence Techniques
Keywords: Non-determinism, condition-action pairs, parsing, stack and buffer parsing
Categories: Natural Language
Author(s): Henry Thompson
Non-determinism arises in a parsing process which proceeds on a word by word or constituent by constituent basis because of (often local) ambiguity in the grammar and lexicon. The degree of non-determinism can therefore be reduced by expanding the focus of attention to include more than just the `next' constituent or word. Marcus has recently generated considerable interest with the claim that a small expansion of this sort allows English to be parsed deterministically in all but a few cases and in those it is claimed that people have difficulty as well. Marcus and others pursuing this approach employ a stack and buffer parsing technique, in which words (and sometimes completed constituents) are accessed through a fixed length (typically 3 or 5 items) buffer, and partially completed constituents are held in a stack. Grammar rules are represented by condition-action pairs, where the conditions refer to the buffer and the stack, and the actions effect changes therein. Rules are grouped together for the purpose of activation and deactivation--only some groups of rules are active at any given time. Strict determinism is ensured by the finiteness of the buffer and by requiring that all structures constructed at any point in the analysis must figure in the final result. It is an open question `how much' of English, or other natural languages, can be analysed with grammars which can be parsed in this fashion.
- Marcus, M., A theory of syntactic recognition for natural language
, MIT Press, Cambridge, Mass., 1980.