MAKING A GRAMMAR LL(1)
PRINCIPLES OF PROGRAMMING LANGUAGES
Norbert Zeh Winter 2021
Dalhousie University
1/7
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/7
SOME FACTS ABOUT LL(1) LANGUAGES
There exist context-free languages that do not have LL(1) grammars.
3/7
SOME FACTS ABOUT LL(1) LANGUAGES
There exist context-free languages that do not have LL(1) grammars.
There is no known algorithm to determine whether a language is LL(1) (but there is an algorithm to decide whether a grammar is LL(1)).
3/7
SOME FACTS ABOUT LL(1) LANGUAGES
There exist context-free languages that do not have LL(1) grammars.
There is no known algorithm to determine whether a language is LL(1) (but there is an algorithm to decide whether a grammar is LL(1)).
The obvious grammar for most programming languages is usually not LL(1).
3/7
SOME FACTS ABOUT LL(1) LANGUAGES
There exist context-free languages that do not have LL(1) grammars.
There is no known algorithm to determine whether a language is LL(1) (but there is an algorithm to decide whether a grammar is LL(1)).
The obvious grammar for most programming languages is usually not LL(1).
In many situations, a non-LL(1) grammar can be transformed into an LL(1) grammar for the same language.
3/7
CONVERTING A GRAMMAR TO LL(1)
Two common reasons why a grammar is not LL(1) are left-recursion and common prefixes. Both can be eliminated by modifying the grammar.
4/7
CONVERTING A GRAMMAR TO LL(1)
Two common reasons why a grammar is not LL(1) are left-recursion and common prefixes. Both can be eliminated by modifying the grammar.
Left-recursion:
A |A
4/7
CONVERTING A GRAMMAR TO LL(1)
Two common reasons why a grammar is not LL(1) are left-recursion and common prefixes. Both can be eliminated by modifying the
grammar.
Left-recursion:
A appears as the first symbol on the right-hand side of a production for A.
A |A
4/7
CONVERTING A GRAMMAR TO LL(1)
Two common reasons why a grammar is not LL(1) are left-recursion and common prefixes. Both can be eliminated by modifying the grammar.
Left-recursion: Common prefix:
A |A A |
4/7
CONVERTING A GRAMMAR TO LL(1)
Two common reasons why a grammar is not LL(1) are left-recursion and common prefixes. Both can be eliminated by modifying the grammar.
Left-recursion:
Common prefix:
Example of a common prefix:
A |A A |
Expr Term
Expr Term + Expr
4/7
REMOVING LEFT-RECURSION
Left-recursion can be replaced with right-recursion:
A |A
A A A |A
5/7
REMOVING LEFT-RECURSION
Left-recursion can be replaced with right-recursion:
A |A
AA A |A
Using left-recursion:
A A A
A
Using right-recursion:
A A A
A
5/7
REMOVING LEFT-RECURSION
Left-recursion can be replaced with right-recursion:
Caveat:
A |A
A A A |A
Left-recursion is often used intentionally to capture the structure of the language (e.g., associativity of operators in arithmetic expressions).
The above conversion discards this information.
5/7
REMOVING COMMON PREFIXES
Common prefixes can be removed using left-factoring:
A |
A A A |
6/7
CONVERTING A GRAMMAR TO LL(1): EXAMPLE
Rule R
S E$ EEAT
ET TTMF
PREDICT(R)
{n, (} {n, (}
{n, (} {n, (}
{n, (} F(E) {(}
A+ {+} A {}
M {} M/ {/}
TF
Fn {n}
7/7
CONVERTING A GRAMMAR TO LL(1): EXAMPLE
Rule R
S E$ EEAT
ET TTMF
PREDICT(R)
{n, (} {n, (}
{n, (} {n, (}
Rule R PREDICT(R)
SE$ {n,(} ETE {n,(}
{n, (} F(E) {(}
A+ {+} A {}
M {} M/ {/}
E
E ATE
T F T T
{$,)} {+,}
{n, (} {+,,$,)}
TF
Fn {n}
T MFT
Fn {n}
{,/} F (E) {(}
A+ {+} A {}
M {} M/ {/}
7/7
Reviews
There are no reviews yet.