[SOLVED] CS TYPES OF PARSERS

TYPES OF PARSERS
PRINCIPLES OF PROGRAMMING LANGUAGES
Norbert Zeh Winter 2021
Dalhousie University
1/14

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/14

EFFICIENT PARSERS
Programming language parsers should be efficient:
Any context-free grammar can be used to derive a parser that runs in O(n3) time.
We want linear time.
3/14

EFFICIENT PARSERS
Programming language parsers should be efficient:
Any context-free grammar can be used to derive a parser that runs in O(n3) time.
We want linear time.
Question: What types of grammars admit linear-time parsers?
3/14

EFFICIENT PARSERS
Programming language parsers should be efficient:
Any context-free grammar can be used to derive a parser that runs in O(n3) time.
We want linear time.
Question: What types of grammars admit linear-time parsers? Most common parser types:
Recursive-descent parser Shift-reduce parser
3/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Input
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Phrase Verb Phrase
Input
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase
Input
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase
Input
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase Jim ate Phrase
Input
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase Jim ate Phrase Jim ate Noun
Input
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase Jim ate Phrase Jim ate Noun Jim ate cheese
Input
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase Jim ate Phrase Jim ate Noun Jim ate cheese
Finding a leftmost derivation incrementally
Sentential form
Sentence
Input
Jim ate cheese
Input left to consume
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase Jim ate Phrase Jim ate Noun Jim ate cheese
Finding a leftmost derivation incrementally
Sentential form
Sentence
Phrase Verb Phrase
Input
Jim ate cheese
Input left to consume
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase Jim ate Phrase Jim ate Noun Jim ate cheese
Finding a leftmost derivation incrementally
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase
Input
Jim ate cheese
Input left to consume
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase Jim ate Phrase Jim ate Noun Jim ate cheese
Finding a leftmost derivation incrementally
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase
Input
Jim ate cheese
Input left to consume
Jim ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Finding a leftmost derivation incrementally
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase
Verb Phrase
Sentence
Phrase Verb
Noun Verb
Jim Verb
Jim ate
Jim ate
Jim ate cheese
Input
Jim ate cheese
Input left to consume
Phrase Phrase Phrase Phrase Noun
ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Finding a leftmost derivation incrementally
Sentential form
Sentence
Phrase Verb Phrase Noun Verb Phrase Jim Verb Phrase
Verb Phrase ate Phrase
Sentence
Phrase Verb
Noun Verb
Jim Verb
Jim ate
Jim ate
Jim ate cheese
Input
Jim ate cheese
Input left to consume
Phrase Phrase Phrase Phrase Noun
ate cheese 4/14

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Finding a leftmost derivation incrementally
Sentential form
Sentence
Phrase Verb
Noun Verb
Jim Verb
Jim ate
Jim ate
Jim ate cheese
Sentence Phrase Verb Noun Verb Jim Verb
Verb
ate
Phrase Phrase Phrase Phrase Phrase Phrase
Input
Jim ate cheese
Input left to
consume
cheese 4/14
Phrase Phrase Phrase Phrase Noun

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Finding a leftmost derivation incrementally
Sentential form
Sentence
Phrase Verb
Noun Verb
Jim Verb
Jim ate
Jim ate
Jim ate cheese
Sentence Phrase Verb Noun Verb Jim Verb
Verb
ate
Phrase Phrase Phrase Phrase Phrase Phrase Noun
consume
cheese 4/14
Input
Jim ate cheese
Input left to
Phrase Phrase Phrase Phrase Noun

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Finding a leftmost derivation incrementally
Sentential form
Sentence
Phrase Verb
Noun Verb
Jim Verb
Jim ate
Jim ate
Jim ate cheese
Sentence Phrase Verb Noun Verb Jim Verb
Verb
ate
Phrase Phrase Phrase Phrase Phrase Phrase Noun cheese
consume
cheese 4/14
Input
Jim ate cheese
Input left to
Phrase Phrase Phrase Phrase Noun

