CS计算机代考程序代写 RECURSIVE-DESCENT PARSING

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 X’s 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′
F→n {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′
F→n {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′
F→n {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′
F→n {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′
F→n {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

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′
F→n {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′
F→n {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 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′
F→n {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′
F→n {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 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′
F→n {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'()
F→n {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′ {∗,/}
F→n {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

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'()
def parseT():
if next token is n or (:
parseF() parseT'()
F→n {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'()
def parseT():
if next token is n or (:
parseF() parseT'()
def parseF():
if next token is n:
Match n
elif next token is (:
…
F→n {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'()
def parseT():
if next token is n or (:
parseF() parseT'()
F→n {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 $
F→n {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 ):
…
elif next token is + or -:
parseA() 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'()
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 $
F→n {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 ):
…
elif next token is + or -:
parseA() 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 /:
…
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 $
F→n {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 ):
…
elif next token is + or -:
parseA() 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 parseF():
if next token is n:
Match n
elif next token is (:
…
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 $
F→n {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 ):
…
elif next token is + or -:
parseA() 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 parseT'():
if next token is +, -, $ or ):
Do nothing
elif next token is * or /:
…
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'()
def parseT():
if next token is n or (:
parseF() parseT'()
F→n {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 parseE'():
if next token is $ or ):
…
elif next token is + or -:
parseA() parseT() parseE'()
def parseE'():
if next token is $ or ):
Do nothing
elif next token is + or -:
…
T′ →MFT′
F→n {n}
{∗,/} F → (E) {(}
A → + {+} A→− {−}
M→∗ {∗} M→/ {/}
5/5

Related Posts