6.1120: Parsing

Top-Down Parsing

Martin Rinard

Laboratory for Computer Science

Massachusetts Institute of Technology

MIT 6.1100 (6.035) �Top-Down Parsing

Orientation

• Language specification
• Lexical structure – regular expressions
• Syntactic structure – grammar
• This Lecture - recursive descent parsers
• Code parser as set of mutually recursive procedures
• Structure of program matches structure of grammar

Starting Point

• Assume lexical analysis has produced a sequence of tokens
• Each token has a type and value
• Types correspond to terminals
• Values to contents of token read in
• Examples
• Int 549 – integer token with value 549 read in
• if - if keyword, no need for a value
• AddOp + - add operator, value +

Recognition Approach:�<2-1>+1

Open Int Op Int Close Op Int

Open Expr Op Int Close Op Int

Open Expr Op Expr Close Op Int

Open Expr Close Op Int

Expr Op Int

Expr Op Expr

Expr

Start

Op = +|-|*|/

Int = [0-9] [0-9]*

Open = <

Close = >

​

​

1) Start → Expr

2) Expr → Expr Op Expr

3) Expr → Int

4) Expr → Open Expr Close

Generative Approach: �<2-1>+1

Start

Expr

Expr Op Expr

Open Expr Close Op Expr

Open Expr Op Expr Close Op Expr

Open Int Op Expr Close Op Expr

Open Int Op Expr Close Op Int

Open Int Op Int Close Op Int

Op = +|-|*|/

Int = [0-9] [0-9]*

Open = <

Close = >

​

​

1) Start → Expr

2) Expr → Expr Op Expr

3) Expr → Int

4) Expr → Open Expr Close

Grammar for Today

Start → Expr

Expr → Expr + Term

Expr → Expr - Term

Expr → Term

Term → Term * Int

Term → Term / Int

Term → Int

• Set of tokens is { +, -, *, /, Int }, where Int = [0-9][0-9]*
• For convenience, may represent each Int n token by n

