Scribd
Upload
735 views17 pages

Types of Parser

Top-down parsers like recursive descent and LL(1) parsers start at the start symbol and use the grammar to expand non-terminals. Recursive descent parsers may require backtracking while predictive parsers use a lookahead token and parsing table to avoid backtracking. Bottom-up parsers like LR parsers start with the input tokens and use shift-reduce operations guided by a parsing table to build up the parse tree from the bottom. Both approaches have tradeoffs in terms of efficiency and classes of grammars they can handle.

Uploaded by

Nimi Khan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
735 views17 pages

Types of Parser

Top-down parsers like recursive descent and LL(1) parsers start at the start symbol and use the grammar to expand non-terminals. Recursive descent parsers may require backtracking while predictive parsers use a lookahead token and parsing table to avoid backtracking. Bottom-up parsers like LR parsers start with the input tokens and use shift-reduce operations guided by a parsing table to build up the parse tree from the bottom. Both approaches have tradeoffs in terms of efficiency and classes of grammars they can handle.

Uploaded by

Nimi Khan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

TYPES OF PARSING

Group Members:
 Laraib khan
 Jalwa
 Rabia

Compiler construction
Contents:
• Parser
• Types of parsing
• Top-down parsing
> recursive descent parser
>predictive parser
>LL parser
• Bottom-up parsing
What is Parser ?
Parser:
parser is that phase of compiler which
takes token string as input and with the help
of existing grammar, converts it into the
corresponding parse tree.
parser also known as syntax analyzer.
Types of parsing
Top-down parsing
• Top-down parser is the parser which generates
parse for the given input string with the help of
grammar productions by expanding the non-
terminals i.e.
• it starts from the start symbol (root) and ends
on the terminals (leaf). It uses left most
derivation.
• The root node is labeled with the goal symbol of
the grammar.
Classification of top-down parser
Classification of top-down parser
Recursive Descent Parsing:
Recursive descent is a top-down
parsing technique that constructs the parse tree from the top and the
input is read from left to right. It uses procedures for every terminal and
non-terminal entity. This parsing technique recursively parses the input to
make a parse tree, which may or may not require back-tracking.

• This parsing technique is regarded recursive as it uses context-free


grammar which is recursive in nature
Recursive Descent Parsing:

Back-tracking:
Top- down parsers start from the root node (start
symbol) and match the input string against the production rules to
replace them (if matched).
The right production is determined by processing the input string
more than once.
for example;
CFG:
S → rXd | rZd
X → oa | ea
Z → ai
For an input string: read, a top-down parser, will behave like this:
Example
Predictive Parser
• Predictive parser is a recursive descent parser, which
has the capability to predict which production is to be
used to replace the input string.
• The predictive parser does not suffer from backtracking.
• To accomplish its tasks, the predictive parser uses look-
ahead pointer, which points to the next input symbols.
To make the parser back-tracking free,
• the predictive parser puts some constraints on the
grammar and accepts only a class of grammar known as
LL(k) grammar.
.
Predictive Parser:
Predictive parsing uses
a stack and a parsing
table to parse the
input and generate a
parse tree. Both the
stack and the input
contains an end
symbol $ to denote
that the stack is empty
and the input is
consumed.
LL-Parser
LL parser is a top-down parser for a subset of context-
free-languages. It parses the input from left to right ,
performing leftmost derivation of the sentence.
LL parser is denoted as LL(k). The first L in LL(k) is parsing
the input from left to right, the second L in LL(k)
stands for left-most derivation and k itself represents
the number of look aheads. Generally k = 1, so LL(k)
may also be written as LL(1).
A grammar is called an LL(k) grammar if an LL(k) parser
can be constructed from it.
LL-Parser
.
Problems with Top-Down Parser
i. Left recursion:
can cause a top-down parser to go into an
infinite loop.
A grammar is said to be left-recursive if it has a non-
terminal at extreme left
ii. Back tracking:
the repeated scanning of input string.
The speed of parser is much slower.(very time
consuming).
.

You might also like