lOMoARcPSD|44828247

Module-4 notes - hjk

Automata Theory and Compiler Design (Visvesvaraya Technological University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Lakshmi B (smilekiller1003@[Link])
 lOMoARcPSD|44828247

Module -4
Pushdown Automata

The context free languages have a type of automaton that defines them. This
automaton, called a “pushdown automaton”, is an extension of the non-
deterministic finite automaton with ε-transitions, which is one of the ways to
define the regular languages. The pushdown automaton is essentially an ε-NFA
with the addition of a stack. The stack can be read, pushed, and popped only at
the top just like the “stack” data structure.

The Formal Definition of Pushdown Automata(2M):

The formal notation for a pushdown automaton (PDA) involves seven
components. We write the specification of a PDA P as follows:

P=(Q, ∑, Γ, δ, q0, Z0, F)

Where,
Q: A finite set of states, like the states of a finite automaton
∑: A finite set of input symbols, also analogous to the corresponding component
of a finite automaton.
Γ: A finite stack alphabet. It is the set of symbols that we are allowed to push onto
the stack.
δ: The transition function. Formally, δ takes as argument a triple δ(q, a, X),
where:
1. q is a state in Q.
2. a is either an input symbol in ∑ or a= ε, the empty string.
3. X is a stack symbol, that is, a member of Γ.

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

δ : QX{∑ U ε}X Γ→ Q X Γ*

q0: The start state.

Z0: The start symbol.
F: The set of accepting states or final states.

A Graphical Notation for PDA’s:

The transition function δ will explain the behavior of a PDA. It has following
components:

Example: Let us design a PDA P to accept the language L={wwR : w €{0,1}*}

We shall use a stack symbol Z0 to mark the bottom of the stack. We need to have
this symbol present so that, after we pop w off the stack and realize that we have
seen wwR on the input, we still have something on the stack to permit us to make
a transition to the accepting state, q2. Thus, our PDA for Lwwr can be described
as:

where δ is defined by the following rules:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Transition diagram is,

Figure 2: PDA for L={wwR : w €{0,1}*}

Instantaneous Descriptions of a PDA:

The PDA goes from configuration to configuration, in response to input symbols
(or sometimes ε ) but unlike the finite automaton, where the state is the only thing
that we need to know about the automaton, the PDA’s configuration involves
both the state and the contents of the stack. We shall represent the configuration
of a PDA by a triple (q,w,γ), where:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

1. q is the state,
2. w is the remaining input, and
3. γ is the stack contents

Such a triple is called an instantaneous description, or ID of the pushdown

automaton.
Example:
Let us consider the action of the PDA of Example L={wwR } on the input 1111.
Since q0 is the start state and Z0 is the start symbol, the initial ID is (q0,1111,Z0).
The IDs of the PDA are:

The Languages of a PDA:

We have assumed that a PDA accepts its input by consuming it and entering an
accepting state. We call this approach “acceptance by final state”. There is a
second approach to defining the language of a PDA that has important

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

applications. We may also define for any PDA the language “accepted by empty
stack”, that is, the set of strings that cause the PDA to empty its stack, starting
from the initial ID.
These two methods are equivalent, in the sense that a language L has a PDA that
accepts it by final state if and only if L has a PDA that accepts it by empty stack.
However, for a given PDA P, the languages that P accepts by final state and by
empty stack are usually different.

a) Acceptance by Final State

b) Acceptance by Empty Stack

Exercise:
1) Construct a PDA to accept the language L={wCwR :w€ {a,b}*}

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

The transition diagram of the PDA is,

2. Obtain a PDA to accept a string of balanced parenthesis. The parathesis

to be considered are (, ), [, ]. Ex: (( )), [( )( )],( ) ( )
Ans: The transition diagram for the given language is,

