UNIT-4

PARSING TECHNIQUES

Bottom-Up Parsing:
• A bottom-up parser creates the parse tree of the given input starting from leaves
towards the root.
• A bottom-up parser tries to find the right-most derivation of the given input in the
reverse order.
S ⇒ ... ⇒ ω (the right-most derivation of ω)
← (the bottom-up parser finds the right-most derivation in the
reverse order)
• Bottom-up parsing is also known as shift-reduce parsing because its two main
actions are shift and reduce.
– At each shift action, the current symbol in the input string is pushed to a
stack.
– At each reduction step, the symbols at the top of the stack (this symbol
sequence is the right side of a production) will replaced by the non-
terminal at the left side of that production.
– There are also two more actions: accept and error.

Shift-Reduce Parsing:
• A shift-reduce parser tries to reduce the given input string into the starting
symbol.

a string è the starting symbol

reduced to

• At each reduction step, a substring of the input matching to the right side of a
production rule is replaced by the non-terminal at the left side of that production
rule.
• If the substring is chosen correctly, the right most derivation of that string is
created in the reverse order.
Rightmost Derivation: S⇒ω
Shift-Reduce Parser finds: ω ⇐ ... ⇐ S
Example:
S → aABb input string: aaabb
A → aA | a aaAbb
B → bB | b aAbb ⇓ reduction
aABb
S

S ⇒ aABb ⇒ aAbb ⇒ aaAbb ⇒ aaabb

 Right Sentential Forms

• How do we know which substring to be replaced at each reduction step?

Handle:
• Informally, a handle of a string is a substring that matches the right side of a
production rule.
– But not every substring matches the right side of a production rule is
handle

• A handle of a right sentential form γ (≡ ωβα) is

a production rule A → β and a position of γ
where the string β may be found and replaced by A to produce
the previous right-sentential form in a rightmost derivation of γ.

S ⇒ αAω ⇒ ωβα

• If the grammar is unambiguous, then every right-sentential form of the grammar

has exactly one handle.
• We will see that ω is a string of terminals.

Handle Pruning
• A right-most derivation in reverse can be obtained by handle-pruning.

S=γ0 ⇒ γ1 ⇒ γ2 ⇒ ... ⇒ γn-1 ⇒ γn= ω

input string

• Start from γn, find a handle Anβ→n in γn, and replace βn in by An to get γn-1.
• Then find a handle An-1β→n-1 in γn-1,and replace βn-1 in by An-1 to get γn-2.
• Repeat this, until we reach S.

A Shift-Reduce Parser:

E → E+T | T Right-Most Derivation of id+id*id

T → T*F | F E ⇒ E+T ⇒ E+T*F ⇒ E+T*id ⇒ E+F*id
F → (E) | id ⇒ E+id*id ⇒ T+id*id ⇒ F+id*id ⇒ id+id*id
Right-Most Sentential Form Reducing Production
id+id*id F → id
F+id*id T→F
T+id*id E→T
E+id*id F → id
E+F*id T→F
E+T*id F → id
E+T*F T → T*F
E+T E → E+T
E
Handles are red and underlined in the right-sentential forms.

A Stack Implementation of A Shift-Reduce Parser:

• There are four possible actions of a shift-parser action:

1. Shift : The next input symbol is shifted onto the top of the stack.
2. Reduce: Replace the handle on the top of the stack by the non-terminal.
3. Accept: Successful completion of parsing.
4. Error: Parser discovers a syntax error, and calls an error recovery routine.

• Initial stack just contains only the end-marker $.

• The end of the input string is marked by the end-marker $.

Conflicts During Shift-Reduce Parsing:

• There are context-free grammars for which shift-reduce parsers cannot be used.
• Stack contents and the next input symbol may not decide action:
– shift/reduce conflict: Whether make a shift operation or a reduction.
 – reduce/reduce conflict: The parser cannot decide which of several
reductions to make.
• If a shift-reduce parser cannot be used for a grammar, that grammar is called as
non-LR(k) grammar.

