29

Chapter 4 – Parsing

4.1 Overview of Parsing

If scanning is like constructing words out of letters, then parsing is like

constructing sentences out of words in a natural language. Of course, not
every sequence of words makes a valid sentence: “horse aircraft conju-
gate” is three valid words, but not a meaningful sentence.
To parse a computer program, we must first describe the form of valid
sentences in a language. This formal statement is known as a context free
grammar (CFG). Because they allow for recursion, CFGs are more power-
ful than regular expressions and can express a richer set of structures.
While a plain CFG is relatively easy to write, it does not follow that
is it easy to parse. An arbitrary CFG can contain ambiguities and other
problems that make it difficult to write an automatic parser. Therefore, we
consider two subsets of CFGs known as LL(1) and LR(1) grammars.
LL(1) grammars are CFGs that can be evaluated by considering only
the current rule and next token in the input stream. This property makes
it easy to write a hand-coded parser known as a recursive descent parser.
However, a language (and its grammar) must be carefully designed (and
occasionally rewritten) in order to ensure that it is an LL(1) grammar.
LR(1) grammars are more general and more powerful than LL(1). Nearly
all useful programming languages can be written in LR(1) form. However,
the parsing algorithm for LR(1) grammars is more complex and usually
cannot be written by hand. Instead, it is common to use a parser generator
that will accept an LR(1) grammar and automatically generate the parsing
code.

4.2 Context Free Grammars

Let’s begin by defining the parts of a CFG.

A terminal is an discrete symbol that can appear in the language, oth-
erwise known as a token from the previous chapter. Examples of terminals
are keywords, operators, and identifiers. We will use lower case letters to
represent termals. At this stage, we only need consider the kind (e.g. inte-
ger) and not the value (e.g. 456) of a terminal.

DRAFT September 28, 2016

30 CHAPTER 4. PARSING

A non-terminal represents a structure that can occur in a language,

but is not a literal symbol. Example of non-terminals are declarations,
statements, and expressions. We will use upper-case letters to represent
non-terminals: P for program, S for statement, E for expression, etc.
A sentence is a valid sequence of terminals in a language, while a sen-
tential form is a valid sequence of terminals and non-terminals. We will
used greek symbols to represent sentential forms. For example, α repre-
sents a (possibly) mixed sequence of terminals and non-terminals.
A context-free grammar (CFG) is a list of rules that formally describe
the allowable sentences in a language. The left-hand side of each rule is
always a single non-terminal. The right-hand side of a rule is a sentential
form that describes an allowable form of that non-terminal. For example,
the rule A → xXy indicates that the non-terminal A represents a terminal
x followed by a non-terminal X and a terminal y. The first rule is special:
it is the top-level definition of a program and its non-terminal is known as
the start symbol.
(A context-free grammar is context-free in the sense that a rule has the
same definition no matter where it is used. A context-sensitive grammar
has rules of the form aAb → c, indicating that the rule only applies when
A is surrounded by a and b. Context-sensitive grammars are not widely
used because of the high algorithmic complexity of parsing.)
For example, here is a simple CFG that describes expressions involving
addition, integers, and identifiers:

Grammar G2
1. P→E
2. E→E+E
3. E → ident
4. E → int

This grammar can be read as follows: (1) A complete program consists

of one expression. (2) An expression can be any expression plus any ex-
pression. (3) An expression can be an identifier. (4) An expression can be
an integer literal.

4.2.1 Deriving Sentences

Each grammar describes a (possibly infinite) set of sentences, which is
known as the language of the grammar. To prove that a given sentence is
a member of that language, we must show that there exists a sequence of
rule applications that connects the start symbol with the desired sentence.
A sequence of rule applications is known as a derivation and a double ar-
row is used to show that one sentence is equal to another by derivation.
For example, P ⇒ ident + int by applying rules 1-4 of Grammar G2 .
There are two approaches to derivation: top-down and bottom-up.

DRAFT September 28, 2016

