9.3.  Generating Strings from a CFG

In our grammar for arithmetic expressions, the start symbol is <expression>, so our initial string is:

<expression>

Using rule 5 we can choose to replace this nonterminal, producing the string:

<expression> * <expression>

We now have two nonterminals to replace. We can apply rule 3 to the first nonterminal, producing the string:

<expression> + <expression> * <expression>

We can apply rule two to the first nonterminal in this string to produce:

(<expression>) + <expression> * <expression>

If we apply rule 1 to the remaining nonterminals (the recursion must end somewhere!), we get:

(number) + number * number

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, then s is in L(G), the language of the grammar.

Last modified 22/May/97