FINDING A LEFTMOST DERIVATION
Leftmost derivation
Sentential form
Finding a leftmost derivation incrementally
Sentential form
Sentence
Phrase Verb
Noun Verb
Jim Verb
Jim ate
Jim ate
Jim ate cheese
Sentence Phrase Verb Noun Verb Jim Verb
Verb
ate
Phrase Phrase Phrase Phrase Phrase Phrase Noun cheese
consume
Input
Jim ate cheese
Input left to
Phrase Phrase Phrase Phrase Noun
4/14

RECURSIVE-DESCENT PARSING (1)
5/14

RECURSIVE-DESCENT PARSING (1)
Start with the start symbol ( = S)
5/14

RECURSIVE-DESCENT PARSING (1)
Start with the start symbol ( = S)
While the current sentential form and the input text are not empty:
5/14

RECURSIVE-DESCENT PARSING (1)
Start with the start symbol ( = S)
While the current sentential form and the input text are not empty:
If the first symbol in is a terminal x:
If the first symbol in is a non-terminal X,
5/14

RECURSIVE-DESCENT PARSING (1)
Start with the start symbol ( = S)
While the current sentential form and the input text are not empty:
If the first symbol in is a terminal x:
If x is also the first symbol in , then consume x, that is, remove it
from both and .
If the first symbol in is a non-terminal X,
5/14

RECURSIVE-DESCENT PARSING (1)
Start with the start symbol ( = S)
While the current sentential form and the input text are not empty:
If the first symbol in is a terminal x:
If x is also the first symbol in , then consume x, that is, remove it
from both and .
If x is not the first symbol in , then the parse fails.
If the first symbol in is a non-terminal X,
5/14

RECURSIVE-DESCENT PARSING (1)
Start with the start symbol ( = S)
While the current sentential form and the input text are not empty:
If the first symbol in is a terminal x:
If x is also the first symbol in , then consume x, that is, remove it
from both and .
If x is not the first symbol in , then the parse fails.
If the first symbol in is a non-terminal X, then choose a production X and replace X with in .
5/14

RECURSIVE-DESCENT PARSING (1)
Start with the start symbol ( = S)
While the current sentential form and the input text are not empty:
If the first symbol in is a terminal x:
If x is also the first symbol in , then consume x, that is, remove it
from both and .
If x is not the first symbol in , then the parse fails.
If the first symbol in is a non-terminal X, then choose a production X and replace X with in .
If = and = , the parse succeeds; otherwise, it fails.
5/14

RECURSIVE-DESCENT PARSING (2)
This is also called LL-parsing because it consumes the input Left-to-right and produces a Leftmost derivation.
It is one form of top-down parsing because we start with the start symbol S and construct the parse tree top-down.
6/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
Input string
Stack
S1
+*+2345 S1
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1
Input string
Stack
+*+2345 S1
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1
Input string
+*+2345
Stack
+S2 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2
S3
Input string
+*+2345
Stack
+S2 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2
S3
Input string
+*+2345
Stack
+S2 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2
S3
Input string
* + 2 3 4 5
Stack
S2 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2
S3
Input string
* + 2 3 4 5
Stack
S2 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2
S3
Input string
*+2345
Stack
*S4 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2 S4
S3 S5
*
Input string
*+2345
Stack
*S4 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2 S4
S3 S5
*
Input string
*+2345
Stack
*S4 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4
S3 S5
Input string
+ 2 3 4 5
Stack
S4 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4
S3 S5
Input string
+ 2 3 4 5
Stack
S4 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2 S4
S3 S5
*
Input string
+2345
Stack
+S6 S7 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2 S4 S6
S3 S5
S7
*
+
Input string
+2345
Stack
+S6 S7 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2 S4 S6
S3 S5
S7
*
+
Input string
+2345
Stack
+S6 S7 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2 S4 S6
S3 S5
S7
*
+
Input string
2345
Stack
S6 S7 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2 S4 S6
S3 S5
S7
*
+
Input string
2345
Stack
S6 S7 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1 S2 S4 S6
S3 S5
S7
*
+
Input string
2345
Stack
intS7 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1
S2
S4
S6
int
S3 S5
S7
*
+
Input string
2345
Stack
intS7 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1
S2
S4
S6
int
S3 S5
S7
*
+
Input string
2345
Stack
intS7 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6 2
Input string
3 4 5
S3 S5
S7
Stack
S7 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6 2
Input string
3 4 5
S3 S5
S7
Stack
S7 S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6 2
Input string
3 4 5
S3 S5
S7
Stack
int S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1
S2
S4
S6
S3 S5
S7
*
+
Input string
3 4 5
2 int
Stack
int S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
+
S1
S2
S4
S6
S3 S5
S7
*
+
Input string
3 4 5
2 int
Stack
int S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6
Input string
4 5
S3 S5
S7 2 3
Stack
S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6
Input string
4 5
S3 S5
S7 2 3
Stack
S5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6
Input string
4 5
S3 S5
S7 2 3
Stack
int S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6
Input string
4 5
S3 S5
int
S7 2 3
Stack
int S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6
Input string
4 5
S3 S5
int
S7 2 3
Stack
int S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6
Input string
S3 S5
4
S7 2 3
Stack
5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6
Input string
S3 S5
4
S7 2 3
Stack
5 S3
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
Parse tree
S1 + S2 * S4 + S6
Input string
5
S3 S5
S7 2 3
Stack
int
4
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
+
Parse tree
S1
S2 S3
S4 S5int
*
+ S6 S7 2 3
4
Input string
5
Stack
int
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
+
Parse tree
S1
S2 S3
S4 S5int
*
+ S6 S7 2 3
4
Input string
5
Stack
int
7/14

