Chapter Three
Syntax Analysis(Parsing)
Compiler Design
(CoSc 3112)
1
Objective
At the end of this session students will be able to:
Understand the basic roles of Parser(syntactic Analyzer).
Understand context-Free Grammars(CFGs) and their representation
format.
Understand the different derivation formats: Leftmost derivation,
Rightmost derivation and Non-Leftmost, Non-Rightmost derivations
Be familiar with CFG shorthand techniques.
Understand Parse Tree and its structure.
Understand ambiguous grammars and how to deal with ambiguity
from CFGs.
Understand the Extended Backus Naur Form
2
The Role of the Parser
Source Lexical token Rest of
Pars Parse tree Intermediate
program Analyz Front representation
er
er getNextTo End
ken
Symb
ol
table
Parser
The parser is expected to report
performs context-free
any syntax errors in an intelligible
syntax analysis
fashion and to recover from
guides context-sensitive
commonly occurring errors to
analysis
continue processing the
constructs an intermediate
remainder of the program.
representation
3 Conceptually, for well-formed
produces meaningful error
Contd.
The parser obtains a string of tokens from the lexical analyzer,
as shown in the above Figure and verifies that the string of
token names can be generated by the grammar for the source
language.
A grammar gives a precise, yet easy-to-understand, syntactic
specification of a programming language.
From certain classes of grammars, we can construct
automatically an efficient parser that determines the syntactic
structure of a source program.
As a side benefit, the parser-construction process can reveal
syntactic ambiguities and trouble spots that might have slipped
through the initial design phase of a language.
The structure imparted to a language by a properly
designed grammar is useful for translating source programs
4
into correct object code and for detecting errors.
Contd.
There are three general types of parsers for grammars: universal,
top-down, and bottom-up.
1. Universal parsing methods such as the Cocke-Younger-Kasami
algorithm and Earley's algorithm can parse any grammar [Read
more on this].
These general methods are, however, too inefficient to use
in production compilers.
The methods commonly used in compilers can be classified as
being either top-down or bottom-up.
2. Top-Down Methods:- As implied by their names, top-down
methods build parse trees from the top (root ) to the bottom
(leaves ) .
3. Bottom-up methods:- start from the leaves and work their
5 way up to the root to build the parse tree .
Error Handling
Common Programming Errors include:
Lexical errors, Syntactic errors, Semantic errors and logical Errors
Error handler goals
Report the presence of errors clearly and accurately
Recover from each error quickly enough to detect subsequent
errors
Add minimal overhead to the processing of correct programs
Common Error-Recovery Strategies includes:
1. Panic mode recovery:- Discard input symbol one at a time until
one of designated set of synchronization tokens is found.
2. Phrase level recovery:- Replacing a prefix of remaining input by
some string that allows the parser to continue.
3. Error productions:- Augment the grammar with productions that
generate the erroneous constructs
6
4. Global correction:- Choosing minimal sequence of changes to
Context-Free Grammars (CFGs)
CFG is used as a tool to describe the syntax of a programming
language.
A CFG includes 4 components:
1. A set of terminals T, which are the tokens of the language
Terminals are the basic symbols from which strings are
formed.
The term "token name" is a synonym for "terminal"
2. A set of non-terminals N
Non-terminals are syntactic variables that denote sets of
strings.
The sets of strings denoted by non-terminals help define
the language generated by the grammar.
Non-terminals impose a hierarchical structure on the
language that is key to syntax analysis and translation
3. A set of rewriting rules R.
7
The left-hand side (head) of each rewriting rule is a single
Contd.
Just as regular expression generate strings of characters, CFG generate
strings of tokens
A string of tokens is generated by a CFG in the following way:
1. The initial input string is the start symbol S
2. While there are non-terminals left in the string:
i. Pick any non-terminal in the input string A
ii. Replace a single occurrence of A in the string with the right-hand side
of any rule that has A as the left-hand side
iii. Repeat 1 and 2 until all elements in the string are terminals
Example:
Terminals = { id, num, if, then, else, print, =, {, }, ;, (, ) }
Non-Terminals = { S, E, B, L }
Rules = (1) S print(E);
(2) S while (B) do S
(3) S{L}
(4) E id
(5) E num
(6) BE>E
8 (7) LS
(8) L SL
Contd.
Example 3: A grammar that defines simple arithmetic expressions:
Terminals = { id, +, -, *, /, (, ) }
Non-Terminals = {expression, term,Example
factor } 4:
Start Symbol = expression 1. expression expression +
expression
Rules = expression expression + term
2. expression expression –
expression – term
expression
term 3. expression expression *
term expression
term* factor
term/factor 4. expression expression /
expression
factor
5. expression num
factor ( expression )
id expression expression +
9
expression
Conventions
[Link] symbols are terminals :
A. Lowercase letters early in the alphabet, such as a, b, c.
B. Operator symbols such as +, *, and so on .
C. Punctuation symbols such as parentheses , comma, and so
on.
D. The digits 0, 1, ... ,9 .
E. Boldface strings such as id or if, each of which represents a
single terminal symbol.
[Link] symbols are non-terminals:
i. Uppercase letters early in the alphabet, such as A, B, C.
ii. The letter S, which, when it appears, is usually the start symbol.
iii. Lowercase, italic names such as expr or stmt.
iv. Uppercase letters may be used to represent non-terminals for the
constructs.
10
For example:- non terminals for expressions, terms, and
Contd.
4. Lowercase letters late in the alphabet , chiefly u, v, ... ,z ,
represent (possibly empty) strings of terminals.
5. Lowercase Greek letters ,,, for example, represent (possibly
empty) strings of grammar symbols.
Thus, a generic production can be written as A , where A is the
head and the body.
6. A set of productions A 1, A 2, A 3,..., A k with a common
head A (call them A-productions), may be written A 1|A 2|A
3|...|A k.
Call 1, 2, 3,...,k the alternatives for A • The notational
conventions tell us
7. Unless stated otherwise, the head of the firstthat production
E,T, and is the start
F are
non-terminals, with
symbol. E the start symbol.
Example:- Using these conventions , the grammar • The remaining
of Example 4 of
11 symbols are
slide # 9 can be rewritten concisely as:terminals
Derivations
A derivation is a description of how a string is generated from the
start symbol of a grammar.
1. A leftmost derivation always picks the leftmost non-terminal to
replace (see slide 13)
2. A rightmost derivation always picks the rightmost non-terminal to
replace(see slide 14)
Some derivations are neither leftmost nor rightmost (see slide 15)
For example: Use the CFG below to generate print (id);
Terminals = { id, num, if, then, else, print, =, {, }, ;, (, ) }
Non-Terminals = { S, E, B, L }
Rules = (1) S print(E);
(2) S while (B) do S
(3) S { L }
(4) E id
12 (5) E num
(6) B E > E
Leftmost Derivations
A string of terminals and non-terminals α that can be derived from the
initial symbol of the grammar is called a sentential form
Thus the strings “{ S L }”, “while(id>E) do S”, and print(E>id)” of
the above example re all sentential forms
A derivation is “leftmost” if, at each step in the derivation, the leftmost
non-terminal is selected to replace
All of the above examples are leftmost derivations
A sentential form that occurs in a leftmost derivation is called a left-
sentential form
We
Example 2:to
Example 1: We can use leftmost derivations also canwhile(id
generate generate> num) do
print(id); from this CFG as follows: { print(id); print(num); } from
S while(B) do S the CFG as follows:
S{L}
while(E>E) do S
{SL}
while(id>E) do S { print(E); L }
while(id>num) do S { print(id); L }
13 while(id>num) do print(E); { print(id); S }
{ print(id); print(E); }
while(id>num) do print(id);
Rightmost Derivations
Is a derivation technique that chooses the rightmost
non-terminal to replace
Example 1: To generate while(num > num) do print(id);
S while(B) do S
Example 2: Try to derivate { print(num);
while(B) do print(E);
print(id); } from S
S{L}
while(B) do print(id);
{SL}
while(E>E) do print(id);
{SS}
while(E>num) do print(id); { S print(E); }
while(num>num) do print(id); { S print(id); }
{ print(E); print(id); }
{ print(num); print(id); }
14
Non-Leftmost, Non-Rightmost Derivations
Some derivations are Some strings that are not derivable from
neither leftmost or this CFG, such as:
1. print(id)
rightmost, such as:
2. { print(id); print(id) }
S while(B) do S
3. while (id) do print(id);
while(E>E) do S
4. print(id > id);
while(E>E) do 1 & 2: no ; to terminate statements.
print(E); 3: the id in while (id) is not derivable
from B.
while(E>id) do
15 4: id > id is not derivable from E.
print(E);
CFG Shorthand
We can combine two rules of the form S α and S β to get the
single rule S α│β
Example:
Terminals = { id, num, if, then, else, print, =, {, }, ;, (, ) }
Non-Terminals = { S, E, B, L }
Rules = S print(E); | while (B) do S | { L }
E id | num
BE>E
L S | SL
Start Symbol = S
16
Parse Trees
A parse tree is a graphical representation of a derivation that filters
out the order in which productions are applied to replace non-terminals .
Each interior node of a parse tree represents the application of a
production.
The interior node is labeled with the nonterminal A in the head
of the production; the children of the node are labeled, from left to
right, by the symbols in the body of the production by which this A
was replaced during the derivation .
We start with the initial symbol S of the grammar as the root of the tree
The children of the root are the symbols that were used to rewrite the
initial symbol in the derivation
The internal nodes of the parse tree are non-terminals
17
The children of each internal node N are the symbols on the right-hand
Examples
Example 1: -(id+id)
E => -E => -(E) => -(E+E) => -(id+E)=>-(id+id)
Example 2: (id+id*id)
E => E+E => E+E*E =>(E+id*E) =>
(E+id*id)=>(id+id*id)
a b
18 ) )
Ambiguous Grammars
A grammar is ambiguous if there is at least one string derivable from
the grammar that has more than one different parse tree, or more
than one leftmost derivation, or more than one rightmost derivation
Example 2 of slide 18 has two parse trees(parse tree a and b) that
are ambiguous grammars.
Ambiguous grammars are bad, because the parse trees don’t tell us the
exact meaning of the string.
For example, in Example 2 of the previous slide, in Fig a. the string
means id*(id+id), but in Fig.E b, the string means (id*id)+id. This is
T
why we call it “ambiguous”.
We need to change the grammar
T * to Ffix this problem. How? We may
F
rewrite the grammar as follows: ( E )
Terminals = { id, +, -, *, /, (, id
)}
E + T
Non-Terminals = {E, T, F }
T F
Start Symbol = E
F
Rules = E E +T id
19
E E -T id
A parse tree for
Contd.
We need to make sure that all additions appear higher in the tree than
multiplications (Why?)
How can we do this?
Once we replace an E with E*E using single rule 4, we don’t want to
rewrite any of the Es we’ve just created using rule 2, since that would
place an addition (+) lower in the tree than a multiplication (*)
Let’s create a new non-terminal T for multiplication and division
T will generate strings of id’s multiplied or divided together, with
no additions or subtractions.
Then we can modify E to generate strings of T’s added together
This modified grammar is shown at slide no. 19.
20
However, this grammar is still ambiguous. It is impossible to
Contd.
Consider the string id+id+id, which has two parse trees, as shown at
example 2 of slide 18:
id+id+id = (id+id)+id or
= id+(id+id) are all ok
id-id-id = (id-id)-id
!= id-(id-id) but this is wrong
We would like addition and subtraction to have leftmost association
as above
In other words, we need to make sure that the right sub-tree of an
addition or subtraction is not another addition or subtraction
21
We modified the parse tree of example 2 of slide 18 by the CFG and
Extended Backus Naur Form (EBNF)
Another term for a CFG is a Backus Naur Form (BNF).
There is an extension to BNF notation, called Extended Backus Naur
Form, or EBNF
EBNF rules allow us to mix and match CFG notation and regular
expression notation in the right-hand side of CFG rules
For example, consider the following CFG, which describes simpleJava
statement
1. S blocks
{ B } and stylized We
simpleJava print statements:
could express the same language using
2. S print(id) an EBNF as follows:
3. B S ; C 1. S { B }
4. C S ; C 2. S print”(“id”)”
5. C ε 3. B (S;)+
Rules 3, 4, and 5 in the Note
above grammar In Rule 2, when we want a
describe a series of parenthesis to appear in EBNF, we
one or more need to surround it with quotation
22
statements S,
marks.
Exercise
[Link] the following grammar
Terminals = { a, b} Which of the following strings are
Non-Terminals = {S, T, F }
Start Symbol = S derivable from the grammar? Give the
Rules = S TF parse tree [Link]
aaabb strings?
T T T T i. ab v. aaaabb
T a
ii. aabb vi. aabbb
F aFb
F b iii. aba
[Link] that the following CFGs are ambiguous by giving two parse trees
2.2) Terminals = { if, then, else,
for the same string?
print, id }
2.1) Terminals = { a, b }
Non-Terminals = {S, T}
Non-Terminals = {S, T}
Start Symbol = S
Start Symbol = S
Rules = S if id then S T
Rules = S STS
S print id
S b
23 T else S
T aT
T ε
Contd.
[Link] a CFG for each of the following:
[Link] integers with sign (Example: +3, -3)
[Link] set of all strings over { (, ), [, ]} which form balanced
parenthesis. That is, (). ()(), ((()())()), [()()] and ([()[]()]) are in
the language but )( , ][ , (() and ([ are not.
[Link] set of all string over {num, +, -, *, /}which are legal binary
post-fix expressions. Thus numnum+, num num num + *, num
num – num * are all in the language, while num*, num*num and
num num num – are not in the language.
24 [Link] your CFGs in a, b and c ambiguous?
JavaCC-A LL(K) Parser Generator
JavaCC can be used to build recursive dependent parser (RDP) as well
as lexical analyzer.
It takes as input an EBNF grammar for a language and creates a suite
mutually recursive methods that implement a LL(K), Left-to-right,
Leftmost-derivation, k-symbol lookahead parser for the language.
JavaCC File Format Revisited ( Javacc .jj file have the following
format)
Options
{
// Code to set various options flags
}
PARSER_BEGIN(simple)
public class simple
{ /* Extra parser method definitions go here, often a main progress
which drives the parse*/
}
PARSER_END(simple)
TOKEN_MGR_DECLS:
{
25 // Declarations used by the lexical analyzer
}
JavaCC Rules
JavaCC uses Extended Brakus Naur Form (EBNF) rules to describe the
grammar of the language to be parsed.
JavaCC Rules Format is shown below:
void nonTerminal():
{ /* Java Declarations /* }
{
/* Rule Definition */
}
The Java declarations block will be used when we add actions to the
JavaCC rules for building abstract syntax Tree.
Since we are only using JavaCC to determine if a program is
syntactically correct, we will have the Java declaration block blank.
The Rule Definition segment defines the right-hand side of the rule
that we are writing.
Non-terminals in these rules will represent function calls, and
26
thus will be followed by ().
Example
The following CFG rule for a subset of simpleJava statements:
S while (E) S
S V=E;
Would be represented by the JavaCC rule as:
void statement():
{ }
{
<WHILE><LEFTPARENTHESIS>expression()<RIGHTPARENTHESIS>
statement()
Terminals = { num, +, -,
| variable <ASSIGNOP>expression <SEMICOLON>
} *, / }
void expression():
Non-Terminals = {E, T,
{ }
{ F}
<PLUS> expression() expression() Start Symbol = E
| <MINUS> expression() expression() Rules = E + E T
| <TIMES> expression() expression() E - E E
| <DIVIDED> expression() expression() E T
| <INTEGER_LITERAL> T * T F
}
27 T - T F
A CFG for prefix arithmetic
T F
Contd.
There are a few things to note about the form of JavaCC rules:
In CFGs, we have followed the common convention of using
uppercase letters for non-terminals, and lowercase variables for
terminals.
JavaCC uses the reverse conversion, i.e. uppercase letters for
terminals and lowercase letters for non-terminals.
JavaCC non-terminals are usually not a single letter, but amore
meaningful identifier.
28 All terminals(token names) are inside < and >
Question?
29