Therefore PDA P=(Q, ∑, Γ, δ, q0, Z0, F)

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Where,
Q={q0, q1}
∑={a,b}
Γ={(, [, Zo}
δ is as shown in the transition diagram.
q0 is the initial state
F={q1}

3. Construct a Pushdown automata to accept the language L={anbn :n>=1}.

Also show the IDs for the string w=aaabbb.

Given w=aaabbb. The IDs are:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

4. Construct a PDA to accept the language L={ w: w€ {a,b}* and

na(w)=nb(w)}.

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Let us trace the string w=abbbaa as follows:

Note: For more problems refer class work

From Empty Stack to Final State

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

From Final State to Empty Stack

Bottom-Up Parsing
A bottom-up parse corresponds to the construction of a parse tree for an input
string beginning at the leaves (the bottom) and working up towards the root (the
top). It is convenient to describe parsing as the process of building parse trees,
although a front end may in fact carry out a translation directly without building
an explicit tree. The sequence of tree snapshots in Fig. 4.25 illustrates a bottom-
up parse of the token stream id * id with respect to the arithmetic expression
grammar (4.1).

E→ E+T |T

T→T * F | F

F→ (E) | id (4.1)

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

The general style of bottom-up parsing is known as shift-reduce Parsing. The

grammar for which we can build shift-reduce parser is LR parser.

Reductions
• Bottom-up parsing as the process of “reducing” a string w to the start
symbol of the grammar.
• At each reduction step, a specific substring matching the body of a
production is replaced by the nonterminal at the head of that production.
• The key decisions during bottom-up parsing are about when to reduce and
about what production to apply, as the parse proceeds.
• We can also think that bottom-up parsing is a rightmost derivation.

• By definition, a reduction is the reverse of a step in a derivation. The goal

of bottom-up parsing is therefore to construct a derivation in reverse. The
following corresponds to the parse in Fig. 4.25:

E =>T =>T * F =>T * id => F * id => id * id

This derivation is in fact a rightmost derivation.

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Handle Pruning
Q. What is handle pruning. Explain with example. (5M)

Bottom-up parsing during a left-to-right scan of the input constructs a right-most

derivation in reverse. Informally, a “handle" is a substring that matches the body
of a production, and whose reduction represents one step along the reverse of a
rightmost derivation.

Example: Consider the string id1*id2, the handles during the parse of this string,
according to the expression grammar (4.1) are as in Fig. 4.26. Although T is the
body of the production E->T, the symbol T is not a handle in the sentential form
T *id2. If T were indeed replaced by E, we would get the string E * id2, which
cannot be derived from the start symbol E. Thus, the leftmost substring that
matches the body of some production need not be a handle.

Figure 4.26: Handles during a parse of id1*id2

Shift-Reduce Parsing
Q. What is Shift-reduce parsing? What are the actions of shift-reduce
parsing. Explain with example. (8M)

Shift-reduce parsing is a form of bottom-up parsing in which a stack holds

grammar symbols and an input buffer holds the rest of the string to be parsed. As
we shall see, the handle always appears at the top of the stack just before it is
identified as the handle.

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

We use $ to mark the bottom of the stack and also the right end of the input.
Conventionally, when discussing bottom-up parsing, we show the top of the stack
on the right, rather than on the left as we did for top-down parsing. Initially, the
stack is empty, and the string w is on the input, as follows:

STACK INPUT

$ w$

During a left-to-right scan of the input string, the parser shifts zero or more input
symbols onto the stack, until it is ready to reduce a string β of grammar symbols
on top of the stack. It then reduces β to the head of the appropriate production.
The parser repeats this cycle until it has detected an error or until the stack
contains the start symbol and the input is empty:

STACK INPUT

$S $

Upon entering this configuration, the parser halts and announces successful
completion of parsing.

Figure 4.28 steps through the actions a shift-reduce parser might take in parsing
the input string id1*id2 according to the expression grammar (4.1).

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

While the primary operations are shift and reduce, there are actually four possible
actions a shift-reduce parser can make: (1) shift, (2) reduce, (3) accept, and (4)
error.
1. Shift. Shift the next input symbol onto the top of the stack.
1. Reduce. The right end of the string to be reduced must be at the top
of the stack. Locate the left end of the string within the stack and
decide with what nonterminal to replace the string.
2. Accept. Announce successful completion of parsing.
3. Error. Discover a syntax error and call an error recovery routine.

Example 2): Consider the following grammar and input string “int id, id;”
S→ TL;
T→int | float
L→ L, id | id . Perform the shift-reduce parsing.

Stack Input Action

$ int id,id; $ shift
$int id, id ; $ Reduce by T→int
$T id, id ; $ shift
$T id , id ; $ Reduce L→id
$TL , id ; $ shift
$TL, id ; $ shift
$TL, id ;$ Reduc L→L,id
$T L ;$ shift
$ T L; $ Reduce S→TL;
$S $ Accept

Conflicts During Shift-Reduce Parsing

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Q. What are the conflicts of shift-reduce parsing? Explain with example.

(4M)

There are context-free grammars for which shift-reduce parsing cannot be used.
Every shift-reduce parser for such a grammar can reach a configuration in which
the parser, knowing the entire stack contents and the next input symbol,

i) Cannot decide whether to shift or to reduce (a shift/reduce conflict), or

