Scribd
Upload
13 views9 pages

Lec3 SyntaxAnalysis Part3

The document discusses top-down parsing techniques, including recursive descent and predictive parsing, which construct parse trees starting from the root. It explains the concepts of FIRST and FOLLOW sets, which are essential for making parsing decisions in predictive parsers, particularly for LL(1) grammars. The document emphasizes the importance of avoiding left recursion and ambiguity in grammar design for effective predictive parsing.

Uploaded by

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

Lec3 SyntaxAnalysis Part3

The document discusses top-down parsing techniques, including recursive descent and predictive parsing, which construct parse trees starting from the root. It explains the concepts of FIRST and FOLLOW sets, which are essential for making parsing decisions in predictive parsers, particularly for LL(1) grammars. The document emphasizes the importance of avoiding left recursion and ambiguity in grammar design for effective predictive parsing.

Uploaded by

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

CSN-352

Syntax Analysis
Grammar and Parsing
Top Down Parsing

Top-down parsing can be viewed as the problem of constructing a


parse tree for the input string, starting from the root and creating
the nodes of the parse tree in preorder (depth-first).

- top-down parsing can also be viewed as finding a leftmost


derivation for an input string.

- Recursive Descendent Parsing


- Predictive Parsing – Having Look Ahead
Generic Top Down Parsing

- Has a set of procedure, one for each


non terminal.
- Procedure begins with the start
symbol, halts when it scans the entire
input string.

- What if there is not a match


between the current input symbol and
the current terminal at leaf of the
parse tree? -backtrack for more
productions of A

- What if there are more than one A-


productions at point-1 of the
algorithm, which one to chose?
First and Follow

- During topdown parsing, FIRST and FOLLOW allow us to choose which


production to apply, based on the next input symbol.

FIRST:
α is any string of grammar symbols,
FIRST(α) is the set of terminals that begin strings derived from α.
If α=>^ then FIRST(α) = {^}
If A=> cy, then FIRST(A) = {c}

Follow:
FOLLOW(A) is the set of terminals a that can appear immediately to the right of A in
some sentential form;
S -> αAaß

If $ is the rightmost symbol in some sentential form, then $ (end marker) is in


FOLLOW(A).
FIRST(X) for all Grammar Symbols X
FOLLOW(X) for all Grammar Symbols X

1. Place $ in FOLLOW(S), where S is the start symbol, and $ is the input


right endmarker.

2. If there is a production A ->αBß, then everything in FIRST(ß) except ^


is in FOLLOW(B).

3. If there is a production A -> αB, or a production A ->αBß, where


FIRST(A ->αBß) contains ^, then everything in FOLLOW(A) is in
FOLLOW(B).
Predictive Parsing and LL(1) Grammars

- Predictive parsers, that is, recursive-descent parsers needing no


backtracking, can be constructed for a class of grammars called LL(1).

L – Scan input from left to right.


L – Producing a leftmost derivation
1 - for using one input symbol of lookahead at each step to make parsing
action decisions.

- The class of LL(1) grammars is rich enough to cover most programming


Constructs.
- Need extra care in designing of grammar, no left recursive grammar or
ambiguous grammar can be LL(1).
Predictive Parsing and LL(1) Grammars

A grammar is LL(1): A ->α|ß

First(α) First(ß)
are disjoint sets.

First(α) and
Follow(A) are
disjoint sets and
likewise if ^ is in
FIRST(α)
Predictive Parsing
Generate Predictive Parsing Table M[A,a], where A is a non-terminal, a is a terminal

If, after performing the above, there is no production at all in M[A; a], then
set M[A; a] to error (which we normally represent by an empty entry in the
table).

You might also like