|Representations of grammars email@example.com (Kelly Morrison) (1993-06-25)|
|Re: Representations of grammars firstname.lastname@example.org (1993-06-26)|
|Re: Representations of grammars P.G.Hamer@bnr.co.uk (1993-06-28)|
|Re: Representations of grammars email@example.com (1993-06-28)|
|Representations of grammars firstname.lastname@example.org (Trevor Jenkins) (1993-06-28)|
|Re: Representations of grammars email@example.com (1993-06-29)|
|Re: Representations of grammars firstname.lastname@example.org (1993-06-29)|
|Re: Representations of grammars email@example.com (1993-07-01)|
|Re: Representations of grammars firstname.lastname@example.org (1993-07-01)|
|From:||email@example.com (Dennis Mickunas)|
|Organization:||University of Illinois, Dept. of Comp. Sci., Urbana, IL|
|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 . These "syntax charts" were introduced by Taylor,
Turner, and Waychoff in 1961 . 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
. 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" ; Vere's "translation equations" , and; Cohen
and Gotlieb's "syntax graphs" . Cohen and Gotlieb begin with recursive
syntax charts, and perform a number of transformations, yielding
Pascal-ish syntax diagrams with iterative looping.
 Huskey, H.D., R. Love, and N. Wirth, "A syntactic description of
BC NELIAC," _CACM 6_ (July, 1963).
 Taylor, W., L. Turner, and R. Waychoff, "A syntactical chart of
Algol 60," _CACM 4_ (September, 1961).
 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).
 Kanner, H., P. Kosinski, and C.L. Robinson, "The structure of
yet another Algol compiler," _CACM 8_ (July, 1965).
 Conway, M.E., "Design of a separable transition-diagram
compiler," _CACM 6_ (July, 1963).
 Vere, S., "Translation equations," _CACM 13_ (February, 1970).
 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
firstname.lastname@example.org (217) 333-6351
Return to the
Search the comp.compilers archives again.