Production Systems: or Can We Do Better than BNF?

Since the development of BNF, the definition
of the syntax of programming languages has been 
almost universally associated with context-free requirements.
 Yet numerous interesting and difficult 
issues in syntax stem from the context-sensitive requirements,
notably the compatibility between the 
declaration of an identifier and its uses, the correspondence
between actual and formal parameters, and 
issues arising from block structure.  This paper explores
the use of a formal notation called Production 
Systems in providing a readable and complete formal definition
of syntax.  As a practical illustration, 
a small but significant subset of PL/I is considered.  A
more detailed presentation, as well as the application 
to define abstract syntax and translations between languages,
is given in a previous paper by the author.

CACM February, 1974

Ledgard, H. F.

syntax, translation, context-sensitive grammars,
compilers, formal definition, PL/I standards

4.2 5.21 5.23

CA740205 JB January 18, 1978  1:07 PM

1086	4	2684
1132	4	2684
1234	4	2684
1263	4	2684
1265	4	2684
1270	4	2684
1323	4	2684
1358	4	2684
1379	4	2684
1380	4	2684
1453	4	2684
1464	4	2684
1469	4	2684
1484	4	2684
1486	4	2684
1491	4	2684
1491	4	2684
1498	4	2684
1613	4	2684
1614	4	2684
1781	4	2684
1781	4	2684
1781	4	2684
1825	4	2684
1860	4	2684
2083	4	2684
2178	4	2684
2178	4	2684
2178	4	2684
2179	4	2684
2252	4	2684
2325	4	2684
2326	4	2684
2326	4	2684
2341	4	2684
2470	4	2684
2546	4	2684
2645	4	2684
2652	4	2684
2684	4	2684
2684	4	2684
2684	4	2684
2842	4	2684
2929	4	2684
2934	4	2684
3044	4	2684
3069	4	2684
669	4	2684
679	4	2684
691	4	2684
761	4	2684
949	4	2684
989	4	2684
1303	5	2684
1323	5	2684
2684	5	2684
2684	5	2684
2684	5	2684
3184	5	2684