CS 3723  Programming Languages
Formal Grammars

This is the first of 3 pages about grammars.

1. Formal Grammars (Introduction, this page)
2. Derivations, Parse Trees, Ambiguity
3. Types of Grammars

Notice that everything is finite except for the language, where in the interesting cases there are infinitely many sentences, as with the example above. We want to give finite descriptions of languages, including infinite languages. Consider another example: the set L of all strings of as and bs that end with "abb". The previous (English) sentence is an informal finite description. It would (of course) be impossible to list the elements of this language, but we could start: L = {abb, aabb, babb, aaabb, ababb, baabb, bbabb, aaaabb, aababb, ...}.

A context-free grammar (CFG) is a set of recursive replacement rules (or rewriting rules, or productions, or just rules) that are uses to generate patterns of strings.

More formally, a CFG consists of the following components:

• a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar.

• a set of non-terminal symbols, which are placeholders for patterns of terminal symbols that can be generated by the non-terminal symbols.

• a set of replacement rules, which are rules for replacing (or rewriting) non-terminal symbols (on the left side of the production) in a string with other non-terminal or terminal symbols (on the right side of the production). (Replacements are carried out one-at-a-time, independent of other replacements. Replacements are never carried out globally.)

• a start symbol, which is a special non-terminal symbol that appears in the initial string generated by the grammar.

• Identifiers: a, b, or c
• Operators: +, -, *, or /
• Grouping symbols: ( or )

The rules of the grammar are written with a single non-terminal on the left, and a string of terminals and non-terminals used to replace a single occurrence of the non-terminal. Replacements are always done one-at-a-time. We also use an arrow (---->) in the rule between the single non-terminal and the string used for replacement. This arrow is called a meta-symbol: it is neither a terminal nor a non-terminal, but used as part of the notation for the grammar. Here is the grammar:

The start symbol must be a non-terminal, and we only have a single non-terminal, so it must be E.

This grammar defines a language over the alphabet of terminal symbols:

• The first rule states that an expression can be rewritten as (or replaced by) a one of the three identifiers. In other words, an identifier is a valid expression.
• The second rule says that an expression enclosed in parentheses is also an expression. Note that this rule defines an expression in terms of expressions, an example of the use of recursion in the definition of context-free grammars.
• The remaining rules say that the sum, difference, product, or division of two expressions is also an expression.

Using the sixth rule above we can choose to replace this non-terminal, producing the string: E * E.

We now have two non-terminals to replace. We can apply the fourth rule to the first non-terminal, producing the string: E + E * E.

We can apply the last rule to the first non-terminal in this string to produce: (E) + E * E.

If we apply rule 1 three times to the remaining non-terminals (the recursion must end somewhere!), we get: (a) + c * b. This is a valid arithmetic expression, as generated by the grammar.

When applying the rules above, we often face a choice as to which production to choose. Different choices will typically result in different strings being generated.

Given a grammar G with start symbol S, if there is some sequence of productions that, when applied to the initial string S, result in the string s of terminal symbols, then s is in L(G), the language of the grammar.

We will use the symbol ===> to denote the result of a replacement. The sequence of replacements above could be denoted:

Let's rewrite the grammar above. We often use a vertical bar as another meta-symbol to stand for "or". If we do this, then to represent an actual vertical bar as a terminal symbol, we need to enclose it in quotes. Let's also use a non-terminal A to stand for "operator". Then the grammar becomes:

A CFG may have a production for a non-terminal in which the right hand side is the empty string (which is often denoted by Greek epsilon, ε). The effect of this production is to remove the non-terminal from the string being generated.

The discussion of formal grammars continues with Derivations, Parse Trees, Ambiguity.