ii) Cannot decide which of several reductions to make (a reduce/reduce
conflict).

Technically, these grammars are not in the LR(k) class of grammars; we refer to
them as non-LR grammars. The k in LR(k) refers to the number of symbols of
lookahead on the input. Grammars used in compiling usually fall in the LR(1)
class, with one symbol of lookahead at most.

Example: An ambiguous grammar can never be LR. For example, consider the
dangling-else grammar (4.14):

stmt → if expr then stmt

| if expr then stmt else stmt

| other

If we have a shift-reduce parser in configuration,

STACK INPUT

….if expr then stmt else……$

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

we cannot tell whether if expr then stmt is the handle, no matter what appears
below it on the stack. Here there is a shift/reduce conflict. Depending on what
follows the else on the input, it might be correct to reduce if expr then stmt to
stmt, or it might be correct to shift else and then to look for another stmt to
complete the alternative if expr then stmt else stmt.

Introduction to LR Parsing: Simple LR

The most prevalent type of bottom-up parser today is based on a concept called
LR(k) parsing; the “L" is for left-to-right scanning of the input, the “R" for
constructing a rightmost derivation in reverse, and the k for the number of input
symbols of lookahead that are used in making parsing decisions. The cases k = 0
or k = 1 are of practical interest.

Why LR Parsers?
LR parsing is attractive for a variety of reasons:
• LR parsers can be constructed to recognize virtually all programming-
language constructs for which context-free grammars can be written.
• The LR-parsing method is the most general nonbacktracking shift-reduce
parsing method known, yet it can be implemented as efficiently as other, more
primitive shift-reduce methods.
• An LR parser can detect a syntactic error as soon as it is possible to do so on
a left-to-right scan of the input.
• The class of grammars that can be parsed using LR methods is a proper
superset of the class of grammars that can be parsed with predictive or LL
methods.

Items and the LR(0) Automaton

How does a shift-reduce parser know when to shift and when to reduce?

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

• An LR parser makes shift-reduce decisions by maintaining states to keep

track of where we are in a parse. States represent sets of “items."
• An LR (0) item (item for short) of a grammar G is a production of G with
a dot at some position of the body. Thus, production A->XYZ yields the
four items:
A→.XY Z
A→X.Y Z
A→XY.Z
A→XY Z.
The production A→ε generates only one item, A→.
• Intuitively, an item indicates how much of a production we have seen at a
given point in the parsing process.
• One collection of sets of LR(0) items, called the canonical LR(0)
collection, provides the basis for constructing a deterministic finite
automaton that is used to make parsing decisions. Such an automaton is
called an LR(0) automaton.
• To construct the canonical LR (0) collection for a grammar, we define an
augmented grammar and two functions, CLOSURE and GOTO.
• If G is a grammar with start symbol S, then G’, the augmented grammar
for G, is G with a new start symbol S’ and production S’→S. The purpose
of this new starting production is to indicate to the parser when it should
stop parsing and announce acceptance of the input. That is, acceptance
occurs when and only when the parser is about to reduce by S’→S.

Closure of Item Sets

If I is a set of items for a grammar G, then CLOSURE(I) is the set of items
constructed from I by the two rules:
• Initially, add every item in I to CLOSURE(I).

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

