Bachelor of Software Engineering (Hons)
Bachelor of Computer Science (Hons)
ITS64304: Theory of Computation
Tutorial – 2: Parse Trees
Aim
The aim of this tutorial is to learn context free grammar. By the end of this tutorial, you should be
able to build parse tress, analyze and generate a grammar for a given specification, and determine
whether a given grammar is ambiguous. (Aligns with Module Learning Outcome 1)
Taylor’s Graduate Capabilities (TGCs) developed
2.1 Parsing
Example
Let G be the grammar
S → aS | aAb
A → aA | b
1. Using this grammar, produce two left-most derivations for the string ”aaabb”.
2. Build the parse trees for the derivations from part (1).
3. Is this grammar ambiguous? Why or why not?
Solution
1. A left-most derivation is one in which the left-most variable is used for expansion at all points
in the derivation. In other words, when there is a choice to be made between two or more
variables, the left-most one is always chosen. A right-most derivation is defined similarly, i.e.
that the right-most variable is always chosen. If there is only one variable at every derivation
step, then the derivation is both left-most and right-most.
ITS64304 Tutorial - 2: Parse Trees 1
One left-most derivation is as follows:
S aS (for S choose aS)
. aaS (for S choose aS)
. aaaAb (for S choose aAb)
. aaabb (for A choose b) (end - no more variables)
Another way to derive this string is as follows:
S aAb (for S choose aAb)
. aaAb (for A choose aA)
. aaaAb (for A choose aA)
. aaabb (for A choose b)
2. The two parse trees are shown below:
S S
a S a A b
a S a A
a A b a A
b b
(a) Derivation 1 (b) Derivation 2
If you follow the leaf nodes from left to right, you will obtain the derived string.
3. If you can have more than one left-most derivation for the same string in a given grammar,
then that grammar is ambiguous.
Questions
1. Consider the grammar given below.
S → aS | Sb | ab | SS
(a) Using this grammar, produce two leftmost derivations of the string “aaabbb”.
(b) Build the parse trees for the derivations from part (a).
(c) Discuss your answer and how it relates to ambiguity.
ITS64304 Tutorial - 2: Parse Trees 2
2. Let G be the grammar
S → aS | aA | a
A → aAb | ab
(a) Using this grammar, produce two leftmost derivations of the string ”aaaabb”.
(b) Build the parse trees for the derivations from part (a).
3. Let G be the grammar
S → aSb | aAb
A → cAd | B
B → aBb | (λ)
Use leftmost or rightmost derivation to construct a parse tree, on the following strings:
(a) “aacabdbb”
(b) “aaaaabbbbb” See if any of the above strings can be derived by more than one parse
tree.
4. Construct a grammar that recognizes the language L = {w ϵ {a, b}* | if w has a b then it has an
a associated with it}. Evaluate and state whether the grammar that you have constructed for
the given language L is ambiguous or not using derivations or parse trees.
Reflection
What happens if there are more than one parse tree for a given grammar? What relevance it has
with compilation. Record your observation in the tutorial summary sheet.
ITS64304 Tutorial - 2: Parse Trees 3
