Chapter Three: Syntax Analysis

Outlines:
✓ The Role of the Parser
✓ Grammars
✓ Chomsky Hierarchy
✓ Parse Tree
✓ Reduction of CFGs
✓ Issues of CFG for the Programming Languages
✓ Pushdown Machines
Compiler Design Dr. Salah Eldin Shaban
1
Objectives
❑ This chapter presents the basic concepts of parsing.
❑ Formal methods to specify and construct the syntax analysis.

➢ Introduce the concept of a formal grammar as a means of:

✓ Specifying the programming language
✓ Implementing the syntax analysis phase.

Compiler Design Dr. Salah Eldin Shaban 2

The Role of the Parser
❑ Syntax analyzer (Parser) or Hierarchical analyzer.
❑ A Parser
✓ Implements the source language grammar.
✓ Obtains a stream of tokens from the scanner.
✓ Verifies that the stream can be generated by the grammar.
✓ Report any syntax errors in an intelligible fashion.
✓ Recover from commonly occurring errors.
✓ Constructs a parse tree and passes it to the rest of the compiler.
❑ The grammar that a parser implements is called a Context
Free Grammar or CFG.
Compiler Design Dr. Salah Eldin Shaban 3
 The Role of the Parser Cont.

❑ Three general types of parsers are universal, top-down, and bottom-up.

✓ Universal parsing methods can parse any grammar but too inefficient.
✓ The top-down or bottom-up methods are commonly used.

Compiler Design Dr. Salah Eldin Shaban 4

 The Role of the Parser Cont.
❑ The role of the parser is twofold:
✓ To check syntax (= string recognizer) and report syntax errors accurately.
❑ To invoke semantic actions
✓ For static semantics checking, e.g. type checking of expressions,
functions, etc.
❑ The difference between Syntax and Semantic is:
✓ Syntax is the way in which we construct sentences by following
principles and rules.
✓ Semantics is the interpretations of and meanings derived from the
sentence transmission and understanding of the message or in other
words are the logical sentences making sense or not.

Compiler Design Dr. Salah Eldin Shaban 5

The Role of the Parser Cont.
❑ If there are no syntax errors, the output of parser is a stream
of atoms or syntax trees.
✓ An atom is a primitive operation which can be implemented

using only a few machine language instructions.

✓ Each atom includes operands which are ultimately converted to
memory addresses on the target machine.
❑ A syntax tree is a data structure in which the interior nodes
represent operations, and the leaves represent operands.
❑ The syntax directed translation process is not only checking
for proper syntax but producing output as well.
Compiler Design Dr. Salah Eldin Shaban 6
Grammars
❑ Every programming language has precise rules that prescribe the
syntactic structure of well-formed programs.
❑ Grammars offer significant benefits for language designers and
compiler writers.
✓ A grammar gives a precise syntactic specification of a programming
language.
✓ Automatically, we can construct an efficient parser that determines
the syntactic structure of a source program.
✓ The designed grammar is useful for translating source
programs into correct object code and for detecting errors.

Compiler Design Dr. Salah Eldin Shaban 7

Grammars Cont.
✓ A grammar allows a language to be evolved or developed
iteratively, by adding new constructs to perform new tasks.
▪ By follow the grammatical structure of the language.

❑ There are some concepts of formal language theory which the

student must understand.
✓ A language is a set of strings from a specific alphabet.
✓ Ways of formally specifying a language are:
▪ Regular expressions

▪ Finite Automata (FAs) or Finite State Machines (FSMs)

▪ Grammars

Compiler Design Dr. Salah Eldin Shaban 8

Grammars Cont.
❑ A grammar is a list of rules which can be used to produce or
generate all the strings of a language, and which does not
generate any strings which are not in the language.
❑ Mathematically, a grammar is defined as a 4-tuple;

G: (S, N, P, S)
✓ S is a finite set of characters, called the input alphabet, the input
symbols, or terminal symbols.
✓ N is a finite set of symbols, distinct from the terminal symbols,
called non-terminal symbols (grammar variables).

Compiler Design Dr. Salah Eldin Shaban 9

Grammars Cont.
✓ P is a finite list of rewriting rules, also called productions, which
define how strings in the language may be generated. Each of
these rewriting rules is of the form  → , where  and  are
arbitrary strings of terminals and non-terminals, and  is not null.

✓ S is a particular non-terminal called the goal symbol, which

represents exactly all the strings in the language. part of N