• If A→α.Bβ is in CLOSURE(I) and B→γ is a production, then add the item

B→.γ to CLOSURE(I), if it is not already there. Apply this rule until no
more new items can be added to CLOSURE(I).

The set items are divided into 2 classes: Kernel items and Non-kernel items:

The Function GOTO:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

The algorithm to construct C, the canonical collection of sets of LR(0) items

for an augmented grammar G’ is:

Example: Find LR(0) items for the arithmetic expression grammar,

E→E+T | T
T→T * F | F
F→(E) |id
Also construct the LR(0) automata.
Solution:
Step 1: Consider the augmented grammar for the given grammar,
E’→E
E→E+T | T
T→T * F | F
F→(E) |id
Step 2: If I is the set of one item{[E’ →.E]}, then closure(I) contains the set of
items I0 :
E’→.E
E→.E+T
E→.T
T→T * F
T→ .F

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

F→(E)
F→.id
Step 3:The canonical LR(0) items are generated by finding the GOTO and
the LR(0) Automata is represented as follows:

Use of the LR(0) Automaton:

Let us use LR(0) automata along with a stack to parse the string “id * id” as
follows:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Constructing SLR-Parsing Tables

The SLR method begins with LR(0) items and LR(0) automata. That is, given a
grammar, G, we augment G to produce G’, with a new start symbol S’. From G’,
we construct C, the canonical collection of sets of items for G’ together with the
GOTO function.
The ACTION and GOTO entries in the parsing table are then constructed using
the following algorithm. It requires us to know FOLLOW(A) for each
nonterminal A of a grammar.
Algorithm : Constructing an SLR-parsing table.
INPUT: An augmented grammar G’.
OUTPUT: The SLR-parsing table functions ACTION and GOTO for G’.
METHOD:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

• The parsing table consisting of the ACTION and GOTO functions

determined by the above Algorithm is called the SLR(1) table for G.
• An LR parser using the SLR(1) table for G is called the SLR(1) parser for
G, and
• A grammar having an SLR(1) parsing table is said to be SLR(1).

Note: We usually omit the “(1)" after the “SLR," since we shall not deal here with
parsers having more than one symbol of lookahead.

Example: Construct the SLR parsing table for the arithmetic expression
grammar.

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Solution: To construct SLR parsing table, we will number the productions

as follows:
1) E→E+ T
2) E→T
3) T→T * F
4) T→F
5) F→(E)
6) F→id
SLR table construction starts with finding Canonical item sets or LR(0) sets
from the augmented grammar.

Then the SLR parsing table is:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

The codes for the actions are:

1) si means shift and stack state i,
2) rj means reduce by the production numbered j,
3) acc means accept,
4) blank means error.

The model of LR Parser:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

LR-parsing Algorithm:
INPUT: An input string w and an LR-parsing table with functions ACTION and

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

GOTO for a grammar G.

OUTPUT: If w is in L(G), the reduction steps of a bottom-up parse for w;
otherwise, an error indication.
METHOD: Initially, the parser has s0 on its stack, where s0 is the initial state,
and w$ in the input buffer. The parser then executes the following program:

Now let us parse the string id*id+id using SLR parsing table as follows:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Ex: 2)For the given grammar construct SLR parsing table.

Ans: The lR(0) items are:

STATE ACTIONS GOTO

id = * $ s l r
0 s5 s4 1 2 3
1 accept
2 s6/r5 r5
3 r2
4 s5 s4 8 7
5 r4 r4
6 s5 s4 8 9
7 r3 r3
8 r5 r5
9 r1

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Since we got conflict for the state 2 on input symbol = as s6/r5 the given grammar
is not SLR.

