Ling484 Examples

A. C. Brett acbrett@uvic.ca Department of Linguistics University of Victoria Clearihue C139

Production Systems

1. a Database;
2. a Production Set; and,
3. an Interpreter.

In these examples, Production Systems are applied to the problem of recognising, and parsing, sentences. If the recognition works bottom-up, the Database, in its Initial State, contains a string comprising a putative sentence; the Production Set is a collection of context- free rewriting rules defining the grammar of a language; and, the Prolog program itself is the Interpreter. The program applies rewriting rules from the Production Set to the string in the Database. The initial string in the Database is recognised as a sentence in the language defined by the grammar comprising the Production Set if, after no further rewriting rules can be applied, and the Interpreter halts, the Database contains only the root or axiom symbol of the grammar. The Database can then be said to represent an Accepting State of the Production System.

Production Systems thus perform a recognition in an intuitive fashion; that is, they apply Productions (rewriting rules) in the fashion in which we are accustomed to think of rewriting rules being used to determine whether or not a string is a sentence. Therefore, they represent an appealing starting point for an introduction to the study of grammar using computational methods and serve as a convenient and perspicuous device whereby to present some basic concepts and the associated lexicon. Production Systems also comprise a very general class of problem-solving mechanisms and are important in their own right, being used in conjunction with other recognition strategies and in other areas of computational linguistics, particularly in artificial intelligence studies. See Rosner (1983) for a discussion of Production Systems and their application to language analysis.

The following exampes also illustrate the bottom-up versus top-down and depth-first versus breadth-first taxonomy of recognition and parsing strategies. For background information on the psycholinguistic issues related to these strategies, see Frazier (1989) for a discussion of the arguments supporting the top-down, structurally-driven, or principle-based strategy. See Tyler (1989) for arguments supporting the position that the human processor pursues bottom-up, lexically-driven, or data-driven parsing strategy. An extensive review of the psychological data and competing models of the sentence analysis process appears in Mitchell (1994).

• Bottom-Up Processing.
  • Bottom-up, Breadth-first Recogniser. This program illustrates the application of a Production System to the problem of determining whether or not a string of words is a sentence by causing the Interpreter to pursue a bottom-up, breadth-first strategy.
  • Bottom-up, Depth-first Recogniser. This program illustrates a Production System that works depth-first to recognise or accept a sentence, rather than breadth-first as does the Production System Interpreter demonstrated in the previous example. Like the previous example, however, this program also works bottom-up.

• Top-Down Processing.
  • Top-down, Depth-first Recogniser. This example demonstrates a Production System that works top-down and depth-first to recognise a sentence. Thus, this program causes the Interpreter to pursue the same strategy as that which it follows in the case of Definite Clause Grammar implementations.
  • Top-down, Depth-first Parser. This example demonstrates a Production System that performs top-down, depth-first parse of a sentence.
  • Top-down, Breadth-first Parser. This program illustrates a Production System that performs top-down, breadth-first parse of a sentence. The purpose of this example, however, is to demonstrate the parsing of structurally ambiguous sentences. The sentence used in this demonstration is one of the "buffalo sentences" described by Barton et al. (1987:99-100).

• Multiple Analyses.
  • Top-down, Depth-first Parser. This program illustrates a Production System that performs top-down, depth-first parser that yields multiple analyses of structurally ambiguous sentences by a somewhat inelegant and inefficient strategy. This example uses one of the sentences employed by Kay (1980) to demonstrate the chart parsing strategy whereby all analyses of an ambiguous sentence can be obtained in a systematic and efficient fashion.

Linguistics 484

Examples Index

Top of Page