Module - 2

Introduction to Syntax Analysis

 Introduction to Syntax Analysis

Role of the Syntax Analyser – Syntax error handling.

Review of Context Free Grammars - Derivation and Parse
Trees, Eliminating Ambiguity.
Basic parsing approaches - Eliminating left recursion, left
factoring.
Top-Down Parsing - Recursive Descent parsing, Predictive
Parsing, LL(1) Grammars.
• Every programming language has certain rules
that describe the syntactic structure of its
programs.
– Procedure oriented programs -> blocks -> statements
-> expressions -> tokens etc.
• The syntax of programming language constructs
can be described by Context Free
Grammar(CFG) or Backus Naur Form (BNF)
• Grammar offer certain benefits to both
language designers and compiler writers:
– A Grammar gives a precise, yet easy to understand
syntatic specification of a PL.
– Using grammars, we can automatically construct an
efficient parser that determine the syntatic structure of
the source program. This parser construction process
reveals syntatic ambiguities and other difficult-to-parse
constructs.
– A properly designed grammar imparts a structure to a PL
that is useful for the translation of programs and error
detection.
– New constructs can be added to the language when there
is an implementation based on a grammar.
 The role of the Parser

token
Source Lexical Parse tree Rest of Front Intermediate
Parser
program Analyzer End representation
getNext
Token

Symbol
table
 Parsing
• Parsing is the process of determining whether a string of
tokens can be generated by a grammar.
• Detect syntax errors and recover from commonly
occurring errors.
• Most parsing methods fall into one of two classes, called the
top-down and bottom-up methods.
• In top-down parsing, construction starts at the root and
proceeds to the leaves.
• In bottom-up parsing, construction starts at the leaves and
proceeds towards the root.
• Bottom-up parsing, can handle a larger class of grammars.
They are not as easy to build, but tools for generating them
directly from a grammar are available.
5
 Syntax Error handling
• Common programming errors
– Lexical errors
– misspelling of an identifier, keyword or operator
– Syntactic errors
– Arithmetic expression with unbalanced parenthesis
– Semantic errors
– An operator applied to an incompatible operand
– Logical Errors
– Iinfinitely recursive call

Much of the error detection and recovery in a compiler is

done by the syntax analyzer.
• Error handler goals
– Report the presence of errors clearly and accurately.
– Recover from each error quickly enough to
detect subsequent errors.
– Should not slow down the processing of correct
programs.
 Error-recover strategies
• Panic mode recovery
– Discard input symbol one at a time until one of
designated set of synchronization tokens is found.
• Phrase level recovery
– Parser may perform local correction on the input
– Replacing a prefix of remaining input by some string
that allows the parser to continue
– Eg: replace a comma by semicolon, delete an extraneous
semicolon, insert a missing semicolon etc.
• Error productions
– Augment the grammar with productions that
generate the erroneous constructs
• Global correction
– Using algorithms to choose minimal sequence of
changes to obtain a globally least-cost correction.
– Too costly to implement, exists only for
theoretical interest.
 Context free grammars
• Used to specify the syntax of a language.
• A CFG has four components:
– Terminals (tokens) – basic symbols from which strings
are formed(token).
– Non-terminals - Syntatic variables, denote sets of
strings. Eg:- stmt, expr …
– Start symbol – One of the NT.
– The set of strings the start symbol denotes is the language defined by
the grammar.
– Productions – Specify the manner in which the terminals
and non-terminals can be combined to form strings.
A grammar for arithmetic expressions
expression -> expression + term
expression -> expression – term
expression -> term
term -> term * factor
term -> term / factor
term -> factor
factor -> (expression)
factor -> id

• Terminal Symbols : id + - * / ( )
 Notational Conventions

• Terminals:
• Lower case early in the alphabet a,b,c….
• Operator symbols +,-,* etc.
• Punctuation Symbols(parenthesis,comma etc.)
• The digits 0,1,2,….,9.
• Token names such as id, num,if, then else etc.