✓ The set of terminals and non-terminals is called the vocabulary

of the grammar.

Compiler Design Dr. Salah Eldin Shaban 10

Grammars Cont.
❑ The following symbols will have particular meanings:
A, B, C, . . . a single non-terminal.
a, b, c, . . . a single terminal.
. . ., X, Y, Z a single terminal or non-terminal.
. . ., x, y, z a string of terminals.
, , g, . . . a string of terminals and non-terminals.
Thus, a generic production can be written as A → 
✓ Terminals: Lower case letters, operator symbols, punctuation

symbols, digits, boldface strings are all terminals.

✓ Non-Terminals: Upper case letters, lower case italic names are
usually non terminals.

Compiler Design Dr. Salah Eldin Shaban 11

Grammars Cont.
✓ The starting non-terminal is always S unless otherwise specified.
✓ For reference purposes, each of the grammars shown will be
numbered (G1, G2, G3, ...).
❑ If G is a grammar, the language specified by G is L(G).
❑ For example, let production for any grammar are:

S →aSa
S →bSb
S →c
G: (S, N, P, S)
S = {a, b, c} N = {S}
P = {S → a S, S → b S b, S → c } S = S
Compiler Design Dr. Salah Eldin Shaban 12
Grammars Cont.
❑ The most common way of specifying productions is called
Backus-Naur Form (BNF)
✓ non-terminals are enclosed in angle brackets ‹ ›,
✓ The arrow is replaced by a ::= as: ‹ S › ::= a ‹ S › b which is the BNF
version of the grammar rule: S → a S b
❑ So, in BNF, productions have the form
left side → definition
where left side  (S Ս N) * and definition  (S Ս N) *
❑ For left side contains one non-terminal, left side ∩ N = ϕ.

Compiler Design Dr. Salah Eldin Shaban 13

Grammars Cont.
❑ For multiple definitions of one non-terminal, production rules
are abbreviated by listing the definitions as a set of one or
more alternatives, separated by a vertical bar symbol "|".
❑ For example, ‹ S › ::= a ‹ S › b | e which is the BNF version of
two grammar rules: S → a S b, S → e.
❑ Let production for any grammar are:
S →aSa
S →bSb
S →c
can represented as: S → a S a | b S b | c
Compiler Design Dr. Salah Eldin Shaban 14
Chomsky Hierarchy
❑ Noam Chomsky defined four levels of grammars according to
complexity and the corresponding four classes of automata or
abstract machine types have been identified.

Chomsky
Grammar Recognizer
Language Class
3 Regular Finite State Automaton
2 Context-Free Push-Down Automaton
1 Context-Sensitive Linear-Bounded Automaton
0 Unrestricted Turing Machine

Compiler Design Dr. Salah Eldin Shaban 15

Chomsky Hierarchy Cont.
❑ 0. Unrestricted grammar is one in which there are no
restrictions on the rewriting rules. Each production rule on the
form  →  where  and  are arbitrary string of grammar
symbols with  ≠ e.
❑ 1. Context-Sensitive grammar is one in which each rule must
be of the form:  A g →   g where , , and g are any
string of terminals and non-terminals (including e), and A
represents a single non-terminal.  is at least as long as  that
is clearly |  | ≤ |  |

Compiler Design Dr. Salah Eldin Shaban 16

Chomsky Hierarchy Cont.
❑ 2. Context-Free Grammar (CFG) is one in which each rule
must be of the form: A →  where A represents a single non-
terminal and  is any string of terminals and non-terminals (A ϵ
N and  ϵ (S Ս N)*).
❑ 3. Regular Grammar - If all production rules of a CFG are of
the form: A → wB or A → w where A and B are non-terminals
and w ϵ S*, then we say that is a right linear grammar. If all
production rules of a CFG are of the form: A → Bw or A → w,
we call it a left linear grammar.

Compiler Design Dr. Salah Eldin Shaban 17

Chomsky Hierarchy Cont.
❑ Every context-sensitive grammar is in the unrestricted class.
❑ Every CFG is in the context-sensitive and unrestricted classes.
❑ Every regular grammar is in the context-free, context-sensitive,
and unrestricted classes.

Compiler Design Dr. Salah Eldin Shaban 18

Chomsky Hierarchy Cont.
❑ A grammar G is said to be
✓ Regular if it is right linear where each production is of the form
A→wB or A→w
or left linear where each production is of the form
A→Bw or A→w
✓ Context-free if each production is of the form A → 
where A  N and   (N  S)*
✓ Context sensitive if each production is of the form
A→g
where A  N, , g,   (N  S)*, |g| > 0
✓ Unrestricted

