Compiler Design

Instructor: Worku.B
Email: workubacha340@gmail.com

Mattu University

Chapter 3: Syntax Analyzer

 Example of Top-down parser
Example 3
Example1: Consider The Grammar ✓ S→E+E
✓S→cAd ✓ E→E*E
✓A→ab|a ✓ E→E
✓And the input string w=cad. ✓ E→id
✓Example 2 Input---w=id*id+id
✓S→aABe
✓A→Abc/b
✓B→d
✓Input---w=abbcde
 Cont…
✓ top-down parsing technique parses the input, and starts
constructing a parse tree from the root node gradually moving
down to the leaf nodes.
✓ The types of top-down parsing are depicted below:
 Recursive Descent Parsing
❑ Recursive descent is a top-down parsing technique that constructs the
parse tree from the top and the input is read from left to right. It uses
procedures for every terminal and non-terminal entity.

❑ This parsing technique recursively parses the input to make a parse tree,
which may or may not require back-tracking.

❑ But the grammar associated with it (if not left factored) cannot avoid back-
tracking.

❑ A form of recursive-descent parsing that does not require any back-

tracking is known as predictive parsing.

❑ This parsing technique is regarded recursive as it uses context-free

grammar which is recursive in nature.
 Back-tracking
✓ Top- down parsers start from the root node (start symbol) and match the
input string against the production rules to replace them (if matched).
✓ To understand this, take the following example of CFG:

Example 1
S → rXd | rZd
X → oa | ea
Z → ai
For an input string: read, a top-down parser, will behave like this:
➢ It will start with S from the production rules and will match its yield to
the left-most letter of the input, i.e. The very production of S (S → rXd)
matches with it. So the to ‘r’. p-down parser advances to the next input
letter (i.e. ‘e’).
➢ The parser tries to expand non-terminal ‘X’ and checks its production
from the left (X → oa). It does not match with the next input symbol. So
the top-down parser backtracks to obtain the next production rule of X,
(X → ea).
✓ Now the parser matches all the input letters in an ordered
manner. The string is accepted.
Example 2 − Consider the Grammar
S→aAd
A→bc|b
✓ Make parse tree for the string abd. Also, show parse Tree when
Backtracking is required when the wrong alternative is chosen.
Solution
The derivation for the string abd will be −
S ⇒ a A d ⇒ abd (Required String)
If bc is substituted in place of non-terminal A then the string obtained will
be abcd.
S ⇒ a A d ⇒ abcd (Wrong Alternative)
Figure (a) represents S → aAd
Figure (a)

✓ Figure (b) represents an expansion of tree with production

✓ A → bc which gives string abcd which does not match with string
abd.

✓ So, it backtracks & chooses another alternative, i.e., A → b in

figure (c) which matches with abd.
Cont..
 Top-Down Parsing without Backtracking
✓ As backtracking looks more powerful by which we can select
different alternatives. But backtracking cannot be applied or
implemented so easily in parsing. There are two types of Top-
Down Parsing without Backtracking, which are as follows −
✓ LL Parser
✓ Predictive Parser
 Top-Down Parsing with Top-Down Parsing without
Backtracking Backtracking
The parser can try all alternatives in any The parser has to select correct
order till it successfully parses the alternatives at each step.
string.
Backtracking takes a lot of time, i.e., It takes less time.
exponential time to perform the
parsing.
A Grammar can have left recursion. Left Recursion will be removed before
doing parsing.
A lot of overhead will be there while It can run less overhead.
undoing things.
Information, once inserted, will be Information will not be removed.
removed from the symbol table while
backtracking.
It can be difficult to find where actually It can easy to find the location of the
error has occurred. error.
 Predictive Parser
✓ Predictive parser is a recursive descent parser, which has the
capability to predict which production is to be used to replace the
input string.

✓ The predictive parser does not suffer from backtracking.

✓ To accomplish its tasks, the predictive parser uses a look-ahead

