GRAMMARS FOR PROGRAMMING LANGUAGES
PRINCIPLES OF PROGRAMMING LANGUAGES
Norbert Zeh Winter 2021
Dalhousie University
1/6
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/6
PARSING USING LL(1) PARSERS (1)
An LL(1) parser needs to decide which production to apply when the next symbol in the current sentential form is a non-terminal:
Input: x . . . Sentential form: X . . . Production: X ?
3/6
PARSING USING LL(1) PARSERS (1)
An LL(1) parser needs to decide which production to apply when the next symbol in the current sentential form is a non-terminal:
Input: x . . . Sentential form: X . . . Production: X ?
A terminal x is in the predictor set of the production X if S X xforsome,,(V).
3/6
PARSING USING LL(1) PARSERS (2)
A terminal x is in the predictor set of the production X if S X xforsome,,(V).
4/6
PARSING USING LL(1) PARSERS (2)
A terminal x is in the predictor set of the production X if S X xforsome,,(V).
Two cases: S
X
4/6
PARSING USING LL(1) PARSERS (2)
A terminal x is in the predictor set of the production X if S X xforsome,,(V).
Two cases:
X x.
S
X
x
4/6
PARSING USING LL(1) PARSERS (2)
A terminal x is in the predictor set of the production X if S X xforsome,,(V).
Two cases: S
X x.
X andXissucceededbyx X
in some sentential form derivable from S.
x
x
4/6
PARSING USING LL(1) PARSERS (2)
A terminal x is in the predictor set of the production X if S X xforsome,,(V).
Two cases:
X x.
X andXissucceededbyx in some sentential form derivable from S.
S
X
x
x
Xx
x
4/6
PREDICTOR SETS: AN EXAMPLE
Rule Predictor set S+SS {+} S-SS {-} S*SS {*} S/SS {/}
S neg S {neg} S int {int}
5/6
PREDICTOR SETS: AN EXAMPLE
Rule Predictor set S+SS {+} S-SS {-} S*SS {*} S/SS {/}
S neg S {neg} S int {int}
Recursive-descent parser for S-grammars:
When expanding a leading non-terminal in the current form, use the rule that starts with the next terminal in the input.
5/6
S-GRAMMARS
An S-grammar or simple grammar is a special case of an LL(1) grammar:
Every production starts with a terminal
The productions for each non-terminal start with different terminals
6/6
S-GRAMMARS
An S-grammar or simple grammar is a special case of an LL(1) grammar: Every production starts with a terminal
The productions for each non-terminal start with different terminals
An S-grammar:
A aAA Ab
6/6
S-GRAMMARS
An S-grammar or simple grammar is a special case of an LL(1) grammar: Every production starts with a terminal
The productions for each non-terminal start with different terminals
An S-grammar: Not an S-grammar:
A aAA A aAA Ab Aa
6/6
Reviews
There are no reviews yet.