Compiler Design Dr. Salah Eldin Shaban 19

 Chomsky Hierarchy Cont.
❑ L(regular)  L(context free)  L(context sensitive)  L(unrestricted)
✓ Where L(T) = {L(G)|G is of type T} That is: the set of all languages
generated by grammars G of type T.
❑ Examples:
✓ Every finite language is regular! (construct a FSA for strings in L(G))
✓ L1 = { anbn | n  1 } is context free G1:
✓ L2 = { anbncn | n  1 } is context sensitive
✓ G1 is an example of a context-sensitive grammar.

Compiler Design Dr. Salah Eldin Shaban 20

 Derivation
❑ A derivation is a sequence of rewriting rules, applied to the
starting non-terminal, ending with a string of terminals.
✓ It demonstrates that a particular string is a member of the language.
✓ Assuming S is the starting non-terminal, derivations are written as:
✓ , , and g are strings of terminals and/or non-terminals, and x is a
string of terminals. Sg…x
❑ The one-step derivation is defined by  A    g 
where A → g is a production in the grammar
❑ The language generated by G is defined by
L(G) = {w  T* | S + w}
Compiler Design Dr. Salah Eldin Shaban 21
Derivation Cont.
❑ A sentential form is the goal or start symbol, or any string that
can be derived from it, that is any string w such that S w
where w  (S  N) *
❑ A recursive grammar permits derivations of the form
A w1 A w2 (where A  N and w1 and w2  (S  N) *)
❑ It is a left recursive if A A w and right recursive if A wA
❑ A self-embedding grammar permits derivations of the form

A w1 A w2 (where A  N and w1 and w2  (S  N) *)

but where w1 or w2 contains at least one terminal that is (w1 ∩ S) Ս
(w2 ∩ S ) ≠ ϕ.

Compiler Design Dr. Salah Eldin Shaban 22

Derivation Cont.
❑ In addition, we define
 is leftmost lm if  does not contain a nonterminal
 is rightmost rm if  does not contain a nonterminal
Transitive closure * (zero or more steps)
Positive closure + (one or more steps)
❑ Grammar G = ({+,*, (, ), -, id}, {E}, P, E) with
Productions P=E→E+E
E→E*E
E→(E)
E→-E
E → id
Compiler Design Dr. Salah Eldin Shaban 23
Derivation Cont.
❑ Example derivations:
E  - E  - id
E rm E + E rm E + id rm id + id
E * E
E * id + id
E + id * id + id

Compiler Design Dr. Salah Eldin Shaban 24

Derivation Cont.
❑ Example 1: G2 consists of: G2:
✓ Four rules, the terminal symbols {0, 1}, and
✓ The starting non-terminal S.
✓ An example of a derivation using G1 is:

✓ Thus, 0010100 is in L(G1).

✓ G2 specifies language of palindromes of odd length over the
alphabet {0,1}.
✓ A palindrome is a string which reads the same from left to right as it
does from right to left.
L(G1) = {0, 1, 000, 010, 101, 111, 00000, . . . }

Compiler Design Dr. Salah Eldin Shaban 25

Derivation Cont.
❑ Example 2: G3 consists of: G3:
✓ Four rules, the terminal symbols {a, b}, and
✓ e is not a terminal symbol.
✓ The starting non-terminal S.
✓ An example of a derivation using G3 is:
S  ASB  aSB  aASBB  aaSBB  aaBB  aabB  aabb
✓ Thus, aabb is in L(G2).
✓ G3 specifies the set of all strings of a's and b's which contain the same
number of a's as b's and in which all the a's precede all the b's.
L(G2) = {e, ab, aabb, aaabbb, aaaabbbb, aaaaabbbbb, . . . }
= {anbn} such that n greater than or equal to zero.
✓ G3 language is the set of all strings of a's and b's which consist of zero or
more a's followed by exactly the same number of b's.

Compiler Design Dr. Salah Eldin Shaban 26

 Derivation Cont.
❑ Two grammars, G1 and G2, are said to be equivalent if L(G1)
= L(G2) – i.e., they specify the same language.
❑ In the following grammar, there can be several different
derivations for a particular string e.g.

S  aSA  aBAA  abAAA  ababAA  abababA  abababab

