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.


I don't think that Peter Naur modified BNF, I understood that the acronym was
modified to reflect his role in their use; chair of the Algol 60 committee, on
which John Backus sat. [I believe that's correct. -John]


>2. The Cobol Notation.
> - created by the CODASYL Short-Range Subcommittee.


Is the notation used for PL/1 the same, or different?


>3. Syntax Diagrams.
> - created by Niklaus Wirth (?).


Quite a long time ago (10-15 yrs?) a special issue of Software Practice &
Experience was devoted to Per Brinch Hansen on the Edison language. The
discussion on how the language was specified was remarkably informative.
I think he said that specifying the language, to Peter Naur's
satisfaction, took longer than designing it and building the first
compiler! He used to be a syntax-diagram fan (might even have invented
them for concurrent Pascal?), but became a BNF convert when he realised
the importance of non-terminals when talking about a language.


Regards, Peter


BTW You should also look at the various extended BNFs. Typical reasons for
extension are: lists; thing-separated-lists (eg comma-separated lists);
constrained lists (zero or more, one or more, not more than ...); context
sensitivity.


PS You have not mentioned 2-level grammars; eg Van Wijngarden used for
Algol 68. Perhaps you are wise. :-)
[The 1976 PL/I standard uses a simple EBNF to define the concrete and
abstract syntax of the language. -John]
--

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