Scribd
Upload
5 views

Unit 2 Basic Parsing Techniques

The document discusses parsing techniques, specifically top-down and bottom-up parsing, detailing their principles and types. It covers issues such as backtracking, left recursion, left factoring, and ambiguity in grammars, along with methods for their resolution. Additionally, it explains the recursive descent parser and predictive parser, highlighting their construction and implementation requirements.

Uploaded by

pandeyakshay301
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
5 views

Unit 2 Basic Parsing Techniques

The document discusses parsing techniques, specifically top-down and bottom-up parsing, detailing their principles and types. It covers issues such as backtracking, left recursion, left factoring, and ambiguity in grammars, along with methods for their resolution. Additionally, it explains the recursive descent parser and predictive parser, highlighting their construction and implementation requirements.

Uploaded by

pandeyakshay301
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
You are on page 1/ 34

Basic Parsing

Techniques
Dr. Sushil Kumar
Parsing Techniques
• There are two parsing techniques:

1. Top-down parsing
2. Bottom-up parsing
Principle of parsing techniques
• Parser scans the input string from left to right
• Parser identifies the leftmost or rightmost derivation
• Parser uses the production rules for choosing the
appropriate derivation
• The different parsing techniques use different
approaches in selecting the appropriate rules for
derivation
Types of Parsing
Top Down parser
• When the parser starts constructing the parse tree from the
start symbol and then tries to transform the start symbol to the
input, it is called top-down parsing.
• Recursive descent parsing : It is a common form of top-down
parsing. It is called recursive as it uses recursive procedures to process
the input. Recursive descent parsing suffers from backtracking.
• Backtracking : It means, if one derivation of a production fails, the
syntax analyzer restarts the process using different rules of same
production. This technique may process the input string more than
once to determine the right production.
Bottom-up Parsing

• bottom-up parsing starts with the input symbols and tries to


construct the parse tree up to the start symbol.
Example:
• Input string : a + b * c
• Production rules: S → E
E → E + T
E → E * T
E → T
T → id
• Top-down parser: ?
• Bottom-Up parser: ?
Types of Top-Down Parser
Recursive Descent Parsing
• 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.

• A form of recursive-descent parsing that does not require any


back-tracking is known as .
Predictive Parsing

• A form of recursive-descent parsing that does not require any


back-tracking is known as predictive parsing.
Problems with Top-down Parsing

1. Backtracking
2. Left recursion
3. Left Factoring
4. Ambiguity
1. Backtracking
• Backtracking is a technique in which for expansion of non-terminal
symbol we choose one alternative and if some mismatch occurs then
we try another alternative if any.
• Example: S -> xPz
P -> yw | y
Input String: xyz
2. Left Recursion
that there is a derivation of the form A=> Aa for some ∝
• A grammar G is said to be left recursive if it has an non-terminal A such

• Examples:
S → Sa | b
S → Ab A → Ad | Sa | e
S → Ac A→Ab | Bc | a B → Bb | Aa | Sc | b
Elimination of Left Recursion which
is immediate
• Grammar Containing Left Recursion

A→A∝1 | A∝2 | ……. | A∝m | β1 | β2 | ….| βn

• Eliminate left recursion by re-writing the production rule as:

A→β1A'|β2A'|......|βnA’
A'→∝1A'|∝2A'|....|∝mA’|∈

Where A' is anew non-terminal introduced


Example 1: S→ Sa |b

• After eliminating left recursion S→bS’, S'→ aS'|∈


Example 2: E→E+T | T, T→T*F|F,
F→(E)|id
• Here only E and T are left recursive, after eliminating
left recursion
E→TE’
E'→+TE’|∈
T→FT’
T'→FT’|∈
F→(E)|id
Example 3:
• Remove left recursion Grammar after removal of left
recursion
A -> Abd | Aa | a
B -> Be | b A -> aA’
A’ -> bdA’ | aA’ | Є
B -> bB’
B’ -> eB’ | Є
3. Left Factoring
• Left factoring is used when it is not clear that which of the two or
more alternatives are used to expand the non-terminal.

A -> ∝ β1 | ∝ β2 | ∝ β3 |…………..| ∝ βn

A -> ∝A’
• After removal of left factoring:

A -> β1 | β2 | β3|…………..| βn
Example 1: Consider the following Grammar:
S -> iEtS | iEtSeS |a
E -> b
After removal of left factoring:

S -> iEtSS’ | a
S’ -> Є | eS
E -> b
Example 2: Remove left factoring
A -> aAB | aA | a
B -> bB | b

A -> aA’
A’ -> AB | a | Є
B -> bB’
B’ -> b | Є
4. Ambiguity
• The ambiguous grammar is not desirable in top-down parsing.
• Hence, we need to remove the ambiguity from the grammar if it is
present
• How to check the ambiguity?
1. If we find two or more leftmost derivation for particular input string or
2. If we find two or more rightmost derivation for particular input string
• Example: Check the following grammar is ambiguous or not.
E -> E+E | E*E | id
How to remove ambiguity?
1. If the grammar has left associative operator (such as +,-,*,/)
1. Then induce left recursion

2. If the grammar has right associative operator (exponential operator)


1. Then induce right recursion
Example :
E -> E+E E -> E + T E -> TE’
E -> E*E E -> T E’ -> +TE’ | Є
T -> T*F T -> FT’
E -> id
T -> F T’ -> *FT’ | Є
F -> id
F -> id

Grammar is Grammar is
ambiguous. Grammar is unambiguous as
unambiguous but well as free from
left recursion. left recursion.
Types of top-down parsing

Top Down
Parser

Predictive
Backtracking
Parser

Recursive- Descent
LL(1) Parser
(RD) Parser
Backtracking Parsing
• A backtracking parser tries different production rules to find
the match for the input string (Brute-force method).
• Backtracking parser is powerful than predictive parser.
• But backtracking is slower and requires exponential time in
general.
• Hence, backtracking is not preferred for practical
implementation of compilers.
Predictive Parser
• This parser tries to predict the next construction using one or more
lookahead symbols from input string.
• There are two types of predictive parser:
1. Recursive –Descent (RD) Parser
2. LL(1) parser:
First L stands for Left to right scanning, second L stands for
Leftmost derivation, and 1 means that it uses only one input
symbol (lookahead) to predict the parsing process.
Recursive –Descent (RD) Parser

• A parser that uses collection of recursive procedures for


parsing the given input string is called Recursive
Descent (RD) Parser.
• In this parser, we use CFG to build the recursive
routines (procedures)
For implementing a recursive
descent parser for a grammar

• The grammar must not be left recursive


• The grammar must not be left factored that means it
should not have common prefixes for alternates
• We need a language that has recursion facility
Basic steps for construction of RD
parser:
1. The R.H.S. of the rule is directly converted into program code
symbol by symbol.
2. If the input is non-terminal then a call to the procedure
corresponding to the non-terminal is made.
3. If the input is terminal then it is matched with the lookahead
from input. The lookahead pointer has to be advanced on
matching of the input symbol.
4. If the production rule has many alternates then all these
alternates has to be combine into a single body of procedure.
5. The parser should be activated by a procedure corresponding
to the start symbol.
Example:
• Consider the Grammar
E → TE’
E' → +TE' | ε
Transition Diagram
T → FT'
T' → *FT' | ε
F → (E) | id
Improvement on the transition
diagrams
Improved version of the transition
diagram
Exercise: E -> num T
T -> *num T | Є
• Write Pseudo code for RD parser

You might also like