left to right right-most k lookhead

scanning derivation

• An ambiguous grammar can never be a LR grammar.

Shift-Reduce Parsers:
• There are two main categories of shift-reduce parsers

1. Operator-Precedence Parser
– simple, but only a small class of grammars.

2. LR-Parsers
– covers wide range of grammars.
• SLR – simple LR parser
• LR – most general LR parser
• LALR – intermediate LR parser (lookahead LR parser)
– SLR, LR and LALR work same, only their parsing tables are different.

Operator Precedence Grammar:

The bottom up parsing technique considered is called the operator precedence method.
This method is loaded on examining pairs of consecutive operators in the source program
and making decisions about which operation should be performed first.
Example: A + B * C - D (1)
The usual procedure of operation multiplication and division has higher precedence over
addition and subtraction.
Now considering equation (1) the two operators (+ and *), we find that + has
lower precedence than *. This is written as +⋖ * [+ has lower precedence *]
Similarly (* and -), we find that * ⋗ - [* has greater precedence -].
The operation precedence method uses such observations to guide the parsing process.
 A+B*C-D (2)

Precedence Matrix for the Grammar

Equation (2) implies that the sub expression B * C is to be computed before either of the
other operations in the expression is performed. In times of the parse tree this means that
the * operation appears at a lower level than does either + or -. Thus a bottom up parses
should recognize B * C by interpreting it in terms of the grammar, before considering the
surrounding terms. The first step in constructing an operator precedence parser is to
determine the precedence relations between the operators of the grammar. Operator is
taken to mean any terminal symbol (i.e., any token). We also have precedence relations
involving tokens such as BEGIN, READ, id and (. For the grammar in fig. 5, the
precedence relation is given in the above fig.

Example: PROGRAM ≐ VAR ; These two tokens have equal precedence

Begin ⋖ FOR ; BEGIN has lower precedence over FOR. There are some values which do
not follows precedence relations for comparisons.
Example: ; ⋗ END and END ⋗ ;
i.e., when ; is followed by END, the ' ; ' has higher precedence and when END is
followed by ; the END has higher precedence.
In all the statements where precedence relation does not exist in the table, two
tokens cannot appear together in any legal statement. If such combination occurs during
parsing it should be recognized as error.
Let us consider some operator precedence for the grammar in fig. 5.
Example: Pascal Statement: BEGIN
READ (VALUE);
These Pascal statements scanned from left to right, one token at a time. For each pair of
operators, the precedence relation between them is determined. Fig. 12(a) shows the
parser that has identified the portion of the statement delimited by the precedence
relations ⋖ and ⋗ to be interpreted in terms of the grammar.

According to the grammar id may be considered as < factor >. (rule 12),
<program > (rule 9) or a < id-list > (rule 6). In operator precedence phase, it is not
necessary to indicate which non-terminal symbol is being recognized. It is interpreted as
non-terminal < N1 >. Hence the new version is shown in fig. 12(b).
An operator-precedence parser generally uses a stack to save token that have been
scanned but not yet parsed, so it can reexamine them in this way. Precedence relations
hold only between terminal symbols, so < N1 > is not involved in this process and a
relationship is determined between (and).
READ (<N1>) corresponds to rule 13 of the grammar. This rule is the only one that could
be applied in recognizing this portion of the program. The sequence is simply interpreted
as a sequence of some interpretation < N2 >. Fig. 12(c) shows this interpretation. The
parser tree is given in fig. 12(d).
Note: (1) The parse tree in fig. 1 and fig. 12 (d) are same except for the name of
the non-terminal symbols involved.
(2) The name of the non-terminals is arbitrarily chosen.
Top-Down Parsing:
• The parse tree is created top to bottom.
• Top-down parser
– Recursive-Descent Parsing
• Backtracking is needed (If a choice of a production rule does not
work, we backtrack to try other alternatives.)
• It is a general parsing technique, but not widely used.
• Not efficient
– Predictive Parsing
• no backtracking
• efficient
• needs a special form of grammars (LL(1) grammars).
• Recursive Predictive Parsing is a special form of Recursive
Descent parsing without backtracking.
• Non-Recursive (Table Driven) Predictive Parser is also known as
LL(1) parser.

Recursive-Descent Parsing (uses Backtracking):

• Backtracking is needed.
• It tries to find the left-most derivation.

S → aBc
B → bc | b
input: abc

Predictive Parser:
a grammar è è a grammar suitable for predictive
eliminate left parsing (a LL(1) grammar)
left recursion factor no %100 guarantee.

• When re-writing a non-terminal in a derivation step, a predictive parser can

uniquely choose a production rule by just looking the current symbol in the input
string.
 A → α1 | ... | αn input: ... a .......

current token
Example:
stmt → if ...... |
while ...... |
begin ...... |
for .....

• When we are trying to write the non-terminal stmt, if the current token is if we
have to choose first production rule.
• When we are trying to write the non-terminal stmt, we can uniquely choose the
production rule by just looking the current token.
• We eliminate the left recursion in the grammar, and left factor it. But it may not be
suitable for predictive parsing (not LL(1) grammar).

Recursive Predictive Parsing:

• Each non-terminal corresponds to a procedure.
Ex: A → aBb (This is only the production rule for A)

proc A {
- match the current token with a, and move to the next token;
- call ‘B’;
- match the current token with b, and move to the next token;
}
A → aBb | bAB

proc A {
case of the current token {
‘a’: - match the current token with a, and move to the next token;
- call ‘B’;
- match the current token with b, and move to the next token;
‘b’: - match the current token with b, and move to the next token;
- call ‘A’;
- call ‘B’;
}
}

• When to apply ε-productions.

A → aA | bB | ε

• If all other productions fail, we should apply an ε-production. For example, if the
current token is not a or b, we may apply the ε-production.
 • Most correct choice: We should apply an ε-production for a non-terminal A when
the current token is in the follow set of A (which terminals can follow A in the
sentential forms).

Example:
A → aBe | cBd | C
B → bB | ε
C→f
proc C { match the current token with f,
and move to the next token; }

proc A {
case of the current token {
a: - match the current token with a,
and move to the next token; proc B {
- call B; case of the current token {
- match the current token with e, b: - match the
current token with b,
and move to the next token; and move to the next
token;
c: - match the current token with c, - call B
and move to the next token; e,d: do nothing
- call B; }
- match the current token with d, }
and move to the next token;
f: - call C
}
}

Non-Recursive Predictive Parsing -- LL(1) Parser:

• Non-Recursive predictive parsing is a table-driven parser.
• It is a top-down parser.
• It is also known as LL (1) Parser.
LL (1) Parser:
input buffer
– our string to be parsed. We will assume that its end is marked with a
special symbol $.

output
– a production rule representing a step of the derivation sequence (left-most
derivation) of the string in the input buffer.

stack
– contains the grammar symbols
– at the bottom of the stack, there is a special end marker symbol $.
– initially the stack contains only the symbol $ and the starting symbol S.
$S ç initial stack
– when the stack is emptied (ie. only $ left in the stack), the parsing is
completed.

parsing table
– a two-dimensional array M[A,a]
– each row is a non-terminal symbol
– each column is a terminal symbol or the special symbol $
– each entry holds a production rule.

LL (1) Parser – Parser Actions:

• The symbol at the top of the stack (say X) and the current symbol in the input
string (say a) determine the parser action.
• There are four possible parser actions.

1. If X and a are $ è parser halts (successful completion)

2. If X and a are the same terminal symbol (different from $)
è parser pops X from the stack, and moves the next symbol in the input buffer.
 3. If X is a non-terminal
è parser looks at the parsing table entry M[X,a]. If M[X,a] holds a production
rule X→Y1Y2...Yk, it pops X from the stack and pushes Yk,Yk-1,...,Y1 into the stack.
The parser also outputs the production rule X→Y1Y2...Yk to represent a step of the
derivation.
4. none of the above è error
– all empty entries in the parsing table are errors.
– If X is a terminal symbol different from a, this is also an error case.

Example 1:

Outputs: S → aBa B → bB B → bB B→ε

Derivation (left-most): S⇒aBa⇒abBa⇒abbBa⇒abba

€
Example 2:
E → TE’
E’ → +TE’ | ε
T → FT’
T’ → *FT’ | ε
F → (E) | id

Constructing LL(1) Parsing Tables:

• Two functions are used in the construction of LL(1) parsing tables:
– FIRST FOLLOW
 • FIRST(α) is a set of the terminal symbols which occur as first symbols in strings
derived from α where α is any string of grammar symbols.
• if α derives to ε, then ε is also in FIRST(α) .

• FOLLOW(A) is the set of the terminals which occur immediately after (follow)
the non-terminal A in the strings derived from the starting symbol.
– a terminal a is in FOLLOW(A) if S ⇒ αAaβ
– $ is in FOLLOW(A) if S ⇒ αA

Compute FIRST for Any String X:

• If X is a terminal symbol è FIRST(X)={X}
• If X is a non-terminal symbol and X → ε is a production rule
è ε is in FIRST(X).
• If X is a non-terminal symbol and X → Y1Y2..Yn is a production rule
è if a terminal a in FIRST(Yi) and ε is in all FIRST(Yj) for j=1,...,i-1
then a is in FIRST(X).
è if ε is in all FIRST(Yj) for j=1,...,n
then ε is in FIRST(X).
• If X is ε è FIRST(X)={ε}
• If X is Y1Y2..Yn
è if a terminal a in FIRST(Yi) and ε is in all FIRST(Yj) for j=1,...,i-1
then a is in FIRST(X).
è if ε is in all FIRST(Yj) for j=1,...,n
then ε is in FIRST(X).

FIRST Example:
E → TE’
E’ → +TE’ | ε
T → FT’
T’ → *FT’ | ε
F → (E) | id

FIRST(F) = {(,id} FIRST(TE’) = {(,id}

FIRST(T’) = {*, ε} FIRST(+TE’ ) = {+}
FIRST(T) = {(,id} FIRST(ε) = {ε}
FIRST(E’) = {+, ε} FIRST(FT’) = {(,id}
FIRST(E) = {(,id} FIRST(*FT’) = {*}
FIRST(ε) = {ε}
FIRST((E)) = {(}
FIRST(id) = {id}

Compute FOLLOW (for non-terminals):

• If S is the start symbol è $ is in FOLLOW(S)
 • if A → αBβ is a production rule
è everything in FIRST(β) is FOLLOW(B) except ε

• If ( A → αB is a production rule ) or
( A → αBβ is a production rule and ε is in FIRST(β) )
è everything in FOLLOW(A) is in FOLLOW(B).

We apply these rules until nothing more can be added to any follow set.

FOLLOW Example:
E → TE’
E’ → +TE’ | ε
T → FT’
T’ → *FT’ | ε
F → (E) | id

FOLLOW(E) = { $, ) }
FOLLOW(E’) = { $, ) }
FOLLOW(T) = { +, ), $ }
FOLLOW(T’) = { +, ), $ }
FOLLOW(F) = {+, *, ), $ }

Constructing LL(1) Parsing Table – Algorithm:

• for each production rule A → α of a grammar G
– for each terminal a in FIRST(α)
è add A → α to M[A,a]
– If ε in FIRST(α)
è for each terminal a in FOLLOW(A) add A → α to M[A,a]
– If ε in FIRST(α) and $ in FOLLOW(A)
è add A → α to M[A,$]

• All other undefined entries of the parsing table are error entries.
Constructing LL(1) Parsing Table – Example:

LL (1) Grammars:
• A grammar whose parsing table has no multiply-defined entries is said to be
LL (1) grammar.

• The parsing table of a grammar may contain more than one production rule. In
this case, we say that it is not a LL(1) grammar.

A Grammar which is not LL(1):

S→iCtSE | a FOLLOW(S) = { $,e }
E→eS | ε FOLLOW(E) = { $,e }
C→b FOLLOW(C) = { t }
Problem è ambiguity

• What do we have to do it if the resulting parsing table contains multiply defined

entries?
– If we didn’t eliminate left recursion, eliminate the left recursion in the
grammar.
– If the grammar is not left factored, we have to left factor the grammar.
– If its (new grammar’s) parsing table still contains multiply defined entries,
that grammar is ambiguous or it is inherently not a LL(1) grammar.
• A left recursive grammar cannot be a LL(1) grammar.
– A → Aα | β
è any terminal that appears in FIRST(β) also appears FIRST(Aα)
because Aα ⇒ αβ.
è If β is ε, any terminal that appears in FIRST(α) also appears in
FIRST(Aα) and FOLLOW(A).
• A grammar is not left factored, it cannot be a LL(1) grammar
– A → βα1 | βα2
è any terminal that appears in FIRST(βα1) also appears in
FIRST(βα2).
• An ambiguous grammar cannot be a LL(1) grammar.

Properties of LL(1) Grammars:

• A grammar G is LL(1) if and only if the following conditions hold for two
distinctive production rules A → α and A → β
1. Both α and β cannot derive strings starting with same terminals.
2. At most one of α and β can derive to ε.
3. If β can derive to ε, then α cannot derive to any string starting with a
terminal in FOLLOW(A).

Error Recovery in Predictive Parsing:

• An error may occur in the predictive parsing (LL(1) parsing)
– if the terminal symbol on the top of stack does not match with the
current input symbol.
– if the top of stack is a non-terminal A, the current input symbol is a, and
the parsing table entry M[A,a] is empty.
 • What should the parser do in an error case?
– The parser should be able to give an error message (as much as possible
meaningful error message).
– It should be recover from that error case, and it should be able to
continue the parsing with the rest of the input.

Error Recovery Techniques:

• Panic-Mode Error Recovery
– Skipping the input symbols until a synchronizing token is found.
• Phrase-Level Error Recovery
– Each empty entry in the parsing table is filled with a pointer to a specific
error routine to take care that error case.
• Error-Productions
– If we have a good idea of the common errors that might be encountered,
we can augment the grammar with productions that generate erroneous
constructs.
– When an error production is used by the parser, we can generate
appropriate error diagnostics.
– Since it is almost impossible to know all the errors that can be made by the
programmers, this method is not practical.
• Global-Correction
– Ideally, we we would like a compiler to make as few change as possible in
processing incorrect inputs.
– We have to globally analyze the input to find the error.
– This is an expensive method, and it is not in practice.

Panic-Mode Error Recovery in LL(1) Parsing:

• In panic-mode error recovery, we skip all the input symbols until a synchronizing
token is found.
• What is the synchronizing token?
– All the terminal-symbols in the follow set of a non-terminal can be used as
a synchronizing token set for that non-terminal.
• So, a simple panic-mode error recovery for the LL(1) parsing:
– All the empty entries are marked as synch to indicate that the parser will
skip all the input symbols until a symbol in the follow set of the non-
terminal A which on the top of the stack. Then the parser will pop that
non-terminal A from the stack. The parsing continues from that state.
– To handle unmatched terminal symbols, the parser pops that unmatched
terminal symbol from the stack and it issues an error message saying that
that unmatched terminal is inserted.
Panic-Mode Error Recovery – Example:

Phrase-Level Error Recovery:

• Each empty entry in the parsing table is filled with a pointer to a special error
routine which will take care that error case.
• These error routines may:
– change, insert, or delete input symbols.
– issue appropriate error messages
– pop items from the stack.
• We should be careful when we design these error routines, because we may put
the parser into an infinite loop.