NonTerminals:
•Upper case letters early in the alphabet A,B,C,…
•Start symbol, S.
•Lower case names such as expr, stmt etc.
Notational Conventions
• Upper case letters late in the alphabet, X,Y,Z, represent
grammar symbols(terminals or nonterminals)
• Lower case letters late in the alphabet, u.v…,z, represent
strings of terminals.
• Upper case Greek letters α,β,γ,represent strings of grammar
symbols. A -> α
Derivations
 A production is a rewriting rule in which the NT on the left
is replace by the string on the right side.
 Example:

- If E is an expression, then –E must also be an expression

denotes the replacement of a single E by -E
“ E derives –E”
derivation of –(id) from E
-(id) is an instance of an expression.
L(G) – denote the language generated by G.
Starting with S, relation can be used to define L(G).
Strings in L(G) contain only terminal symbols of G.
A string of terminal w is in L(G), only if S w.
The string w is a sentence of grammar G.
 At each step in a derivation, two choices are to be
made:
 Which nonterminal to replace.
 Which alternative(production) to use for that nonterminal.

 Leftmost Derivations – Leftmost NT in each sentential form is

replaced at each step.
 Rightmost Derivations –

 then, α is a left sentential form of the Grammar.

 Parse Trees and Derivations
 Parse Tree - Graphical representation for a derivation.
 Each interior node of the parse tree is labelled by a NT A.
 The children of the node are labelled, from left to right, by the
symbols in the right side of the production by which A was
replaced in the derivation.
 The leaves of a parse tree are labelled by terminals or
nonterminals.
 Reading from left to right, they form a sentential form.
 Parse Tree for –(id+id)
Sequence of parse tree derivations
Ambiguous Grammar
 Produces more than one leftmost derivation or more
than one rightmost derivation for the same sentence.
 Eg:- Consider the Grammar

 Eg:- Two distinct leftmost derivations for the sentence

id+id*id
Eliminating Ambiguity
 Eg:- Consider the “dangling else” grammar

 The statement
has the parse tree,
 The grammar is ambiguous since the string
has two parse trees:
 Eliminating ambiguity
 The general rule is “Match each else with the closest previous
unmatched then”
 This disambiguating rule can be incorporated into the grammar.
 The statement appearing between a then and an else must be
matched.
 A matched statement is an if-then-else statement containing no
unmatched statements or any other kind of unconditional
statements.
 Left Recursive Grammars
• A grammar is left recursive if it has a nonterminal A
such that there is a derivation A Aα, for some
string α.
• Top-down parsers can loop forever when facing a
left-recursive rule. Therefore, such rules need to be
eliminated.
• A left-recursive rule such as A A α | β can
be eliminated by replacing it by:

A β A’ where A’ is a new non-terminal

