Research and Advances
Computing Applications

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.

View this article in the ACM Digital Library.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More