Augmented Syntax Diagram Grammars

James A. Mason

Professor Emeritus of Computer Science
York University

I have coined the term "Augmented Syntax Diagram" (abbreviated ASD) to describe a cross between Augmented Transition Networks (ATNs) [Woods, 1970; Bates, 1978], which have been used to represent grammars of natural languages such as English, and syntax diagrams which have been used to represent grammars of programming languages [Goldberg & Robson, 1983; Jensen & Wirth, 1975; Wikipedia article "Syntax Diagram"]. While ASD grammars are equally as powerful as ATNs, they are conceptually simpler. They involve fewer primitives, and they permit a grammar to be combined with the lexicon of a language, rather than being represented as a structure separate from the lexicon. They can represent any context-free grammar, and in addition they can be augmented like ATNs with arbitrary computational tests and actions which are to be performed as utterances are parsed.

Figure 1 shows part of an ATN grammar and Figure 2 shows its ASD equivalent. In both cases only the networks are shown, not the augmentations. In both kinds of network, initial nodes are shown with bold outlines. S stands for "Sentence", NP for "Noun Phrase", VP for "Verb Phrase", PP for "Prepositional Phrase", DET for "Determiner", and ADJ for "Adjective".

ATN grammar example

Figure 1

ASD grammar example

Figure 2

Both of the figures are incomplete in that they involve non-terminal vocabulary elements PP and VP which represent phrase types, but they do not show the grammar networks for recognizing those phrase types. Those parts of the grammar networks have been omitted here for brevity.

The following are some of the main differences between ASD grammars and ATN grammars:

I have implemented efficient ASD parsers in several programming languages, including Java, LISP and Smalltalk. I have also implemented graphical editors for ASD grammars which run in Java, and in Smalltalk/V or Visual Smalltalk under Microsoft Windows. I also have examples of ASD grammars for parts of the English language, as well as examples of small applications involving English-language understanding which I have implemented with ASD grammars.


Click here to go to ASD home page.

created 1996 Aug 30
last revised 2011 Jan 1