4.2. CONTEXT FREE GRAMMARS 31

In top-down derivation, we begin with the start symbol, and then ap-
ply rules in the CFG to expand non-terminals until reaching the desired
sentence. For example, ident + int + int is a sentence in this language, and
here is one derivation to prove it:

Sentential Form Apply Rule

P P→E
E E → E+E
E+E E → ident
ident + E E → E+E
ident + E + E E → int
ident + int + E E → int
ident + int + int

In bottom-up derivation, we begin with the desired sentence, and then

apply the rules backwards until reaching the start symbol. Here is a bottom-
up derivation of the same sentence:

Sentential Form Apply Rule

ident + int + int E → int
ident + int + E E → int
ident + E + E E → E+E
ident + E E → ident
E+E E → E+E
E P→E
P

4.2.2 Ambiguous Grammars

An ambiguous grammar allows for more than one possible derivation of
the same sentence. Our example grammar is ambiguous because there are
two possible derivations for any sentence involving two plus signs. The
sentence ident + int + int can have the two derivations shown in
Figure 4.1.
Ambiguous grammars present a real problem for parsing (and lan-
guage design in general) because we do not want a program to have two
possible meanings.
Does it matter in this example? It certainly does! In a language like
Java, the + operator indicates addition between integers, but concatenation
between strings. If the identifier is hello and the two integers have the
value 5, then the left-most derivation would concatenate all three together
into hello55, while the right-most derivation would compute 5+5=10
and concatenate the result into hello10.
Fortunately, it is usually possible to re-write a grammar so that it is not
ambiguous. In the common case of binary operators, we can require that
one side of the expression be an atomic term (T), like this:

DRAFT September 28, 2016

32 CHAPTER 4. PARSING

Left-Most Derivation Right-Most Derivation

P P

E E

E + E E+E

E + E int ident E+E

ident int int int

Figure 4.1: Two Derivations of the Same Sentence

Grammar G3
1. P→E
2. E→E+T
3. E→T
4. T → ident
5. T → int

With this change, the grammar is no longer ambiguous, because it only

allows a left-most derivation. But also note that it still accepts the same lan-
guage as Grammar G2 . That is any sentence that can be derived by Gram-
mar G2 can also be derived by Grammar G3 , but there exists only one
derivation (and one meaning) per sentence. (Proof is left as an exercise to
the reader.)
Now suppose that we would like to add more operators to our gram-
mar. If we simply add more rules of the form E → E ∗ T and E → E ÷ T, we
would still have an unambiguous grammar, but it would not follow the
rules of precedence in algebra: each operator would be applied from left
to right.
Instead, the usual approach is to construct a grammar with multiple
levels that reflect the intended precedence of operators. For example, we
can combine addition and multiplication by expressing them as a sum of

DRAFT September 28, 2016

4.2. CONTEXT FREE GRAMMARS 33

terms (T ) that consist of multiplied factors (F ), like this:

Grammar G4
1. P→E
2. E→E+T
3. E→T
4. T→T*F
5. T→F
4. F → ident
5. F → int

Here is another common example that occurs in most programming

languages in some form or another. Suppose that an if statement has two
variations: an if-then which takes an action when an expression is true,
and an if-then-else that takes a different action for the true and false cases.
We can express this fragment of the language like this:

Grammar G5
1. P→S
2. S → if E then S
3. S → if E then S else S
4. S → other

Grammar G5 is ambiguous because it allows for two derivations of

this sentence: if E then if E then other else other. Do you
see the problem? The else part could belong to the outer if or to the in-
ner if. In most programming langauges, the else is defined as belonging
to the inner if, but the grammar does not reflect this.

Exercise: Write out the two possible parse trees for the sentence if E
then if E then other else other.

Exercise: Write out an improvement to Grammar G5 that does not have

the dangling-else problem. Hint: Prevent the inner S from containing an
if without an else.

DRAFT September 28, 2016

34 CHAPTER 4. PARSING

4.3 LL Grammars