S  aSA  aSab  aBAab  aBabab  abAabab  abababab
S  BA  bAA  babA  babab

Compiler Design Dr. Salah Eldin Shaban 27

Derivation Cont.
❑ Let a grammar with productions E → E + E | E ∗ E | x | y | z
A leftmost derivation of x + y ∗ z is:
E E+E x+E x+E∗E x+y∗E x+y∗z
A rightmost derivation of x + y ∗ z is:
E E+E E+E∗E E+E∗z E+y∗z x+y∗z
Another leftmost derivation of x + y ∗ z is:
E E∗E E+E∗E x+E∗E x+y∗E x+y∗z
The following is neither left- nor rightmost:
E E+E E+E∗E E+y∗E x+y∗E x+y∗z

Compiler Design Dr. Salah Eldin Shaban 28

 Parse Tree
❑ A derivation/parse tree is a pictorial representation of a
derivation.
✓ The root of the tree is labeled by the start symbol
✓ Each leaf of the tree is labeled by a terminal (=token) or e in the
derived string.
✓ Each interior node is labeled by a non-terminal in a sentential
form.
✓ If A → X1 X2 … Xn is a production, then node A has immediate
children X1, X2, …, Xn where Xi is a (non)terminal or e
✓ A parse tree for the string aaabbb using G3 is:

Compiler Design Dr. Salah Eldin Shaban 29

 Parse Tree Cont.
❑ The yield of a parse tree is the
concatenation of its leaves from
left to right.
❑ The yield is always a string that
is derived from the root node.
❑ The yield is a terminal string
labelled from S Ս {e}.

Compiler Design Dr. Salah Eldin Shaban 30

Reduction of CFGs
❑ There are several ways to restrict the format of CFG
without reducing the language generation power of CFG.
❑ Let L be a non-empty context free language generated by a
CFG with elimination of:
1. Useless symbols, those terminals or non-terminals that
do not appears in any derivation of a terminal string from
the start symbol.
2. Unit productions, those of the form X → Y for some non-
terminals X and Y.
3. e-productions, those of the form X → e for some non-
terminal X.

Compiler Design Dr. Salah Eldin Shaban 31

Elimination of Useless Production/Symbols from CFG
❑ Any symbol is useful only when it is deriving any terminal
and if a symbol is deriving a terminal but not reachable from
start state.
❑ All terminals will be useful symbols.
❑ A symbol that is useful will be both generating and reachable.
❑ For example: Find the reduced grammar that is equivalent to
G4 G4: 1. S → S B | a C
2. A → b S C a
3. B → a S B | b B C
4. C → a B C | a d

Compiler Design Dr. Salah Eldin Shaban 32

Elimination of Useless Production/Symbols from CFG Cont.
Solution:
1. Since C → a d, C is a generating symbol and
2. Since S → a C, S is also a generating symbol.
3. According to the production A → b S C a, A is also a generating
symbol.
4. Right side of B → a S B and B → b B C contains B, and B is not
terminating, so B is not a generating symbol.
5. So, we can eliminate those productions and grammar becomes:
G4: 1. S → a C
2. A → b S C a
3. C → a d
Compiler Design Dr. Salah Eldin Shaban 33
Elimination of Useless Production/Symbols from CFG Cont.
Solution:
Since S is the start symbol and right side of S does not contain A,
hence A is not reachable as:

So, by eliminating A we get

G4: 1. S → a C
2. C → a d

which is reduced grammar equivalent to the given grammar,

containing no useless symbol.

Compiler Design Dr. Salah Eldin Shaban 34

Eliminating Unit Productions
❑ A unit production in a CFG is a production of the form:
Non -terminal → One non-terminal (A → B)
Eliminate unit productions Algorithm:
While (there exist a unit production A → B)
{
Select a unit production, such that there exist a production
B → a, where a is a terminal.
for (every non-unit production, B → a)
add production A → a to the grammar.
Eliminate A → B from the grammar
}
Compiler Design Dr. Salah Eldin Shaban 35
 Eliminating Unit Productions Cont.
❑ Example: Remove the unit productions from G5:
❑ Solution: There are three-unit productions in the grammar (I)
G5: I II
1. S → A B
3. B → C G5: 1. S → A B
2. A → a
4. C → D 2. A → a
3. B → C | b
5. D → E 3. B → a | b
4. C → D
4. C → a
5. D → E III
5. D → a
6. E → a G5: 1. S → A B
6. E → a
2. A → a
3. B → a | b

