Bottom-Up Parsing in Compiler Design

Bottom-Up Parsing

A bottom-up parsing constructs the parse tree for an input string beginning from the bottom (the leaves) and moves to work towards the top (the root). Bottom-up parsing is a parser that reduces the string to the start symbol of the grammar.  During the reduction, a specific substring matching the right side or body of the production will be replaced by a non – terminal at the head of that production. Bottom-up parsing constructs rightmost derivation in reverse order while scanning the input from left to right.

Shift – Reducing Parser

It is a type of bottom-up parser. In this parser, a stack holds the grammar symbol, and an input buffer holds the rest of the string that is set to be parsed. 

The symbol $ denotes the bottom of the stack and also the input's right side. While discussing the bottom-up parsing, we generally represent the top of the stack on the right-hand side. In the beginning, the stack is empty, and the string a is on the input side, as shown below:

                                         STACK                                     INPUT

                                              $                                              a$ 

This parsing generally performs two action shifts and reduce. But there are four possible actions that this parser can perform: shift, reduce, accept, error.

1) Shift – Shift operation shifts the input symbol onto the top of the stack.

2) Reduce – The top of the stack must hold the right end of that string, which is set to be reduced. It finds the left end of the string within the stack and decides which non – terminal can replace the string.

3) Accept – When we are only left with the start symbol in the stack, then the parsing action is called as Accept state.

4) Error – It detects the error and try to recover it.

Example:

Grammar:

A => A + A

A => A – A

A => (A)

A => a

input string:

a1-(a2+a3)

Parsing Table:

Stack	Input	Action
$	a1- (a2+a3)$	Shift a1
$a1	-(a2+a3)$	Reduce by A => a
$A	-(a2+a3)$	Shift -
$A-	(a2+a3)$	Shift (
$A-(	a2+a3)$	Shift a2
$A-(a2	+a3)$	Reduce by A => a
$A -(A	+a3)$	Shift +
$A -(A +	a3)$	Shift +
$A -(A +a3	) $	Reduce by A =>a
$A -(A + A	) $	Shift )
$A -(A + A)	$	Reduce by A => A +A
$A - (A)	$	Reduce by A => (A)
$A – A	$	Reduce by A => A - A

$A

$

Accept

Table1: Configuration of shift-reduce parser on input a1-(a2+a3)

Operator Precedence Parser

A grammar that is used to generate or define the mathematical expression with some restrictions on it is known as operator precedence grammar. Any grammar can be operator precedence grammar if it follows two properties:

• No two-variable should be adjacent.
• It should not have a null production.

Example:

E => E + E/ E * E/id

This is operator precedence grammar because there are no two adjacent variables, and there is no null production on the right side of the grammar.

Operator precedence parser ignores the non – terminal. It can only be established between the terminal of grammar. Only operator precedence grammar accepts ambiguous grammar.

Operator precedence relation

If a ? b, it means that terminal b has lower precedence than terminal a.

If b ? a, it means that terminal b has higher precedence over terminal a.

If a=b, it means that terminal a and terminal b have the same precedence.

An identifier has higher precedence than any other symbol, and the symbol $ has the lower precedence.

If two operator has the same precedence, then we will decide by checking the associativity of the operator.

Precedence Table

	+	*	(	)	id	$
+	?	?	?	?	?	?
*	?	?	?	?	?	?
(	?	?	?	=	?	X
)	?	?	X	?	X	?
Id	?	?	X	?	X	?
$	?	?	?	X	?	X

Parsing Action

• Adds symbol $ at both ends of the input string
• Scans the input symbol from left to right until the ? encounter.
• Scan towards leftover all the equal precedence until the first left-most ? is encountered.
• Everything between the left-most ? and rightmost ? is a handle.
• $ on $ means parsing is successful.

Example:

Grammar:

E => EAE |id

A => + | x

String:

id + id x id.

Depict the operator precedence parser and parse the given input string.

Solution:

Firstly, we will convert the given grammar into an operator precedence grammar.

The equivalent operator precedence grammar is as follows:

                                                  E => E + E | E x E | id

The terminal symbols in the given grammar are = (id, +, x, $)

We will construct the operator precedence table as:

	Id	+	x	$
Id		>	>	>
+	<	>	<	>
X	<	>	>	>
$	<	<	<

String to be parsed is given as id + id x id.

We will follow the given steps to parse the given input string:

The symbol $ will be added at both ends of the given input string:

                                                                  $ id + id x id $

Now insert the precedence operators between the string symbol as:

                                                                 $ < id > + < id > x < id > $

Now let's process the string with the help of the given precedence table:

$ < id > + < id > x < id > $

$ E + < id > x < id > $

$ E + E x < id > $

$ E + E x E $

$ + x $

$ < + < x > $

$ < + > $

$ $