Goal: Recursive Descent Parser �(Generative/Top-Down Approach

Term()

if (token = Int n)

oldToken = token; token = NextToken();

node = TermPrime();

if (node == NULL) return oldToken;

else return(new TermNode(oldToken, node);

else throw SyntaxError

TermPrime()

if (token = *) || (token = /)

first = token; next = NextToken();

if (next = Int n)

token = NextToken();

return(new TermPrimeNode(first, next, TermPrime())

else throw SyntaxError

else return(NULL)

Basic Approach

• Start with Start symbol
• Build a leftmost derivation
• If leftmost symbol is nonterminal, choose a production and apply it
• If leftmost symbol is terminal, match against input
• If all terminals match, have found a parse!
• Key: find correct productions for nonterminals

Graphical Illustration of Leftmost Derivation

Apply Production Here

NT₁ T₁ T₂ T₃ NT₂ NT₃

Not Here

Sentential Form

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Start

Current Position in Parse Tree

Parsing Example

Applied Production

Start → Expr

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Expr

Expr

Current Position in Parse Tree

Parsing Example

Applied Production

Expr → Expr - Term

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Expr - Term

Start

Expr

Term

Expr

-

Parsing Example

Expr → Expr + Term

Expr → Expr - Term

Expr → Term

Applied Production

Expr → Term

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Term - Term

Expr

Term

Expr

-

Term

Parsing Example

Expr → Expr + Term

Expr → Expr - Term

Expr → Term

Applied Production

Term → Int

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Expr

Term

Expr

-

Term

Int

Int - Term

Parsing Example

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

2 - Term

Expr

Term

Expr

-

Term

Match

Input

Token!

Int 2

Parsing Example

Start

Parse

Tree

Sentential Form

Remaining Input

-2*2

2 - Term

Expr

Term

Expr

-

Term

Match

Input

Token!

Int 2

Parsing Example

Start

Parse

Tree

Sentential Form

Remaining Input

2*2

2 - Term

Expr

Term

Expr

-

Term

Match

Input

Token!

Int 2

Parsing Example

Applied Production

Term → Term * Int

Start

Parse

Tree

Sentential Form

Remaining Input

2*2

2 - Term*Int

Expr

Term

Expr

-

Term

Term

Int

*

Int 2

Parsing Example

Applied Production

Term → Int

Start

Parse

Tree

Sentential Form

Remaining Input

2*2

2 - Int * Int

Expr

Term

Expr

-

Term

Term

Int

*

Int 2

Int

Parsing Example

Match

Input

Token!

Start

Parse

Tree

Sentential Form

Remaining Input

2*2

2 - 2* Int

Expr

Term

Expr

-

Term

Term

Int

*

Int 2

Int 2

Parsing Example

Match

Input

Token!

Start

Parse

Tree

Sentential Form

Remaining Input

*2

2 - 2* Int

Expr

Term

Expr

-

Term

Term

Int

*

Int 2

Int 2

Parsing Example

Match

Input

Token!

Start

Parse

Tree

Sentential Form

Remaining Input

2

2 - 2* Int

Expr

Term

Expr

-

Term

Term

Int

*

Int 2

Int 2

Parsing Example

Parsing Example

Start

Parse

Tree

Sentential Form

Remaining Input

2

2 - 2*2

Expr

Term

Expr

-

Term

Term

Int 2

*

Int 2

Int 2

Parse

Complete!

Summary

• Three Actions (Mechanisms)
• Apply production to expand current nonterminal in parse tree
• Match current terminal (consuming input)
• Accept the parse as correct
• Parser generates preorder traversal of parse tree
• visit parents before children
• visit siblings from left to right

Act 1

Policy Problem

• Which production to use for each nonterminal?
• Classical Separation of Policy and Mechanism
• One Approach: Backtracking
• Treat it as a search problem
• At each choice point, try next alternative
• If it is clear that current try fails, go back to previous choice and try something different
• General technique for searching
• Used a lot in classical AI and natural language processing (parsing, speech recognition)

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Start

Applied Production

Start → Expr

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Expr

Expr

Applied Production

Expr → Expr + Term

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Expr + Term

Expr

Term

Expr

+

Applied Production

Expr → Term

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Term + Term

Expr

Term

Expr

+

Term

Applied Production

Term → Int

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Int + Term

Expr

Term

Expr

+

Term

Int

Match

Input

Token!

Applied Production

Term → Int

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

-2*2

2 + Term

Expr

Term

Expr

+

Term

Int 2

Can’t

Match

Input

Token!

Applied Production

Start → Expr

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Expr

Expr

So

Backtrack!

Applied Production

Expr → Expr - Term

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Expr - Term

Expr

Term

Expr

-

Term

Applied Production

Expr → Term

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Term - Term

Expr

Term

Expr

-

Term

Applied Production

Term → Int

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

2-2*2

Int - Term

Expr

Term

Expr

-

Int

Match

Input

Token!

Term

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

-2*2

2 - Term

Expr

Term

Expr

-

Int 2

Match

Input

Token!

Term

Backtracking Example

Start

Parse

Tree

Sentential Form

Remaining Input

2*2

2 - Term

Expr

Term

Expr

-

Int 2

Act 2

Any one see a problem?

• Example Production: Term → Term*Num
• Potential parsing steps:

Term

Num

*

Term

Term

Term

Num

*

Term

Term

Num

*

Left Recursion + Top-Down Parsing = Infinite Loop

• Example Production: Term → Term*Num
• Potential parsing steps:

Term

Num

*

Term

Term

Term

Num

*

Term

Term

Num

*

General Search Issues

• Three components
• Search space (parse trees)
• Search algorithm (parsing algorithm)
• Goal to find (parse tree for input program)
• Would like to (but can’t always) ensure that
• Find goal (hopefully quickly) if it exists
• Search terminates if it does not
• Handled in various ways in various contexts
• Finite search space makes it easy
• Exploration strategies for infinite search space
• Sometimes one goal more important (model checking)
• For parsing, hack grammar to remove left recursion

Eliminating Left Recursion

• Start with productions of form
• A →A α
• A → β
• α, β sequences of terminals and nonterminals that do not start with A
• Repeated application of A →A α

builds parse tree like this:

A

α

A

α

A

α

β

Eliminating Left Recursion

• Replacement productions
• A →A α A → β R R is a new nonterminal
• A → β R → α R
• R → ε

A

α

A

α

β

A

β

R

α

R

α

R

ε

Old Parse Tree

New Parse Tree

Hacked Grammar

Original Grammar Fragment

Term → Term * Int

Term → Term / Int

Term → Int

New Grammar Fragment

Term → Int Term’

Term’ → * Int Term’

Term’ → / Int Term’

Term’ → ε

Term

Int

*

Term

Int

*

Int

Term

Int

Term’

Int

*

Term’

Int

*

Term’

ε

Parse Tree Comparisons

Original Grammar

New Grammar

Eliminating Left Recursion

• Changes search space exploration algorithm
• Eliminates direct infinite recursion
• But grammar less intuitive
• Sets things up for predictive parsing

Act 3

Predictive Parsing

• Alternative to backtracking
• Useful for programming languages, which can be designed to make parsing easier
• Basic idea
• Look ahead in input stream
• Decide which production to apply based on next tokens in input stream
• We will use one token of lookahead
• (Getting closer in form to our recognition approach – but not quite…see 6.1100!)

Predictive Parsing Example Grammar

Start → Expr

Expr → Term Expr’

Expr’ → + Term Expr’

Expr’ → - Term Expr’

Expr’ → ε

Term → Int Term’

Term’ → * Int Term’

Term’ → / Int Term’

Term’ → ε

Choice Points

• Assume Term’ is current position in parse tree
• Have three possible productions to apply

Term’ → * Int Term’

Term’ → / Int Term’

Term’ → ε

• Use next token to decide
• If next token is *, apply Term’ → * Int Term’
• If next token is /, apply Term’ → / Int Term’
• Otherwise, apply Term’ → ε

Predictive Parsing Example

Start

Parse

Tree

Sentential Form

Remaining Input

*2

2 - 2 Term’

Expr

Term

Term

Int 2

Term’

ε

Expr’

Term

Int 2

Term’

-

Term → Int Term’

Term’ → * Int Term’

Term’ → / Int Term’

Term’ → ε

Predictive Parsing Example

Start

Parse

Tree

Sentential Form

Remaining Input

*2

2 - 2 Term’

Expr

Term

Term

Int 2

Term’

ε

Expr’

Int 2

Term’

-

Applied Production

Term’ → * Int Term’

*

Term’

Int

Predictive Parsing + Hand Coding = Recursive Descent Parser

• One procedure per nonterminal NT
• Productions NT → β₁ , …, NT → β_n
• Procedure examines the current input symbol T to determine which production to apply
• If T∈First(β_k) (we still discuss first next lecture)
• Apply production k
• Consume terminals in β_k (check for correct terminal)
• Recursively call procedures for nonterminals in β_k
• Current input symbol stored in global variable token
• Procedures return the section of the parse tree for the part of the string it parsed

Example

Boolean Term()

if (token = Int n) token = NextToken(); return(TermPrime())

else return(false)

Boolean TermPrime()

if (token = *)

token = NextToken();

if (token = Int n) token = NextToken(); return(TermPrime())

else return(false)

else if (token = /)

token = NextToken();

if (token = Int n) token = NextToken(); return(TermPrime())

else return(false)

else return(true)

Term → Int Term’

Term’ → * Int Term’

Term’ → / Int Term’

Term’ → ε

Next time: Parse

Term()

if (token = Int n)

oldToken = token; token = NextToken();

node = TermPrime();

if (node == NULL) return oldToken;

else return(new TermNode(oldToken, node);

else throw SyntaxError

TermPrime()

if (token = *) || (token = /)

first = token; next = NextToken();

if (next = Int n)

token = NextToken();

return(new TermPrimeNode(first, next, TermPrime())

else throw SyntaxError

else return(NULL)

Term → Int Term’

Term’ → * Int Term’

Term’ → / Int Term’

Term’ → ε

Building A Parse Tree

• Have each procedure return the section of the parse tree for the part of the string it parsed
• Use exceptions to make code structure clean

Term

Int

2

Term’

Int

3

*

Term’

Int

4

*

Term’

ε

Parse Tree