pointer, which points to the next input symbols. To make the
parser back-tracking free, the predictive parser puts some
constraints on the grammar and accepts only a class of grammar
known as LL(k) grammar.
✓ Predictive parsing uses a stack and a parsing table to parse
the input and generate a parse tree.
✓ Both the stack and the input contains an end symbol $ to
denote that the stack is empty and the input is consumed.
✓ The parser refers to the parsing table to take any decision on
the input and stack element combination.
✓ In recursive descent parsing, the parser may have more than one
production to choose from for a single instance of input, whereas in
predictive parser, each step has at most one production to choose.
✓ There might be instances where there is no production matching the
input string, making the parsing procedure to fail.
 LL Parser
✓ An LL Parser accepts LL grammar. LL grammar is a subset of
context-free grammar but with some restrictions to get the
simplified version, in order to achieve easy implementation.
✓ LL grammar can be implemented by means of both algorithms
namely, recursive-descent or table-driven.
✓ LL parser is denoted as LL(k). The first L in LL(k) is parsing
the input from left to right, the second L in LL(k) stands for
left-most derivation and k itself represents the number of look
a heads.
✓ Generally k = 1, so LL(k) may also be written as LL(1).
 Cont…

❑ A grammar G is LL(1) if A → α | β are two distinct productions of G:

✓ for no terminal, both α and β derive strings beginning with a.
✓ at most one of α and β can derive empty string.
✓ if β → t, then α does not derive any string beginning with a terminal
in FOLLOW(A).
 Bottom-Up Parser
✓ Bottom-up parsing starts from the leaf nodes of a tree and works
in upward direction till it reaches the root node.
✓ Here, we start from a sentence and then apply production rules
in reverse manner in order to reach the start symbol.
✓ The image given below depicts the bottom-up parsers available.
 Shift-Reduce Parsing
✓ Shift-reduce parsing uses two unique steps for bottom-up parsing.
These steps are known as shift-step and reduce-step.
•Shift step: The shift step refers to the advancement of the input
pointer to the next input symbol, which is called the shifted symbol.
This symbol is pushed onto the stack. The shifted symbol is treated
as a single node of the parse tree.
•Reduce step : When the parser finds a complete grammar rule
(RHS) and replaces it to (LHS), it is known as reduce-step. This
occurs when the top of the stack contains a handle. To reduce, a POP
function is performed on the stack which pops off the handle and
replaces it with LHS non-terminal symbol.
 LR Parser
❖ The LR parser is a non-recursive, shift-reduce, bottom-up parser. It uses a
wide class of context-free grammar which makes it the most efficient syntax
analysis technique.
❖ LR parsers are also known as LR(k) parsers, where L stands for left-to-right
scanning of the input stream; R stands for the construction of right-most
derivation in reverse, and k denotes the number of lookahead symbols to
make decisions.
❖ There are three widely used algorithms available for constructing an LR
parser:
✓ SLR(1) – Simple LR Parser:
✓ Works on smallest class of grammar
✓ Few number of states, hence very small table
✓ Simple and fast construction
✓ LR(1) – LR Parser:
✓ Works on complete set of LR(1) Grammar
✓ Generates large table and large number of states
✓ Slow construction
✓ LALR(1) – Look-Ahead LR Parser:
• Works on intermediate size of grammar
• Number of states are same as in SLR(1)
LL vs. LR
 Bottom-up Approach
Example 1
✓S→aAcBe
Right most derivation:
✓A→Ab/b
aAcBe
✓B→d
aAcde Since ( ) B->d
✓Input---w=abbcde
aAbcde Since ( ) A→Ab
abbcde Since ( ) A->b
 Bottom-up Approach
Example 2 Right most derivation:

✓S→aABe aABe
✓A→Abc/b aAde Since ( ) B->d
aAbcde Since ( ) A→Abc
✓B→d abbcde Since ( ) A->b
✓Input---w=abbcde
 Bottom-up Approach

