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β⇒ασβ⇒∗ αxγforsomeα,β,γ∈(V∪Σ)∗.
3/6
PARSING USING LL(1) PARSERS (2)
A terminal x is in the predictor set of the production X → σ if S⇒∗ αXβ⇒ασβ⇒∗ αxγforsomeα,β,γ∈(V∪Σ)∗.
4/6
PARSING USING LL(1) PARSERS (2)
A terminal x is in the predictor set of the production X → σ if S⇒∗ αXβ⇒ασβ⇒∗ αxγforsomeα,β,γ∈(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β⇒ασβ⇒∗ αxγforsomeα,β,γ∈(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β⇒ασβ⇒∗ αxγforsomeα,β,γ∈(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β⇒ασβ⇒∗ αxγforsomeα,β,γ∈(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 A→b
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 A→b A→a
6/6