Production rule systems

Rewrite grammars

A grammar implemented as a set of rules which apply turn by turn to convert (or rewrite) progressively a string of symbols - taking, the string [s] to the string [my dog likes the hairy cat], for example - is at heart a special case of a type of system which workers in artificial intelligence know as a production rule system.

A production rule system comprises a working memory and a set of rules (productions) which form the production memory. All rules have a simple condition-action form:

IF state of working memory is like this THEN do this action

The system runs by making successive passes through the set of rules. A rule becomes potentially applicable if the working memory meets the condition(s) expressed by the first part of the rule. It may turn out that on a particular pass through the rules, a number of rules are applicable in this sense. In that case, a selection procedure is invoked to determine which rule actually 'fires', since only one rule may 'fire' on one pass. After a rule has fired, another pass through the entire rule set is made. When a pass through the rules shows none to be applicable, or when some explicit end point is signalled, the system halts.

A production system grammar

Rethinking our sentence generator in production system terms is straightforward. The working memory will be very simple. It will consist at any one time of a single list or string of sentence constituents. On each cycle it represents the current structure of the developing sentence, one step in its derivational history. Initially the working memory will be set up as a string containing the one element [s]. At the end of a run when the system halts it may contain the string [my dog likes the hairy cat].

The rules we previously implemented with make can readily be interpreted as abbreviated versions of productions. Ignoring make, they have effectively two important parts. A category and a list of possible expansions of that category. In production system terms these two parts correspond to the condition and the action components of a rule. Together they can be interpreted to mean:

IF the working memory contains this constituent THEN replace the constituent in the working memory by a randomly chosen element from this substitution list

In the course of deriving a sentence, it will frequently happen that more than one rule is applicable to a string - e.g. the string [np vp] could be altered by a production expanding np or one expanding vp. What selection criteria should be adopted? The progress of category expansion in our original system was determined by the order of the elements of the string as they are met traversing it from left to right. The directly equivalent criterion for rule selection would obviously be to choose the production which expands the element in working memory nearest the left. However, in a system based on making a series of passes through a list of rules, a different possibility is more easily implemented. We can simply allow the order of the rules to determine which rule fires. The processing algorithm would thus involve passing through the rules until one is met which is applicable. When that rule has fired, the set of rules is passed through again from the beginning. Such an algorithm will obviously provide a different history for the development of a sentence from our original version but there are no consequences for the structures finally output because the effect of the rules is not determined by the ordering. It is, however, worth noticing that in this approach , in order to determine if the condition part of the rule is met, it is still necessary to scan the contents of working memory as each rule is encountered . If this scan is made from left to right through the string [np vp np] it will consequently be the leftmost np which ensures the satisfaction of a condition requiring the presence of an np. More importantly, though coincidentally, the version of replace which we will use directly from the toolbox also tracks from left to right through a list and only replaces the first occurrence of old.item by new.item. The progress of the derivation is on closer examination thus going to be determined both by the order of the rules and the order of the constituents in the emerging structure.

Components of the system

The components of the system of the Logo implementation of the system are described in a serties of pages which can be selected separately from the list below. The Logo procedures in plain text form, ready to be loaded into your workspace, appeart at the end of this list.

  1. The production memory (i.e. the grammar rules)
  2. An interpreter which uses the production memory to generate a sentence
  3. An interpreter which uses the production memory to parse a sentence
  4. A couple of add on utilities to improve the interface
  5. Plain text version of Logo procedures
  6. And finally, a more versatile production system allowing more actions than simply replacement of constituents by randomly selected substitutions.

Ron Brasington
Department of Linguistic Science
The University of Reading