A Context Free Grammar for Arithmetic Expressions

The following context free grammar applet allows you to explore context free grammars, including construction of context free grammars, derivations of strings in context free grammars, and parse tree building.  You will notice that the applet is actually larger than the browser window. You will occasionally need to scroll the parse tree window down; to do this you will have to run the bottom slder bar to the right so that you can move the browser pane slider bar down.

Example:  A Grammar for Arithmetic Expressions

A simple grammar for arithmetic expressions shows up in the applet below.  The terminals for this grammar are {identifier, integer_literal, addop, mulop, (, and )}.  The terminal "identifier" stands for any variable name in a typical programming language.  The terminal "integer_literal" stands for any integer.  The terminal addop stands for either the + or the - operator, and the mulop terminal stands for either the * or the / operator.  The language of this grammar is the set of all strings that are valid arithmetic expressions, such as

• a + b * a
• b * (a + b) / 4
• c

and so forth.

Create a parse tree for each of the above arithmetic expressions.  Remember that what you are really deriving in each case is

• identifier addop identifier mulop identifier
• identifier mulop (identifier addop identifier) mulop integer_literal
• identifier