Viable Prefixes:
The prefixes of right sentential forms that can appear on the stack of a shift-
reduce parser are called viable prefixes. They are defined as follows: a viable
prefix is a prefix of a right-sentential form that does not continue past the right
end of the rightmost handle of that sentential form. By this definition, it is always
possible to add terminal symbols to the end of a viable prefix to obtain a right-
sentential form.
Example:
Consider the CFG:
E -> E + T | T
T -> T * F | F
F -> id
Let w = id * id (input string)
Here is the trace of the shift-reduce parsing algorithm:
STACK INPUT ACTION
$ id * id$ shift
$ id * id$ reduce
$F * id$ reduce
$T * id$ shift
$T * id$ shift
$T * id $ reduce
$T * F $ reduce
$T $ reduce
$E $ Accept
We observe that at any point of time, the stack contents must be a prefix of a right
sentential form. However, not all prefixes of a right sentential form can appear on

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

the stack. For example, consider the rightmost derivation: E -> T -> T * F -> T *
id -> F * id -> id * id Here, ‘id *’ is a prefix of a right sentential form. But it can
never appear on the stack! This is because we will always reduce by F -> id before
shifting ‘*’.
More Powerful LR Parsers
In this section, we shall extend the previous LR parsing techniques to use one
symbol of lookahead on the input. There are two different methods:

1. The “canonical-LR" or just “LR" method, which makes full use of the
lookahead symbol(s). This method uses a large set of items, called the LR(1)
items.
2. The “lookahead-LR" or “LALR" method, which is based on the LR(0) sets
of items, and has many fewer states than typical parsers based on the LR(1) items.
By carefully introducing lookaheads into the LR(0) items, we can handle many
more grammars with the LALR method than with the SLR method, and build
parsing tables that are no bigger than the
SLR tables.

Canonical LR(1) Items:

• It is possible to carry more information in the state of SLR parser that will
allow us to rule out some of the invalid reductions by A->α.
• The extra information is incorporated into the state by redefining items to
include a terminal symbol as a second component. The general form of an
item becomes [A->α.β; a], where A-> αβ is a production and a is a
terminal or the right endmarker $.
• We call such an object an LR(1) item.
• The 1 refers to the length of the second component, called the lookahead
of the item.

Constructing LR(1) Sets of Items:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Example:
Let us find LR(1) items for the grammar given below:
S ->C C
C ->c C | d

Ans:
Consider the augmented grammar of the given grammar.
S’-> S
S ->C C
C ->c C
C->d

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

GOTO(I0 , S): I1
S→S. , $

GOTO(I0 , C): I2
S→C.C, $
C→.cC, $
C→.d, $
GOTO(I0 , c) : I3
C→c.C, c/d
C→.cC, c/d
C→d, c/d
GOTO(I0 , d): I4
C→d. c/d
GOTO(I2 , C): I5
S→CC. , $
GOTO(I2 , c): I6
C→c.C, $
C→.cC, $
C→.d, $
GOTO(I2 , d): I7
C→d. , $
GOTO(I3 , C): I8
C→cC, c/d
GOTO(I3 , c): I3
GOTO(I3 , d): I4
GOTO(I6 , C): I9
C→cC., $

GOTO(I6 , c): I6
GOTO(I6 , d) :I7

Canonical LR(1) Parsing Tables:

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

The CLR parsing table for the given grammar is,

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

Constructing LALR Parsing Tables:

• This method is often used in practice, because the tables obtained by it are
considerably smaller than the canonical LR tables, yet most common
syntactic constructs of programming languages can be expressed
conveniently by an LALR grammar. The same is almost true for SLR
grammars, but there are a few constructs that cannot be conveniently
handled by SLR techniques.
• For a comparison of parser size, the SLR and LALR tables for a grammar
always have the same number of states, and this number is typically several
hundred states for a language like C. The canonical LR table would
typically have several thousand states for the same-size language. Thus, it
is much easier and more economical to construct SLR and LALR tables
than the canonical LR tables.
•

From the previous grammar LR(1) items, As we mentioned, there are three pairs
of sets of items that can be merged. I3 and I6 are replaced by their union:
I36 : C→c.C, c/d/$
C→.cC, c/d/$
C→.d, c/d/$

I4 and I7 replaced by their union:

I47 : C→d. , c/d/$

and I8 and I9 are replaced by their union:

I89 : C→cC. , c/d/$

Downloaded by Lakshmi B (smilekiller1003@[Link])

 lOMoARcPSD|44828247

********

Downloaded by Lakshmi B (smilekiller1003@[Link])