Compiler Design Dr. Salah Eldin Shaban 36

Eliminating Unit Productions Cont.
❑ For D → E there is E → a so, add D → a to G5 and delete
D → E from G5.
❑ Also, C → D so, add C → a to G5 and delete C → D from
G5.
❑ Similarly, B → C by adding B → a and removing B → C
So, the final grammar free of unit productions as in (II).
❑ See C, D and E are unreachable symbols. So, to get a
completely reduced grammar, remove them from G5. The
final G2 is in (III).

Compiler Design Dr. Salah Eldin Shaban 37

Eliminate e-Productions
❑ Null productions are of the form A → e.
❑ All e-productions cannot be removed from a grammar if the
language contains e as a word, but if it does not remove all.
❑ In each CFG, a non-terminal N is nullable if there is a production
N → e or there is a derivation that starts at N and leads to e :
N ... e
❑ If A → e is an eliminated production, look for all productions
whose right side contains A, and replace each occurrence of A in
each of these productions to obtain the non e-productions.
❑ Add the resultant non e-productions to the grammar to keep the
language the same.

Compiler Design Dr. Salah Eldin Shaban 38

Eliminate e-Productions Cont.
❑ Example: Remove the null productions from G6:
❑ Solution:
There are two null productions in the grammar A → e and B → e.
To eliminate A → e must change the productions containing A in the
right side. Those productions are S → A B A C and A → a A
So, replace each occurrence of A by e. Four new productions are in (I)
G6: 1. S → A B A C
1. S → B A C | A B C | B C
2. A → a A | e
2. A → a
3. B → b B | e
4. C → c
I

Compiler Design Dr. Salah Eldin Shaban 39

 Eliminate e-Productions Cont.
❑ Add these productions to the grammar and eliminate A → e (II).

G6: 1. S → A B A C | B A C | A B C | B C
1. S → A A C | A C | C
2. A → a A | a 2. B → b
3. B → b B | e
III
4. C → c
II

❑ To eliminate B → e, change the productions containing B on the

right side. Doing that generate new productions in (III).

Compiler Design Dr. Salah Eldin Shaban 40

Eliminate e-Productions Cont.
❑ Add these productions to the grammar and remove the
production B → e from the grammar.
❑ The new grammar after removal of e-productions is:
G6: 1. S → A B A C | A B C | B A C | B C | A A C | A C | C

2. A → a A | a
3. B → b B | b
4. C → c

Compiler Design Dr. Salah Eldin Shaban 41

Issues of CFGs
❑ Writing Issues of a CFG include:
✓ Ambiguity, Left Recursion, and Left Factoring
✓ For example, consider a CFG of arithmetic expressions:
G7:
1. Expr → Expr + Expr
2. Expr → Expr * Expr
3. Expr → ( Expr )
4. Expr → var
5. Expr → const
✓ This is an ambiguous grammar and should be avoided.
Compiler Design Dr. Salah Eldin Shaban 42
Ambiguity
❑ In natural languages, ambiguous phrases are those which
may have more than one interpretation.
❑ A CFG is ambiguous if there is more than one
derivation tree for a particular string.
❑ There are two different derivation trees for the string
var + var * var using grammar G7
❑ One way to resolve an ambiguity is to rewrite the grammar
of the language to be unambiguous e.g. G8 of G7.
❑ There is a derivation tree for var + var * var using
grammar G8.
Compiler Design Dr. Salah Eldin Shaban 43
Ambiguity Cont.

Compiler Design Dr. Salah Eldin Shaban 44

Ambiguity Cont.

Compiler Design Dr. Salah Eldin Shaban 45

Ambiguity Cont.
❑ Another example of ambiguity in programming languages
is the conditional statement as defined by grammar G9:
G9:
1. Stmt → IfStmt
2. IfStmt → if Cond then Stmt
3. IfStmt → if Cond then Stmt else Stmt

❑ Two different derivation trees for: if Cond then if Cond then

Stmt else Stmt are:

Compiler Design Dr. Salah Eldin Shaban 46

Ambiguity Cont.

Compiler Design Dr. Salah Eldin Shaban 47

Ambiguity Cont.
❑ A derivation tree for if Cond then if Cond then OtherStmt
else OtherStmt using grammar G10 is:

Compiler Design Dr. Salah Eldin Shaban 48