RECURSIVE-DESCENT PARSING: EXAMPLE
An S-grammar for arithmetic expressions in Polish notation:
S + S S S – S S S * S S S / S S S neg S
S int
(2 + 3) * 4 + 5 + * + 2 3 4 5
+
Parse tree
S1
S2 S3
S4 S5 5 + S6 S7 4
2 3
Stack
*
Input string
7/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
Finding a rightmost derivation incrementally
Input
Jim ate cheese
Sentential form
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
Finding a rightmost derivation incrementally
Input
Sentential form
Jim
ate cheese
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
Finding a rightmost derivation incrementally
Input Sentential form
Jim
Noun
ate cheese
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
Finding a rightmost derivation incrementally
Input Sentential form
Jim
Noun Phrase
ate cheese
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
Finding a rightmost derivation incrementally
Input Sentential form
Jim
Noun Phrase Phrase ate
cheese
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
Finding a rightmost derivation incrementally
Input Sentential form
Jim
Noun Phrase Phrase ate Phrase Verb
cheese
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
Finding a rightmost derivation incrementally
Input Sentential form
Jim
Noun
Phrase
Phrase ate
Phrase Verb
Phrase Verb cheese
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
Finding a rightmost derivation incrementally
Input Sentential form
Jim
Noun
Phrase
Phrase ate
Phrase Verb
Phrase Verb cheese Phrase Verb Noun
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
Finding a rightmost derivation incrementally
Input Sentential form
Jim
Noun
Phrase
Phrase ate
Phrase Verb
Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase
8/14

FINDING A RIGHTMOST DERIVATION
Rightmost derivation
Input
Jim ate cheese
Sentential form
Jim ate cheese Noun ate cheese Phrase ate cheese Phrase Verb cheese Phrase Verb Noun Phrase Verb Phrase Sentence
Finding a rightmost derivation incrementally
Input Sentential form
Jim
Noun
Phrase
Phrase ate
Phrase Verb
Phrase Verb cheese
Phrase Verb Noun
Phrase Verb Phrase
Sentence 8/14

SHIFT-REDUCE PARSING (1)
9/14

SHIFT-REDUCE PARSING (1)
Begin with an empty stack R
9/14

SHIFT-REDUCE PARSING (1)
Begin with an empty stack R
While R does not contain the start symbol S and the input = , either
9/14

SHIFT-REDUCE PARSING (1)
Begin with an empty stack R
While R does not contain the start symbol S and the input = , either
Shift the next input symbol from to R (remove it from and push it onto R).
9/14

SHIFT-REDUCE PARSING (1)
Begin with an empty stack R
While R does not contain the start symbol S and the input = , either
Shift the next input symbol from to R (remove it from and push it onto R).
Reduce R by choosing a production X such that is the sequence of symbols on the top of R and replace with X in R.
9/14

