Name: [SOLVED] CS RECURSIVE-DESCENT PARSING
Brand: Assignment Chef
SKU: 5881769656
Price: 25 USD
Availability: InStock
Rating: 5 (1 reviews)

5/5 - (1 vote)

RECURSIVE-DESCENT PARSING
PRINCIPLES OF PROGRAMMING LANGUAGES
Norbert Zeh Winter 2021
Dalhousie University
1/5

ROAD MAP
Parsing: Transform (tokenized) program text into parse tree
Modelling programming languages: Context-free grammars and languages
Capturing the syntactic structure of a program: Parse trees
Types of parsers and types of grammars they can parse
Grammars that describe programming languages and can be parsed
efficiently
Construction of an LL(1) grammar
Parsing LL(1) languages
Push-down automata
2/5

PARSING LL(1) LANGUAGES
LL(1) languages can be parsed using efficient, easy-to-implement parsers.
Two approaches:
Recursive-descent parser
Deterministic push-down automaton (next lecture)
3/5

RECURSIVE-DESCENT PARSING
Recursive-descent parser:
For each non-terminal X, write a procedure parseX:
Choose production X Y1Y2 . . . Yk whose predictor set contains next token. For i = 1,2,,k:
If Yi is a terminal, match Y1 with next input token. If Yi is a non-terminal, call parseYi.
If next token is not in PREDICT(X ) for any of Xs productions, the parse fails (the input is syntactically incorrect).
4/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
2 * 40 18 * 3 $
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E A T E
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+, }
{n,(} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):

elif next token is * or /:
parseM() parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E A T E
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+, }
{n,(} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):

elif next token is * or /:
parseM() parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E A T E
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+, }
{n,(} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):

elif next token is * or /:
parseM() parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E A T E
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+, }
{n,(} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):

elif next token is * or /:
parseM() parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E A T E
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+, }
{n,(} {+,,$,)}
2 * 40 18 * 3 $
T MFT
Fn {n}
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):

elif next token is * or /:
parseM() parseF() parseT'()
def parseM():
if next token is *:
Match *
elif next token is /:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

elif next token is * or /:
parseM() parseF() parseT'()
def parseM():
if next token is *:
Match *
elif next token is /:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

elif next token is * or /:
parseM() parseF() parseT'()
def parseM():
if next token is *:
Match *
elif next token is /:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

elif next token is * or /:
parseM() parseF() parseT'()
def parseM():
if next token is *:
Match *
elif next token is /:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E A T E
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+, }
{n,(} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):

elif next token is * or /:
parseM() parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E A T E
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+, }
{n,(} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):

elif next token is * or /:
parseM() parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

elif next token is * or /:
parseM() parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

elif next token is * or /:
parseM() parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

elif next token is * or /:
parseM() parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

elif next token is * or /:
parseM() parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E A T E
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+, }
{n,(} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):

elif next token is * or /:
parseM() parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E A T E
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+, }
{n,(} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):

elif next token is * or /:
parseM() parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

elif next token is * or /:
parseM() parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):
Do nothing
elif next token is * or /:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

elif next token is * or /:
parseM() parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):
Do nothing
elif next token is * or /:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

elif next token is * or /:
parseM() parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):
Do nothing
elif next token is * or /:

{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E A T E
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+, }
{n,(} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseT'():
if next token is +, -, $ or ):

elif next token is * or /:
parseM() parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
T MFT
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
{,/}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseE'():
if next token is $ or ):

elif next token is + or -:
parseA() parseT() parseE'()
Fn {n} F (E) {(}
A +
A {}
M {} M/ {/}
{+}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R PREDICT(R) S E $ {n, (}
E T E {n, (}
E {$,)}
E ATE {+,} T F T {n, (}
T {+,,$,)} T MFT {,/}
Fn {n} F (E) {(}
A + {+} A {}
M {} M/ {/}
2 * 40 18 * 3 $
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseE'():
if next token is $ or ):

elif next token is + or -:
parseA() parseT() parseE'()
def parseA():
if next token is +:

elif next token is -:
Match-
5/5

elif next token is + or -:
parseA() parseT() parseE'()
def parseA():
if next token is +:

elif next token is -:
Match-
5/5

elif next token is + or -:
parseA() parseT() parseE'()
def parseA():
if next token is +:

elif next token is -:
Match-
5/5

elif next token is + or -:
parseA() parseT() parseE'()
def parseA():
if next token is +:

elif next token is -:
Match-
5/5

elif next token is + or -:
parseA() parseT() parseE'()
def parseA():
if next token is +:

elif next token is -:
Match-
5/5

elif next token is + or -:
parseA() parseT() parseE'()
Fn {n} F (E) {(}
A +
A {}
M {} M/ {/}
{+}
5/5

elif next token is + or -:
parseA() parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
Fn {n} F (E) {(}
A +
A {}
M {} M/ {/}
{+}
5/5

elif next token is + or -:
parseA() parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

Fn {n} F (E) {(}
A +
A {}
M {} M/ {/}
{+}
5/5

elif next token is + or -:
parseA() parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

Fn {n} F (E) {(}
A +
A {}
M {} M/ {/}
{+}
5/5

elif next token is + or -:
parseA() parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

Fn {n} F (E) {(}
A +
A {}
M {} M/ {/}
{+}
5/5

elif next token is + or -:
parseA() parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:

Fn {n} F (E) {(}
A +
A {}
M {} M/ {/}
{+}
5/5

elif next token is + or -:
parseA() parseT() parseE'()
def parseT():
if next token is n or (:
parseF() parseT'()
Fn {n} F (E) {(}
A +
A {}
M {} M/ {/}
{+}
5/5

RECURSIVE DESCENT PARSING: EXAMPLE
Rule R
S E $
E T E
E
E ATE
T F T T
T MFT
PREDICT(R)
{n, (}
{n, (}
{$,)} {+,}
{n, (} {+,,$,)}
{,/}
2 * 40 18 * 3 $
Fn {n} F (E) {(}
def parseS():
if next token is n or (:
parseE() Match $
def parseE():
if next token is n or (:
parseT() parseE'()
def parseE'():
if next token is $ or ):