Augmented Syntax Diagram

Augmented Syntax Diagram (ASD) Grammars

Augmented Syntax Diagram home page

Augmented Syntax Diagrams (abbreviated ASD) are a cross between Augmented Transition Networks (ATNs) [Woods, 1970; Bates, 1978] and syntax diagrams [Goldberg & Robson, 1983; Jensen & Wirth, 1975]. 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.

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

1. ASD networks have node labels but no edge labels. In contrast, ATN networks require both node (state) labels and edge (arc) labels. The node labels of an ASD grammar correspond to the edge labels of an ATN.

2. ASD networks are designed for bottom-up parsing; ATN networks are more suitable for top-down parsing.

3. ASD networks have null or dummy nodes as the counterpart to JUMP arcs in ATN grammars. Both match empty strings in the utterance being parsed.

4. ASD networks require only three kinds of node labels: (1) terminal vocabulary elements, (2) non-terminal vocabulary elements which represent phrase types, and (3) a special symbol, $$, to represent dummy nodes. Instance numbers in node labels distinguish between different nodes that are labeled with the same vocabulary element. In contrast, ATN networks require five kinds of arc labels: (1) PUSH arcs, (2) CAT arcs, (3) WORD arcs, (4) JUMP arcs, and (5) POP arcs, in addition to node labels.

5. ASD networks can be represented in non-graphical form by a single lexicon containing both terminal and non-terminal vocabulary elements. In contrast, ATN networks require a representation for the grammar that is separate from the lexicon.

References

1. Bates, M., The theory and practice of augmented transition network grammars. In Natural Language Communication with Computers, L. Bolc, Ed., Springer-Verlag, 1978, pp. 191-259.

2. Goldberg, A. and Robson, D., Smalltalk-80: The Language and its Implementation, Addison-Wesley, 1983.

3. Jensen, K. and Wirth, N., Pascal User Manual and Report (2nd Edition), Springer-Verlag, 1975.

4. Woods, W.A., Transition network grammars for natural language analysis, Communications of the ACM 13:10 (Oct. 1970), pp. 591-606.