LECTURE 4

TYPES OF
PARSERS IN
COMPILER
DESIGN
TYPES OF PARSERS IN COMPILER DESIGN

• The parser is that phase of the compiler that takes a token string

as input and with the help of existing grammar, converts it into

the corresponding Intermediate Representation(IR). The parser

is also known as Syntax Analyzer.

TYPES OF PARSERS IN COMPILER DESIGN
TYPES OF PARSERS

• The parser is mainly classified into two categories, Top-down Parser, and Bottom-up Parser. These are explained

below:

• Top-Down Parser:

• The top-down parser is the parser that generates parse for the given input string with the help of grammar

productions by expanding the non-terminals. it starts from the start symbol and ends on the terminals. It uses

leftmost derivation. Where parse constructed from top and input is read from left to right. The input is recursively

parsed for preparing a parse tree. With or without a backtracking

• Further Top-down parser is classified into 2 types: A recursive descent parser, and a Non-recursive descent parser.
TOP-DOWN PARSER:

• Recursive descent parser is also known as the backtracking parser. It

generates the parse tree by using backtracking..

• Non-recursive descent parser is also known as LL(1) parser or predictive

parser or without backtracking parser or dynamic parser. It uses a parsing

table to generate the parse tree instead of backtracking.

BOTTOM-UP PARSER:

• Bottom-up Parser is the parser that generates the parse tree for the given

input string with the help of grammar productions by compressing the

terminals. it starts from terminals and ends on the start symbol. It uses the

Rightmost Derivation in Reverse.

• Further, we classify the Bottom-up parser into two types: LR parser and

Operator precedence parser.

BOTTOM-UP PARSER- LR PARSER :

• LR parser is the bottom-up parser that generates the parse tree for the given string by using

unambiguous grammar. It follows the Rightmost Derivation in Reverse.

• LR parser is of four types:

• LR(0)

• SLR(1)

• LALR(1)

• CLR(1)
BOTTOM-UP PARSER- OPERATOR PRECEDENCE PARSER :

• Operator Precedence Parser is a bottom-up parser used for parsing

programming languages with a defined precedence (order of importance) for

operators.

• This parser is specifically designed to handle mathematical and

programming expressions involving operators with different precedence

levels, such as addition (+), multiplication (*), and parentheses.

CHARACTERISTICS OF THE OPERATOR PRECEDENCE
PARSER
• Operator Precedence: This parser uses rules to determine the precedence between different expressions’ operators. For

example, in the expression 3 + 5 * 2, multiplication (*) has higher precedence than addition (+), so the parser interprets it as 3

+ (5 * 2).

• Associativity Rules: Besides operator precedence, the parser defines the associativity of operators. In most arithmetic

operations, binary operators like + and - are left-associative (evaluated from left to right), while certain operations, such as

exponentiation (^), are right-associative (evaluated from right to left).

• Precedence Table: The Operator Precedence Parser relies on an Operator Precedence Table that contains the precedence order

of the different operators.

• No Overlapping Operators: In grammars used with this parser, there must not be overlapping between operators, which

simplifies the parsing process.

HOW THE OPERATOR PRECEDENCE PARSER WORKS

• This parser functions in a bottom-up parsing manner, where it starts by analyzing smaller parts of an

expression, like operators and numbers, and then gradually builds up the structure of the entire

expression. The process generally works as follows:

• Scanning the Expression from left to right.

• Using the precedence table to determine which operator to evaluate first based on its precedence

over other operators.

• Evaluating operations on operators and numbers according to precedence and associativity.

• Building the expression step-by-step until reaching the final result.

EXAMPLE OF OPERATOR PRECEDENCE PARSING

• Consider the following expression:

• 3+5*2

• Step 1: Start by reading 3, +, and 5.

• Step 2: We see the * operator and know it has higher precedence than +.

• Step 3: First, calculate 5 * 2 = 10.

• Step 4: Then, apply the + operation to get 3 + 10 = 13.

WHEN IS THE OPERATOR PRECEDENCE PARSER USED?

• This parser is primarily used in programming languages that contain mathematical

expressions, where the compiler needs to understand operator precedence, such as C,

Python, and others.

• Limitations of the Operator Precedence Parser

• It cannot handle all complex grammars, as it’s generally limited to parsing expressions

that follow a clear precedence of operators.

• It cannot process expressions with ambiguous or overlapping operators.

BACKTRACKING

• Backtracking: The parse tree is started from the root node and the input

string is matched against the production rules for replacing them. It means,

that if one derivation of a production fails, the syntax analyzer restarts the

process using different rules of the same production. This technique may

process the input string more than once to determine the right production.
BACKTRACKING

• EXAMPLE of backtracking: Let the grammar G be

S→cAd S S

A→ab|d
Input → W=cdd c A d c A d

W = cabd W = cdd
BACKTRACKING

There are some limitations to the backtracking technique. Where if the

given grammar has more numbers of alternatives, then the cost of

Input →

backtracking will be high

PREDICTIVE PARSER (LL PARSER)
• A predictive parser is a type of top-down parser, similar to recursive
descent parsing but without backtracking. It can be implemented
non-recursively using a stack data structure.
• Predictive Parsers have the following components:-
Input →

• Input Buffer − The input buffer includes the string to be parsed followed by
an end marker $ to denote the end of the string.

• Stack − It contains a combination of grammar symbols with $ on the bottom

of the stack. At the start of Parsing, the stack contains the start symbol of
Grammar followed by $.
Types of Top-down Parsing
• Parsing Table − It is a two-dimensional
array or Matrix M [A, a] where A is
nonterminal and 'a' is a terminal symbol.
• Parsing Program − The parsing program
performs some action by comparing the
symbol on top of the stack and the current
input symbol to be read on the input buffer.
• Actions − The parsing program takes
various actions depending upon the symbol
on the top of the stack and the current input
symbol.

17
Thank you for listening