and є is the empty string
A’ α A’ | є
`
 Left-Recursive Grammars
• The general procedure for removing direct left recursion—recursion that
occurs in one rule—is the following:
– Group the A-rules as
A Aα1 | Aα2 | … | Aαm | β1 | β2|…| βn
where none of the β’s begins with A.
– Replace the original A-rules with
• A β1A’ | β2 A’ | … | βn A’
• A’ α1 A’ | α2 A’ | … | αm A’
• This procedure will not eliminate indirect left recursion of the kind:
– S  Aa|b S  Aa | b
– A Ac|Sd|Ԑ A  Ac | Aad |bd | Ԑ
A  bdA’ | A’
A’ cA’ | adA’ |Ԑ
• Direct or Indirect Left-Recursion is problematic for all top-down
parsers. However, it is not a problem for bottom-up parsing
algorithms.
2
7

Left-Recursive Grammars
• Here is an example of a (directly) left-recursive
grammar:
EE+T|T
TT*F|F
F  ( E ) | id
• This grammar can be re-written as the following non
left-recursive grammar:

E  T E’ E’  + TE’ | є
T  F T’ T’  * F T’ | є
F  (E) | id
2
9

Left-Factoring a Grammar
• A grammar transformation useful for producing a
grammar suitable for predictive parsing.
• When it is not clear which of the alternative
productions to use to expand a non-terminal A,
rewrite the A-productions to defer the decision until
we’ve seen enough of the input to make the right
choice.
stmt -> if expr then stmt else stmt
|if expr then stmt
In General,
A  αβ1 | αβ2
A  αA’
A’  β1 | β2
3
0

Left-Factoring a Grammar
• procedure used to left-factor a grammar:
– For each non-terminal A, find the longest prefix α
common to two or more of its alternatives.
– Replace all the A productions:
A  αβ1 | αβ2 … | αβn | γ
(where γ represents all alternatives that do not begin with α)
– By:
A  α A’ | γ
A’  β1 | β2 | … | βn
3
1

Left-Factoring a Grammar
• Here is an example of a common grammar that needs
left factoring:

S  iEtS | iEtSeS | a
Eb
( i stands for “if”; t stands for “then”; and e stands for “else”)

• Left factored, this grammar becomes:

S  iEtSS’ | a
S’  eS | є
Eb
 Top-Down Parsing

• Top-Down Parsing is an attempt to find a left-most

derivation for an input string.
• An attempt to construct a parse tree for the input string
from the root and creating the nodes of the parse tree in
preorder.
• Recursive-Descent Parsing
– A general form of top-down parsing, that may involve
backtracking.(repeated scans of the input)
Recursive-Descent Parsing

Example:
S  cAd Find a derivation for
A  ab | a for w = cad

S S Backtrack S
/|\  /|\  /|\
c A d c A d c A d
/\ |
a b a
3
5

Predictive Parser
• In many cases, by carefully writing a grammar—
eliminating left recursion from it and left factoring the
resulting grammar—we can obtain a grammar that
can be parsed by a recursive-descent parser that needs
no backtracking.
• Such parsers are called predictive parsers.
3
6

Predictive Parser
• The key problem during predictive parsing is that of
determining the production to be applied for a non-
terminal.
• Given the current input symbol ‘a’ and the non-terminal A
to be expanded, which one of the alternatives of the
production A -> α1 | α2 | α3 |…… | αn is the unique
alternative that derives a string beginning with ‘a’.
• The proper alternative must be detectable by looking only
the first symbol it derives.
 Predictive parser
• Predictive parser can be implemented using a parsing table.
• A table-driven predictive parser has
• An input buffer (contains the string to be parsed followed by $)
• A stack(holds the grammar symbols with $ at bottom)
• A parsing table (a two-dimensional array M[A,a] )
where ‘A’ is a non-terminal, and ‘a’ is a terminal
or the symbol $, meaning “end of input string”.
3
8

Predictive Parser: Procedure

• The predictive parser considers X, the symbol on

top of the stack, and a, the current input symbol.
It uses, M, the parsing table.
– If X = a = $ parser halts and return success.
– If X = a ≠ $ pop X off the stack and advance input
pointer to the next symbol
– If X is a non-terminal Check M[X,a]
• If the entry is a production rule, then replace X on the stack by
the Right Hand Side of the production
• If the entry is blank, then halt and return failure
Input: A string w and parsing table M for grammar G.
Output: If w is in L(G), a leftmost derivation of w; otherwise an error indication.
Method:- Initially, parser is in the configuration $S on the stack and w$ in the input buffer.
set ip to point to the first symbol of w$;
repeat
let X be the top stack symbol and ‘a’ the symbol pointed to by ip;
if X is a terminal or $ then
if X = a then
pop X off the stack and advance ip.
else error()
else /* X is a non-terminal */
if M[X,a] = X->Y1Y2…..Yk then begin
pop X from the stack;
push Yk,Yk-1,…….Y1 on to the stack, Y1 on top;
output the production X-> Y1Y2…..Yk
end
else error()
until X=$ /* Stack is empty */
Predictive Parser: An Example
E  T E’
EE+T|T
E’  + TE’ | є
TT*F|F T  F T’
F  ( E ) | id
T’  * F T’ | є
F  (E) | id
id + * ( ) $

E ETE’ ETE’

E’ E’+TE’ E’є E’є

T T FT’ TFT’
T’ T’є T’*FT’ T’є T’є

F Fid F(E)

21
Parsing Table
 Stack Input Output
Predictive Parser: $E id+id*id$
An Example $E’T id+id*id$ E  TE’
$E’T’F id+id*id$ T  FT’
$E’T’id id+id*id$ F  id
$E’T’ +id*id$
$E’ +id*id$ T’  є
$E’T+ +id*id$ E’  +TE’
$E’T id*id$
$E’T’F id*id$ T  FT’
$E’T’id id*id$ F  id
$E’T’ *id$
$E’T’F* *id$ T’  *FT’
$E’T’F id$
$E’T’id id$ F  id
$E’T’ $
Algorithm Trace 
$E’ $ T’  є
$ $ E’  є
 Constructing the Parsing Table :
FIRST and FOLLOW
• If α is any string of grammar symbols, FIRST(α) is the set
of terminals that begin the strings derived from α.
If α => Ɛ, then Ɛ is also in FIRST(α)
• FOLLOW(A) is the set of terminals ‘a’ that can appear
immediately to the right of A in a sentential form.
• If A is the rightmost symbol in some senetntial form, then
$ is in FOLLOW(A) .
• FIRST and FOLLOW are used in the construction of the
parsing table.
Computing FIRST(X):
• If X is a terminal, then FIRST(X) is {X}
• If X -> Ɛ is a production, then add Ɛ to FIRST(X).
• If X is a non-terminal and X -> Y1 Y2 … Yk is a production,
then everything in FIRST(Y1) is in FIRST(X). If FIRST(Y1)
contains Ɛ, (ie. Y1-> Ɛ )then add FIRST(Y2) to FIRST(X).

Computing FOLLOW(A):
• Place $ in FOLLOW(S), where S is the start symbol
and $ is the input right endmarker.
• If there is a production A -> αBβ, then everything in
FIRST(β) except for Ɛ is placed in FOLLOW(B).
• If there is a production A -> αB, or a production A ->
αBβ where FIRST(β) contains Ɛ, then everything in
FOLLOW(A) is in FOLLOW(B).
 Constructing the Parsing Table :
First and Follow
Example: E  TE’
E’  +TE’ | є
T  FT’
T’  *FT’ | є
F  (E) | id

First(E) = First(T) = First(F) = {(, id}

First(E’) = {+, є}
First(T’) = {*, є}
Follow(E) = Follow(E’) = {),$}
Follow(T) = Follow(T’) = {+,),$}
Follow(F)={+,*,),$}

25
 Constructing the Parsing Table
• Algorithm for constructing a predictive parsing table:
1. For each production A  α of the grammar, do steps 2 and 3
2. For each terminal ‘a’ in First(α), add A  α to M[A, a]
3. If є is in First(α), add A  α to M[A, b] for each terminal b in
Follow(A). If є is in First(α) and $ is in Follow(A), add A
 α to M[A, $].
4. Make each undefined entry of M be an error.
 LL(1) Grammars
• A grammar whose parsing table has no multiply- defined
entries is said to be LL(1).
• First ‘L’ - Scanning input from left to right
• Second ‘L’ – Produces a leftmost derivation
• ‘1’ – use one input symbol at each step to make parsing decision.
• No ambiguous or left-recursive grammar can be LL(1).
• A grammar G is LL(1) iff whenever A -> α | β are two distinct
productions of G, then the following conditions hold:
– For no terminal 'a’ do both α and β derive strings beginning
with 'a'.
– At most one of α and β can derive the empty string.
– If β *=> є, then α does not derive any string beginning with
a terminal in Follow(A).
 Example:- S -> iEtSS’ | a
S’-> eS | Ɛ
E -> b