File Grammar.html    Author McKeeman    Copyright © 2007    index

Grammars for Programming Languages

For programming languages, grammar is synonymous with context-free grammar (CFG). The CFG is not only used to define the syntax of a programming language, it is also used as input to compiler writing tools (such as yacc). In the Darwinian world of language invention, a confusing plethora of notations and file formats for grammars has evolved. One of the goals of this section is to settle on just a few CFG notations, each of which has a particular reason to exist.

The alternatives for grammars for programming languages (aside from notational inventiveness) are in the Chomsky hierarcy of rewriting systems. In addition to the Type 2 (context-free) grammars, Type 3 (regular grammars) are frequently used, especially in describing parsing algorithms. As in the case of context-free grammars, the notational variation is Darwinian and has been evolving for thousands of years.

Theory

The combination of REG and IOG gives the template to implement recursive parsers.

                         CFG
                        /   \
                      REG   IOG
                        \   /
             recursive parser template       

Everyday Examples