Re: Representations of grammars

> I am trying to compose a list of representations (both textual and
>graphical) of grammars. So far, the only ones I have been able to find are:
>
>1. Backus-Naur Form (also Backus Normal Form).
> - created by John Backus; modified by Peter Naur.
>2. The Cobol Notation.
> - created by the CODASYL Short-Range Subcommittee.
>3. Syntax Diagrams.
> - created by Niklaus Wirth (?).


An early version of Pascal-ish syntax diagrams was used by Huskey, Love,
and Wirth in [1]. These "syntax charts" were introduced by Taylor,
Turner, and Waychoff in 1961 [2]. Syntax charts were a direct
transliteration of (recursive) BNF descriptions; I don't think that they
employed the iterative "loops" that you find in the Pascal diagrams.


However, at about the same time, Glennie devised a version of syntax
charts which could be used to build a top-down parser from BNF definitions
[3]. Glennie's tech report is probably impossible to find (and I think
that's the reason Glennie fails to receive much credit), but you can see a
use of "Glennie Recognizers" in a paper by Kanner, Kosinski, and Robinson
[4].


Other representations that you'll want to examine are: Conway's "separable
transition diagrams" [5]; Vere's "translation equations" [6], and; Cohen
and Gotlieb's "syntax graphs" [7]. Cohen and Gotlieb begin with recursive
syntax charts, and perform a number of transformations, yielding
Pascal-ish syntax diagrams with iterative looping.


[1] Huskey, H.D., R. Love, and N. Wirth, "A syntactic description of
BC NELIAC," _CACM 6_ (July, 1963).


[2] Taylor, W., L. Turner, and R. Waychoff, "A syntactical chart of
Algol 60," _CACM 4_ (September, 1961).


[3] Glennie, A.E., "On the syntax machine and the construction of a
universal compiler," Tech. Rep. No. 2, Computation Center,
Carnegie Institute of Technology (July, 1960).


[4] Kanner, H., P. Kosinski, and C.L. Robinson, "The structure of
yet another Algol compiler," _CACM 8_ (July, 1965).


[5] Conway, M.E., "Design of a separable transition-diagram
compiler," _CACM 6_ (July, 1963).


[6] Vere, S., "Translation equations," _CACM 13_ (February, 1970).


[7] Cohen, D.J. and C.C. Gotlieb, "A list structure form of grammars
for syntactic analysis," _Computing Surveys 2_ (March, 1970).
--
M. Dennis Mickunas
Department of Computer Science 1304 W. Springfield Ave.
University of Illinois Urbana, Illinois 61801
mickunas@cs.uiuc.edu (217) 333-6351
--

Return to the comp.compilers page.
Search the comp.compilers archives again.