Constructing a parse tree for an input string beginning at the leaves and going towards the root is called bottom-up parsing. A general type of bottom-up parser is a shift-reduce parser.


 Shift-reduce parsing is a type of bottom-up parsing that attempts to construct a parse tree for an input string beginning at the leaves (the bottom) and working up towards the root (the top).


Consider the grammar:

S → aABe

A → Abc | b

B → d

The sentence to be recognized is abbcde.


abbcde (A → b)    S → aABe 

aAbcde(A → Abc)         → aAde     

aAde (B → d)      → aAbcde  

aABe (S → aABe)          → abbcde  


The reductions trace out the right-most derivation in reverse.


 A handle of a string is a substring that matches the right side of a production, and whose reduction to the non-terminal on the left side of the production represents one step along the reverse of a rightmost derivation.


Consider the grammar:





And the input string id1+id2*id3

The rightmost derivation is :


→ E+E*E

→ E+E*id3

→ E+id2*id3

→ id1+id2*

In the above derivation the underlined substrings are called handles.

Handle pruning:

A rightmost derivation in reverse can be obtained by “handle pruning”. (i.e.) if w is a sentence or string of the grammar at hand, then w = γn, where γn is the nth rightsentinel form of

some rightmost derivation.

Actions in shift-reduce parser:

•   shift – The next input symbol is shifted onto the top of the stack.

•   reduce – The parser replaces the handle within a stack with a non-terminal.

•   accept – The parser announces successful completion of parsing.

•   error – The parser discovers that a syntax error has occurred and calls an error recovery routine.

Conflicts in shift-reduce parsing:

There are two conflicts that occur in shift-reduce parsing:

1. Shift-reduce conflict: The parser cannot decide whether to shift or to reduce.

2. Reduce-reduce conflict: The parser cannot decide which of several reductions to make.

Stack implementation of shift-reduce parsing :

1. Shift-reduce conflict: 


Consider the grammar:

E→E+E | E*E | id and input id+id*id

2. Reduce-reduce conflict:

Consider the grammar: M→R+R|R+c|R


and input c+c

Viable prefixes:

α is a viable prefix of the grammar if there is w such that αw is a right

The set of prefixes of right sentinel forms that can appear on the stack of a shift-reduce parser are called viable prefixes

The set of viable prefixes is a regular language.


An efficient way of constructing shift-reduce parser is called operator-precedence parsing. Operator precedence parser can be constructed from a grammar called Operator-grammar. These grammars have the property that no production on right side is ɛor has two adjacent non-terminals.


Consider the grammar:



Since the right side EAE has three consecutive non-terminals, the grammar can be written as follows: E→E+E|E-E|E*E|E/E|E↑E |-E|id

Operator precedence relations:

There are three disjoint precedence relations namely

<. – less than

=                   – equal to

.> – greater than

The relations give the following meaning:

a<.b – a yields precedence to b

a=b – a has the same precedence as b

a.>b – a takes precedence over b

Rules for binary operations:

1. If operator θ1 has higher precedence than operator θ2, then make

θ1 . > θ2 and θ2 < . θ1

2. If operators θ1 and θ2, are of equal precedence, then make

θ1 . > θ2 and θ2 . > θ1 if operators are left associative

θ1 < . θ2 and θ2 < . θ1 if right associative

3. Make the following for all operators θ:

θ  <. id ,id.>θ

θ  <.(, (<.θ

).>θ, θ.>)

θ.>$ , $<. θ

Also make

( = ) , ( <. ( , ) .> ) , (<. id, id .>) , $ <. id , id .> $ , $ Example:

Operator-precedence relations for the grammar

E→E+E|E-E|E*E|E/E|E↑E |(E)|-E|idis given in the following table assuming

1.                 ↑ is of highest precedence and right-associative

2.                 * and / are of next higher precedence and left-associative, and

3.                 + and – are of lowest precedence and left- Note that the blanks in the table denote error entries.

Table : Operator-precedence relations

Operator precedence parsing algorithm:

Input : An input string w and a table of precedence relations.

Output : If w is well formed, a skeletal parse tree ,with a placeholder non-terminal E labeling all interior nodes; otherwise, an error indication.

Method : Initially the stack contains $ and the input buffer the string w $. To parse, we execute the following program :

(1) Set ip to point to the first symbol of w$;

(2)             repeat forever

(3) if $ is on top of the stack and ip points to $ then

(4)             return else begin

(5)             let a be the topmost terminal symbol on the stack and let b be the symbol pointed to by ip;

(6)             if a <. b or a = b then begin

(7)             push b onto the stack;

(8)             advance ip to the next input symbol; end;

(9) else if a . > b then /*reduce*/

(10)        repeat

(11)        pop the stack

(12)        until the top stack terminal is related by <.to the terminal most recently popped

(13)        else error( ) end

Stack implementation of operator precedence parsing:

Operator precedence parsing uses a stack and precedence relation table for its implementation of above algorithm. It is a shift-reduce parsing containing all four actions shift, reduce, accept and error.

The initial configuration of an operator precedence parsing is


INPUT : w$

where w is the input string to be parsed.


Consider the grammar E → E+E | E-E | E*E | E/E | E↑E | (E) | id. Input string is id+id*id .The implementation is as follows:

Advantages of operator precedence parsing:

1.   It is easy to implement.

2.    Once an operator precedence relation is made between all pairs of terminals of a grammar, the grammar can be ignored. The grammar is not referred anymore during implementation.

Disadvantages of operator precedence parsing:

1.   It is hard to handle tokens like the minus sign (-) which has two different precedence.

2.   Only a small class of grammar can be parsed using operator-precedence parser.

Related Posts

© 2024 Basic Computer Science - Theme by WPEnjoy · Powered by WordPress