SHIFT-REDUCE PARSING (1)
Begin with an empty stack R
While R does not contain the start symbol S and the input = , either
Shift the next input symbol from to R (remove it from and push it onto R).
Reduce R by choosing a production X such that is the sequence of symbols on the top of R and replace with X in R.
The parse succeeds if and only if S is the only symbol on R and =attheend.
9/14

SHIFT-REDUCE PARSING (2)
This is also called LR-parsing because it consumes the input Left-to-right and produce a Rightmost derivation in reverse.
It is a form of bottom-up parsing because it produces the parse tree from the leaves up.
10/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
Input string
234+*5+
Stack
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
Input string
Stack
34+*5+ 2
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
2
Input string
Stack
34+*5+ 2
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
2
Input string
Stack
34+*5+ 2
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 2
Input string
Stack
34+*5+ 2
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 2
Input string
Stack
34+*5+ S1
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 2
Input string
Stack
34+*5+ S1
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 2
Input string
4+*5+
Stack
S1 3
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 2
3
Input string
4+*5+
Stack
S1 3
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 2
3
Input string
4+*5+
Stack
S1 3
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2
3
Input string
4+*5+
Stack
S1 3
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2
3
Input string
4 + * 5 +
Stack
S1 S2
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2
3
Input string
4 + * 5 +
Stack
S1 S2
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2
3
Input string
+ * 5 +
Stack
S1 S2 4
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2
3 4
Input string
+ * 5 +
Stack
S1 S2 4
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2
3 4
Input string
+ * 5 +
Stack
S1 S2 4
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2 S3
3 4
Input string
+ * 5 +
Stack
S1 S2 4
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2 S3
3 4
Input string
+ * 5 +
Stack
S1 S2 S3
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2 S3
3 4
Input string
+ * 5 +
Stack
S1 S2 S3
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2 S3
3 4
Input string
* 5 +
Stack
S1 S2 S3 +
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2
S3 + 3 4
Input string
* 5 +
Stack
S1 S2 S3 +
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1
2 S2
S3 + 3 4
Input string
* 5 +
Stack
S1 S2 S3 +
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 S4
2 S2
3 4
Input string
* 5 +
S3 +
Stack
S1 S2 S3 +
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 S4
2 S2
3 4
Input string
* 5 +
S3 +
Stack
S1 S4
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 S4
2 S2
3 4
Input string
* 5 +
S3 +
Stack
S1 S4
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 S4
2 S2
3 4
Input string
5 +
S3 +
Stack
S1 S4 *
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 S4
*
2 S2
3 4
Input string
5 +
S3 +
Stack
S1 S4 *
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S1 S4
*
2 S2
3 4
Input string
5 +
S3 +
Stack
S1 S4 *
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S +
S S S – S5 S S S *
S S S /
S S neg
Parse tree
S1 S4
*
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
2 S2
3 4
Input string
5 +
S3 +
Stack
S1 S4 *
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S +
S S S – S5 S S S *
S S S /
S S neg
Parse tree
S1 S4 *
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
2 S2
3 4
Input string
S3 +
5+ S5
11/14
Stack

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S +
S S S – S5 S S S *
S S S /
S S neg
Parse tree
S1 S4 *
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
2 S2
3 4
Input string
S3 +
5+ S5
11/14
Stack

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S +
S S S – S5 S S S *
S S S /
S S neg
Parse tree
S1 S4 *
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
2 S2
3 4
Input string
S3 +
+ S55
11/14
Stack

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S +
S S S – S5 S S S *
S S S /
S S neg
Parse tree
S1 S4
* 5
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
2 S2
3 4
Input string
S3 +
+ S55
11/14
Stack

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S +
S S S – S5 S S S *
S S S /
S S neg
Parse tree
S1 S4
* 5
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
2 S2
3 4
Input string
S3 +
+ S55
11/14
Stack

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S5 S1 S4
S6 * 5
2 S2
3 4
Input string
S3 +
+ S55
11/14
Stack

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S5 S1 S4
S6 * 5
2 S2
3 4
Input string
S3 +
+ S5S6
11/14
Stack

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S5 S1 S4
S6 * 5
2 S2
3 4
Input string
S3 +
+ S5S6
11/14
Stack

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S5 S1 S4
S6 * 5
2 S2
S3 +
3 4
Input string
Stack
S5 S6 +
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S5 S1 S4
S6 + * 5
2 S2
S3 +
3 4
Input string
Stack
S5 S6 +
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S5 S1 S4
S6 + * 5
2 S2
S3 +
3 4
Input string
Stack
S5 S6 +
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S5 S1 S4
S7
S6 + * 5
2 S2
S3 +
3 4
Input string
Stack
S5 S6 +
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S5 S1 S4
S7
S6 + * 5
2 S2
S3 +
3 4
Input string
Stack
S7
11/14

