compiler Lec05

Lecture 5
Compilers
Principle ,Techniques, and Tools
With My Best Wishes 20
Syntactic Analyzer ( Parser )
Every programming language has rules that prescribe the
syntactic structure of well formed programs. The syntax of
programming language constructs can be described by context
free grammars. In syntax analysis we are concerned with
groping tokens into larger syntactic classes such as expression ,
statements , and procedure. The syntax analyzer (parser) outputs
a syntax tree, in which its leaves are the tokens and every nonleaf node represents a syntactic class type. For example:-
Consider the following grammars:-
Then the parse tree for -(id+id) is:-
E
- E
( E )
E + E
 

Often much of the error detection and recovery in a
compiler is central around the parser. One reason of this is that
many errors are syntactic in nature. Errors where the token
stream violates the structure of the language are determined by
parser, such as an arithmetic expression with unbalanced
parentheses.
E E+E E*E (E) -E id
University of Al-MAARIF, Col. of Sciences
Esam & Sameeh
Compilers
Principle ,Techniques, and Tools
With My Best Wishes 21
Derivations :-
This derivational of view gives a precise description of the
top-down construction of parse tree. The central idea here is that
a production is treated as rewriting rule in which the
nonterminal on the left is replaced by the string on the right side
of the production. For example, consider the following
grammar:
E E+E
E E*E
E (E)
E -E
E id
The derivation of the input string id + id* id is:
 

Note:- parse tree may by viewed as a graphical representation
for a derivation :
E
E + E
id E * E
id id
University of Al-MAARIF, Col. of Sciences
Esam & Sameeh
Compilers
Principle ,Techniques, and Tools
With My Best Wishes 22
Ambiguity :-
A grammar that produce more that one parse tree for same
sentence is said to be Ambiguous. In the another way, by
produced more that one left-most derivation or more that one
Right-most derivation for the same sentence.
E
E + E
id E * E
id id
(1)
E
E * E
E + E id
id id
(2)
two parse tree for id+id*id
E E
E+E E*E
id+E E+E*E
id+E*E id+E*E
id*id*E id+id*E
id+id*id id+id*id
(1) (2)
Two left-most derivations for id+id*id
University of Al-MAARIF, Col. of Sciences
Esam & Sameeh
Compilers
Principle ,Techniques, and Tools
With My Best Wishes 23
Sometimes am ambiguous grammar can be rewritten to
eliminate the ambiguity. Such as:
E E+E E E+T T
E E*E E (E)
E (E) E -E
E -E T T*F F
E id F id
E
E + T
T T * F
F F id
 

Left-Recursion :-
A grammar is left-recursion if has a nonterminal A such
that there is a derivation A Aα for some string α . Topdown parser cannot handle left-recursion grammars, so a
transformation that eliminates left-recursion is needed:
A → Aα ß
A → ß A'
A' → αA' ε
OR:
University of Al-MAARIF, Col. of Sciences
Esam & Sameeh
Compilers
Principle ,Techniques, and Tools
With My Best Wishes 24
A→Aα1 Aα2 … Aαm … ß1 ß2 … ßn
A→ ß1A' ß2 A' … ßn A'
A'→ α1 A' α2 A' … αmA' ε .
Example:
E→ E+T T
T→ T*F F
F→ (E) id
E→ T E'
E' → +T E' ∊
T→ FT'
T'→ *F T' ∊
F→ (E) id
Left-Factoring :-
The basic idea is that when is not clear which of two
alternative production to use to expand a nonterminal A . We
may be able to rewrite the A-productions to defer the decision
until we have seen enough of the input to make the right choice.
A→ α ß1 α ß2 where α ≠ ∊
A→ α A'
A'→ß1 ß2
University of Al-MAARIF, Col. of Sciences
Esam & Sameeh
Compilers
Principle ,Techniques, and Tools
With My Best Wishes 25
Easy Come , Easy Go
OR :-
A→ α ß1 α ß2 .. α ßn γ where α ≠ ∊
A→ α A' γ
A'→ ß1 ß2 .. ßn
Example:
S→ iEtS iEtSeS a
E→b
S → iEtSS' a
S' → eS ∊
E→ b
University of Al-MAARIF, Col. of Sciences
Esam & Sameeh