Syntactic Dominoes was used to describe different parsing algorithms in a Compiling Techniques Course at Brunel University that ran from 1969 until 1985. the film was also made available to other UK universities.
The original idea came from Tom Cheatham at Computer Associates in 1968:
Syntactic Dominoes can be viewed as a game, not unlike the childrens game of dominoes, in which one has "syntactic" dominoes corresponding to the various syntax rules of the grammar as well as the symbols of the source text and the "goal" (or root of the analysis tree). The construction of the analysis tree can now be viewed as a game; the construction of the analysis tree corresponds to choosing and placing syntactic dominoes so as, in the end, to have all edges abutted. The various methods of syntactic analysis (i.e. various ways of constructing the analysis tree) can be viewed as strategies of play of the game.
We then develop "top-down", "left-corner-bottom-up" and "direct reductions" strategies of play; these strategies arc very easily comprehended and, when comprehended, ensure that the student really understands the basic mechanisms required for the three kinds of analysis. Following this we formalize the dominoes and the strategies as AMBIT/G data objects and programs; this has the very distinct advantage that the two-dimensional aspect (the representation of trees and so on) Is indirectly modelled.
ARPA Project 1228: RESEARCH IN MACHINE-INDEPENDENT SOFTWARE PROGRAMMING
A set of dominoes are created that correspond to the grammar rules for the language to be parsed.
At the top is the goal dominoe and at the bottom are a set of dominoes that represent the input to be parsed.
The game consists of adding dominoes to the board that match either the bottom of the goal or the top of the inputs. The pieces are elastic so that they can be made larger or smaller to fit. The aim is to complete the game with all the pieces being fully connected top and bottom. The film shows three different parsing strategies: top-down, bottom-up, and reduction analysis.
The film is aimed at getting the general principles understood before the individual parsing algorithms are described. See Chapter 7, Compiling Techniques.