SHIFT-REDUCE PARSING: EXAMPLE
A grammar for arithmetic expressions in reverse Polish notation:
S S S + S S S – S S S * S S S / S S neg
S int
2 * (3 + 4) + 5 2 3 4 + * 5 +
Parse tree
S5 S1 S4
S7
S6 + * 5
2 S2
S3 +
3 4
Input string
Stack
S7
11/14

DETERMINISTIC PARSERS AND LOOK-AHEAD
Key question for top-down parsers: Which production do I use to expand the next non-terminal?
12/14

DETERMINISTIC PARSERS AND LOOK-AHEAD
Key question for top-down parsers: Which production do I use to expand the next non-terminal?
Key questions for bottom-up parsers:
When do I shift, when do I reduce?
Which production do I use to reduce the top of the stack?
12/14

DETERMINISTIC PARSERS AND LOOK-AHEAD
Key question for top-down parsers: Which production do I use to expand the next non-terminal?
Key questions for bottom-up parsers:
When do I shift, when do I reduce?
Which production do I use to reduce the top of the stack?
A parser is deterministic if it does not have to guess the answers to these questions and always makes the right choice (assuming the input can be produced using the given grammar).
12/14

DETERMINISTIC PARSERS AND LOOK-AHEAD
Key question for top-down parsers: Which production do I use to expand the next non-terminal?
Key questions for bottom-up parsers:
When do I shift, when do I reduce?
Which production do I use to reduce the top of the stack?
A parser is deterministic if it does not have to guess the answers to these questions and always makes the right choice (assuming the input can be produced using the given grammar).
Most efficient deterministic parsers use look-ahead to answer these questions: In each step, inspect the next k symbols in the input text and decide what to do based on these symbols.
12/14

LL AND LR GRAMMARS
A grammar is LL(k) if it can be parsed by a recursive-descent parser and a look-ahead of k symbols suffices to decide which production to choose when expanding a non-terminal.
13/14

LL AND LR GRAMMARS
A grammar is LL(k) if it can be parsed by a recursive-descent parser and a look-ahead of k symbols suffices to decide which production to choose when expanding a non-terminal.
A grammar is LR(k) if it can be parsed by a shift-reduce parser and a look-ahead of k symbols suffices to let the parser choose between shift and reduce steps and, for reduce steps, which production to use.
13/14

LL AND LR GRAMMARS
A grammar is LL(k) if it can be parsed by a recursive-descent parser and a look-ahead of k symbols suffices to decide which production to choose when expanding a non-terminal.
A grammar is LR(k) if it can be parsed by a shift-reduce parser and a look-ahead of k symbols suffices to let the parser choose between shift and reduce steps and, for reduce steps, which production to use.
Almost every programming language can be described by an LL(1) or LR(1) grammar.
13/14

CHOOSING BETWEEN LL AND LR PARSERS
Advantages of LL parsers:
Simpler, easier to understand More space-efficient
14/14

CHOOSING BETWEEN LL AND LR PARSERS
Advantages of LL parsers:
Simpler, easier to understand More space-efficient
Advantages of LR parsers:
More general (some languages need less look-ahead than using an LL parser) Traditionally faster (modern LL parsers are competitive to LR parsers)
14/14

CHOOSING BETWEEN LL AND LR PARSERS
Advantages of LL parsers:
Simpler, easier to understand More space-efficient
Advantages of LR parsers:
More general (some languages need less look-ahead than using an LL parser) Traditionally faster (modern LL parsers are competitive to LR parsers)
Variants of LR parsers:
SLR(1) and LALR(1)
Less powerful than LR(1) parsers but LALR(1) powerful enough for most
programming languages
Easier to construct, more space-efficient than general LR parsers
14/14