LL(1) grammars are a subset of CFGs that are easy to parse with simple
algorithms. A grammar is LL(1) if can be parsed by considering only only
one non-terminal and the next token in the input stream.
To ensure that a grammar is LL(1), we must do the following:

• Remove any ambiguity, as shown above.

• Eliminate any left recursion, as shown below.

• Eliminate any common left prefixes, as shown below.

Once we have taken those steps, then we can prove that it is LL(1) by
generating the F IRST and F OLLOW sets for the grammar, and using them
to create the LL(1) parse table. If the parse table contains no conflicts, then
we have proven that the grammar is LL(1).

4.3.1 Eliminating Left Recursion

LL(1) grammars cannot contain left recursion, which is a rule of the form
A → Aα or, more generally, any rule A → Bβ such that B ⇒ Aγ by some
sequence of derivations. For example, the rule E → E + T is left-recursive
because E appears as the first symbol on the right hand side.
You might be tempted to solve the problem by simply re-writing the
rule as E → T + E. While that would avoid left-recursion, it would would
not be an equivalent grammar because it would result in a right-associative
plus operator. Also, it would introduce the new problem of a common left
prefix, discussed below.
Informally, we must re-write the rules so that the (formerly) recursive
rule begins with the leading symbols of its alternatives.
Formally, if you have a grammar of the form:

A → Aα1 |Aα2 |...|β1 |β2 |...

Substitute with:

A → β1 A′ |β2 A′ |...

A’ → α1 A′ |α2 A′ |...|ǫ

Applying this rule to grammar Grammar G4 , we can re-write it as:

DRAFT September 28, 2016

4.3. LL GRAMMARS 35

Grammar G6
1. P →E
2. E → T E’
3. E’ → + T E’
4. E’ → ǫ
5. T → ident
6. T → int

While Grammar G6 is perhaps slightly harder for a person to read, it

no longer contains left recursion, and satisfies all the LL(1) properties. A
parser considering an E in rule 2 will immediately consider the T non-
terminal, and then look ident or int on the input to decide between rule
5 and 6. After considering T , the parser moves on to consider E ′ and can
distinguish between rule 3 and 4 by looking for either a + or any other
symbol on the inpu.

4.3.2 Eliminating Common Left Prefixes

A simpler problem to solve is grammars that have multiple rules with
the same left hand side and a common prefix of tokens on the right hand
side. Informally, we simply look for all common prefixes of a given non-
terminal, and replace them with one rule that contains the prefix, and an-
other that contains the variants.
Formally, look for rules of this form:

A → αβ1 |αβ2 |...

And replace with:

A → αA′

A′ → β1 |β2 |...

For example, these rules describing an identifier, array reference, and

function call all share the same prefix of a single identifier:

Grammar G7
1. P→E
2. E → id
3. E → id [ E ]
4. E → id ( E )

If a parser is evaluting E and sees an id on the input, that information

is not sufficient to distinguish between rules 2, 3, and 4. However, the
grammar can be salvaged by factoring out the common prefix, like this:

DRAFT September 28, 2016

36 CHAPTER 4. PARSING

Grammar G8
1. P →E
2. E → id E’
3. E’ → [ E ]
4. E’ → ( E )
5. E’ → ǫ

In this formulation, the parser always consumes an id when evaluat-