Left Recursion
❑ A grammar is said to be immediately left recursive if there is 
production of the form A → A .
❑ Consider a grammar G with productions A → A  | 
❑ A new grammar G′ defines the same language as G but without
any left recursion, by replacing the above productions with
A → A′
A′ →  A′ | e
❑ In general, consider a grammar G with productions
A → A 1 | A 2 | · · · | A n |  1 |  2 | · · · |  m
where none of 1, . . . , m begin with an A.
Compiler Design Dr. Salah Eldin Shaban 49
Left Recursion Cont.
❑ A new grammar G′7 without left recursion by replacing the
G7:
above productions with
1. Expr → Expr + Expr
A → 1A′ | 2A′ | · · · | mA′ 2. Expr → Expr * Expr
A′ → 1A′ | 2A′ | · · · | nA′ | e 3. Expr → ( Expr )
4. Expr → var
❑ The left recursion is removed as G8: 5. Expr → const
G8: G’7:
1. Expr → Term Expr’ 1. Expr → Expr + Term | Term
2. Expr’ → + Term Expr’ | e 2. Term → Term * Factor | Factor
3. Expr → ( Expr ) | var | const
3. Term → Factor Term’
4. Term’ → * Factor Term’ | e
5. Factor → ( Expr ) | var | const

Compiler Design Dr. Salah Eldin Shaban 50

Left-Factoring
❑ Many simple parsing algorithms cannot cope with grammars
with productions such as
‹ if stmt › → if ‹ exp › then ‹ stmt › else ‹ stmt ›
| if ‹ exp › then ‹ stmt ›
where two or more productions for a given non-terminal share a
common prefix.
❑ Factor-out the common prefix, the equivalent grammar rules:
‹ if stmt › → if ‹ exp › then ‹ stmt › ‹ rest if ›
‹ rest if › → else ‹ stmt › | e

Compiler Design Dr. Salah Eldin Shaban 51

Left-Factoring Cont.
❑ In general, if situation of the productions are as follows:
A →  1 |  2
❑ Then, it is difficult to decide whether to expand A to  1 or
to  2
❑ We will rewrite the production:
A →  A’
A’ → 1 | 2
❑ After seeing the input derived from , we expand
A’ to 1 or to 2.

Compiler Design Dr. Salah Eldin Shaban 52

Pushdown Machines
❑ A pushdown machine is an abstract or theoretic machine.
❑ Pushdown machines can be used for parsing.
❑ A pushdown machine consists of:
1. A finite set of states, one is designated as the starting state.
2. A finite set of input symbols, the input alphabet.
3. An infinite stack and a finite set of stack symbols.
▪ Pushed on or removed from it.
▪ The stack symbol need not be distinct from the input symbols.
▪ The stack must be initialized to contain at least one stack symbol
before the first input symbol is read.

Compiler Design Dr. Salah Eldin Shaban 53

 Pushdown Machines Cont.
4. A state transition function f (current state, input symbol, top stack
symbol); its result is the new state of the machine.
5. On each state transition, the machine may advance to the next
input symbol or retain the input pointer (i.e., not advance to the next
input symbol).
6. On each state transition, the machine may perform one of the stack
operations, push(X) or pop, where X is one of the stack symbols.
7. A state transition may include an exit from the machine labeled
either Accept or Reject. This determines whether or not the input
string is in the specified language.
❑ The pushdown machine is: Infinite Stack + FSM

Compiler Design Dr. Salah Eldin Shaban 54

 Pushdown Machines Cont.
❑ A pushdown machine to accept the language of grammar G3
✓ rows labeled by stack symbols and columns labeled by input
symbols.
✓ end-marker, indicating the end of the input string, and the
empty stack symbol.
✓ The states of the machine are S1 (will always the starting state)
and S2;
✓ A separate transition table for each state.
✓ Each cell shows a stack operation (push(X) or pop), an input
pointer function (advance or retain), and the next state. "Accept"
and "Reject" are exits from the machine.

Compiler Design Dr. Salah Eldin Shaban 55

 Pushdown Machines Cont.

❑ Sequence of stacks as pushdown machine accepts the input

string aabb is:

Compiler Design Dr. Salah Eldin Shaban 56

Pushdown Machines Cont.
❑ A pushdown machine to accept any string of well-balanced
parentheses is:

Compiler Design Dr. Salah Eldin Shaban 57

Pushdown Machines Cont.
❑ Pushdown translator for infix to postfix expressions.

Compiler Design Dr. Salah Eldin Shaban 58

 ?

Compiler Design Dr. Salah Eldin Shaban 59