Example 3

Input=iad1+id2+id3
 Regular Expression Vs Context Free Grammar (CFG)
Context Free Grammar
✓ Language generated by Context Free Grammar is
accepted by Pushdown Automata
✓ It is a subset of Type 0 and Type 1 grammar and a
superset of Type 3 grammar.
✓ Also called phase structured grammar.
✓ Different context-free grammars can generate the same
context-free language.
✓ Classification of Context Free Grammar is done on the
basis of the number of parse trees.
✓ Only one parse tree->Unambiguous.
✓ More than one parse tree->Ambiguous.
 Regular Grammar
✓ It is accepted by Finite State Automata.
✓ It is a subset of Type 0 ,Type 1 and Type 2 grammar.
✓ The language it generates is called Regular
Language.
✓ Regular languages are closed under operations like
Union, Intersection, Complement etc.
✓ They are the most restricted form of grammar
Parameter Context Free Grammar Regular Grammar

Type Type-2 Type-3

Recognizer Push-down automata. Finite State Automata

Productions are of the form: Productions are of the form:

A->B; V –> VT / T (left-linear grammar)
Rules
A∈N(Non-Terminal) (or)
B∈V*(Any string) V –> TV /T (right-linear grammar)

Restriction Less than Regular Grammar More than any other grammar

The right-hand side of production has no The right-hand side of production should
Right-hand Side
restrictions. be either left linear or right linear.

Set Property Super Set of Regular Grammar Subset of Context Free Grammar

Intersection of two CFL need not be a

Intersection Intersection of two RG is a RG.
CFL

Complement They are not closed under complement Closed under complement

The range of languages that come under The range of languages that come under
Range
CFG is wide. RG is less than CFG.

Examples S –> AB;A –> a;B –> b S -> aS | bS | ∊

 What is Stack Implementation of Shift Reduce Parsing in
compiler design?
✓ Shift reduce parser is a type of bottom-up parser. It uses a stack to
hold grammar symbols.
✓ A parser goes on shifting the input symbols onto the stack until a
handle comes on the top of the stack. When a handle occurs on the
top of the stack, it implements reduction.
❑ There are the various steps of Shift Reduce Parsing which are as
follows −
➢ Step 1: It uses a stack and an input buffer.
➢ Step 2 : Insert $ at the bottom of the stack and the right end of
the input string in Input Buffer.
 Cont..
✓ Step 3 :Shift: Parser shifts zero or more input symbols
onto the stack until the handle is on top of the stack.
✓ Step 4: Reduce: Parser reduce or replace the handle
on top of the stack to the left side of production, i.e.,
R.H.S. of production is popped, and L.H.S is pushed.
✓ Step 4: Accept: Step 3 and Step 4 will be repeated
until it has identified an error or until the stack
includes start symbol (S) and input Buffer is empty,
i.e., it contains $.
 For example 1, consider the grammar
S → aAcBe
A → Ab|b
B→d
and the string is abbcde.

✓ It can reduce this string to S. It can scan string abbcde looking for the substring
that matches the right side of some production. The substrings b and d qualify.

✓ Let us select the left-most b and replace it with A, the left side of the production
A → b, and obtain the string aAbcde. It can identify that Ab, b, and d each
connect the right side of some production. Suppose this time it can select to
restore the substring Ab by A, the left side of the production A → Ab and it can
achieve aAcde.

✓ Thus replacing d by B, the left side of the production B → d, and can achieve
aAcBe. It can replace this string by S. Each replacement of the right-side of a
production by the left side in the process above is known as reduction.
Example 2 – Consider the grammar
E –> 2E2
E –> 3E3
E –> 4
Perform Shift Reduce parsing for input string “32423”.
 Reading Assignment

What is types of LR Parser in compiler design?

There are three types of LR Parsers which are as follows :

✓ Error Recovery
✓ Parser Generator
✓ Non-Recursive Predictive Parsing
 The end

Chapter 3