ing an E. If the next token is [, then rule 3 is applied. If the next token is
(, then rule 4 is applied, otherwise, rule 5 is applied.

DRAFT September 28, 2016

4.3. LL GRAMMARS 37

4.3.3 First and Follow Sets

In order to construct a complete parser for an LL(1) grammar, we must
compute two sets, known as F IRSTand F OLLOW. Informally, F IRST(α) in-
dicates the set of terminals (including ǫ) that could potentially appear in
any derivation of α. F OLLOW(A) indicates the set of terminals (including
$) that could potentially occur after any derivation of the non-terminal A.
Given the contents of these sets, an LL(1) parser will always know which
rule to pick next.
Here is how to compute F IRST and F OLLOW:

Computing First Sets for a Grammar G

F IRST(α) is the set of terminals that begin all strings given by α,

including ǫ if α ⇒ ǫ.

For each terminal a ∈ Σ: F IRST(a) = a

Repeat:
For each rule X → Y1 Y2 ...Yk in a grammar G:
Add a to F IRST(X)
if a is in F IRST(Y1 )
or a is in F IRST(Yn ) and Y1 ...Yn−1 → ǫ
If Y1 ...Yk → ǫ then add ǫ to F IRST(X).
until no more changes occur.

Computing Follow Sets for a Grammar G

F OLLOW(A) is the set of terminals that can come after non-terminal A,

including $ if A occurs at the end of the input.

F OLLOW(S) = {$} where S is the start symbol.

Repeat:
If A → αBβ then:
add F IRST(β) to F OLLOW(B).
If A → αB or F IRST(β) contains ǫ then:
add F OLLOW(A) to F OLLOW(B).
until no more changes occur.

DRAFT September 28, 2016

38 CHAPTER 4. PARSING

Here is an example of computing F IRST and F OLLOW for Grammar G9 :

Grammar G9
1. P →E
2. E → T E’
3. E’ → + T E’
4. E’ → ǫ
5. T → F T’
6. T’ → * F T’
7. T’ → ǫ
8. F →(E)
9. F → int

First and Follow for Grammar G9

P E E’ T T’ F
F IRST ( int ( int +ǫ ( int *ǫ ( id
F OLLOW $ )$ )$ +)$ +)$ +*)$

4.4 Top Down Parsing

Once we have cleaned up a grammar to be LL(1) and computed its F IRST

and F OLLOW sets, we are ready to write code for a parser. This can be
done by hand or with a table-driven approach.

4.4.1 Recursive Descent Parsing

LL(1) grammars are very amenable to writing simple hand-coded parsers.
A common approach is a recursive descent parser in which there is one
simple function for each non-terminal in the grammar. The body of the
function follows the right-hand sides of the corresponding rules: non-
terminals result in a call to another parse function, while terminals result
in considering the next token.
Three helper functions are needed:

• scan token() returns the next token on the input stream.

• putback token(t) puts an unexpected token back on the input

stream, where it will be read again by the next call to scan token.

• expect token(t) calls scan token to retrieve the next token. It

returns true if the token matches the expected type. If not, it puts the
token back on the input stream and returns false.

DRAFT September 28, 2016

4.4. TOP DOWN PARSING 39

Figure 4.2 shows how Grammar G9 could be written as a recursive de-

scent parser. Note that the parser has one function for each non-terminal:
parse P, parse E, etc. Each function returns true (1) if the input matches
the grammar, or false (0) otherwise.
Two special cases should be considered. First, if a rule X cannot pro-
duce ǫ and we encounter a token not in F IRST(X), then we have definitely
encountered a parsing error, and we should display a message and return
failure. Second, if a rule X could produce ǫ and we encounter a token not
in F IRST(X), then we accept the rule X → ǫ put the token back on the input,
and return success. Another rule will expect to consume that token.
There is also the question of what the parser should actually do after
matching some element of the grammar. In our simple example, the parser
simply returns true on a match, and serves only to verify that the input
program matches the grammar. If we wished to actually evaluate the ex-
pression, each parse X function could compute the result and return it
as a double. This would effectively give us a simple interpreter for this
language. Another approach is for each parse X function to return a data
structure representing that node of the parse tree. As each node is parsed,
the result is assembled into an abstract syntax tree, with the root returned
by parse P.

DRAFT September 28, 2016

40 CHAPTER 4. PARSING

int parse_P() {
return parse_E() && expect_token(TOKEN_EOF);
}

int parse_E() {
return parse_T() && parse_E_prime();
}

int parse_E_prime() {
token_t t = scan_token();
if(t==TOKEN_PLUS) {
return parse_T() && parse_E_prime();
} else {
putback_token(t);
return 1;
}
}

int parse_T() {
return parse_F() && parse_T_prime();
}

int parse_T_prime() {
token_t t = scan_token();
if(t==TOKEN_MULTIPLY) {
return parse_F() && parse_T_prime();
} else {
putback_token(t);
}
}

int parse_F() {
token_t = scan_token();
if(t==TOKEN_LPAREN) {
return parse_E() && expect_token(TOKEN_RPAREN);
} else if(t==TOKEN_INT) {
return 1;
} else {
printf("parse error: unexpected token %s\n",
token_string(t));
return 0;
}
}

Figure 4.2: A Recursive-Descent Parser

DRAFT September 28, 2016

4.4. TOP DOWN PARSING 41

4.4.2 Table Driven Parsing

An LL(1) grammar can also be parsed using generalized table driven code.
A table-driver parser requires a grammar, a parse table, and a stack to
represent the current set of non-terminals.
The LL(1) parse table is used to determine which rule should be ap-
plied for any combination of non-terminal on the stack and next token on
the input stream. (By definition, an LL(1) grammar has exactly one rule to
be applied for each combination.) To create a parse table, we use the F IRST
and F OLLOW sets like this:

LL(1) Parse Table Construction.

Given a grammar G and alphabet Σ, create a parse table T [A, a]
that selects a rule for each combination of non-terminal A ∈ G
and terminal a ∈ Σ.

For each rule A → α in G:

For each terminal a (excepting ǫ) in F IRST(α):
Add A → α to T [A, a].
If ǫ is in F IRST(α):
For each terminal b (including $) in F OLLOW(A):
Add A → α to T [A, b].

For example, here is the parse table for Grammar G9 . Notice that the
entries for P , E, T , and F are straightforward: each can only start with
int or (, and so these tokens cause the rules to descend toward F and a
choice between rule 8 (F → int) and rule 9 (F → (E)). The entry for E ′ is
a little more complicated: a + token results in applying E → +T E ′ , while
) or $ indicates E → ǫ.

Parse Table for Grammar G9 :

int + * ( ) $
P 1 1
E 2 2
E’ 3 4 4
T 5 5
T’ 7 6 7 7
F 9 8

DRAFT September 28, 2016

42 CHAPTER 4. PARSING

Now we have all the pieces necessary to operate the parser. Informally,
the idea is to keep a stack which tracks the current state of the parser. In
each step, we consider the top element of the stack and the next token on
the input. If they match, then pop the stack, accept the token and continue.
If not, then consult the parse table for the next rule to apply. If we can
continue until the end-of-file symbol is matched, then the parse succeeds.

LL(1) Table Parsing Algorithm.

Given a grammar G with start symbol P and parse table T ,
parse a sequence of tokens and determine whether they satisfy G.

Create a stack S.
Push $ and P onto S.
Let c be the first token on the input.

While S is not empty:

Let X be the top element of the stack.
If X matches c:
Remove X from the stack.
Advance c to the next token and repeat.
If X is any other terminal, stop with an error.
If T [X, c] indicates rule X → α:
Push symbols α on to the stack and repeat.
If T [X, c] indicates an error state, stop with an error.

Here is an example of the algorithm applied to the sentence int * int:

Stack Input Action

P$ int * int $ apply 1: P ⇒ E
E$ int * int $ apply 2: E ⇒ T E’
T E’ $ int * int $ apply 5: T ⇒ F T’
F T’ E’ $ int * int $ apply 9: F ⇒ int’
id T’ E’ $ * int $ match int
T’ E’ $ * int $ apply 6: T’ ⇒ * F T’
* F T’ E’ * int $ match *
F T’ E’ int $ apply 9: F ⇒ int
int T’ E’ int $ match int
T’ E’ $ apply 7: T’ ⇒ ǫ
E’ $ apply 4: E’ ⇒ ǫ
$ $ match $

DRAFT September 28, 2016