Re: Representations of grammars (Dennis Mickunas)
Tue, 29 Jun 1993 18:15:48 GMT

          From comp.compilers

Related articles
Representations of grammars (Kelly Morrison) (1993-06-25)
Re: Representations of grammars (1993-06-26)
Re: Representations of grammars (1993-06-28)
Re: Representations of grammars (1993-06-28)
Representations of grammars (Trevor Jenkins) (1993-06-28)
Re: Representations of grammars (1993-06-29)
Re: Representations of grammars (1993-06-29)
Re: Representations of grammars (1993-07-01)
Re: Representations of grammars (1993-07-01)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Dennis Mickunas)
Keywords: parse, bibliography
Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
References: 93-06-063 93-06-073
Date: Tue, 29 Jun 1993 18:15:48 GMT

> 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

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 (217) 333-6351

Post a followup to this message

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