COMP2022: Formal Languages and Logic – 2018, Semester 2, Week 7
COMP2022: Formal Languages and Logic
2018, Semester 2, Week 7
Kalina Yacef, Joseph Godbehere
13th September, 2018
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
WARNING
This material has been reproduced and communicated to you by or
on behalf of the University of Sydney pursuant to part VB of the
Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright
under the Act. Any further copying or communication of this
material by you may be subject of copyright protect under the Act.
Do not remove this notice.
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Outline
▶ Grammars
▶ Context-Free Grammars (CFG)
▶ Context-Free Languages (CFL)
▶ Parsing (introduction)
▶ Ambiguity
▶ Recursive Grammars
▶ Clean Grammars
▶ Types of Grammar
3/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Introduction
So far we have seen two different, but equivalent, methods of
describing languages: finite automata and regular expressions,
which describe regular languages
We have already proven that some languages, such as
{0n1n | n ≥ 0}, cannot be described using FA or RE.
Today we will introduce context-free grammars (CFG), which
describe the next category of languages, the context-free languages
4/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Grammars
Grammars are another way to describe a language
A grammar is a set of rules which can be used to generate a
language
The language generated is the set of all strings which can be
derived from the grammar
5/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Introductory example (G1)
S → 01 Base case: 01 ∈ L
S → 0S1 Recursive case: if S ∈ L then 0S1 ∈ L
G1 generates the language L = {0n1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S ⇒ 0S1 using rule S → 0S1
⇒ 00S11 using rule S → 0S1
⇒ 000111 using rule S → 01
6/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Introductory example (G1)
S → 01 Base case: 01 ∈ L
S → 0S1 Recursive case: if S ∈ L then 0S1 ∈ L
G1 generates the language L = {0n1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S
⇒ 0S1 using rule S → 0S1
⇒ 00S11 using rule S → 0S1
⇒ 000111 using rule S → 01
6/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Introductory example (G1)
S → 01 Base case: 01 ∈ L
S → 0S1 Recursive case: if S ∈ L then 0S1 ∈ L
G1 generates the language L = {0n1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S ⇒ 0S1 using rule S → 0S1
⇒ 00S11 using rule S → 0S1
⇒ 000111 using rule S → 01
6/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Introductory example (G1)
S → 01 Base case: 01 ∈ L
S → 0S1 Recursive case: if S ∈ L then 0S1 ∈ L
G1 generates the language L = {0n1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S ⇒ 0S1 using rule S → 0S1
⇒ 00S11 using rule S → 0S1
⇒ 000111 using rule S → 01
6/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Introductory example (G1)
S → 01 Base case: 01 ∈ L
S → 0S1 Recursive case: if S ∈ L then 0S1 ∈ L
G1 generates the language L = {0n1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S ⇒ 0S1 using rule S → 0S1
⇒ 00S11 using rule S → 0S1
⇒ 000111 using rule S → 01
6/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Introductory example (G2)
S → NounPhrase VerbPhrase
NounPhrase → the Noun
VerbPhrase → Verb NounPhrase
Noun → girl | ball
Verb → likes | sees
What language does G2 generate?
{ the girl likes the girl, the girl likes the ball,
the girl sees the girl, the girl sees the ball,
the ball likes the girl, the ball likes the ball,
the ball sees the girl, the ball sees the ball }
7/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Introductory example (G2)
S → NounPhrase VerbPhrase
NounPhrase → the Noun
VerbPhrase → Verb NounPhrase
Noun → girl | ball
Verb → likes | sees
What language does G2 generate?
{ the girl likes the girl, the girl likes the ball,
the girl sees the girl, the girl sees the ball,
the ball likes the girl, the ball likes the ball,
the ball sees the girl, the ball sees the ball }
7/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Definitions
Terminals
▶ The finite set of symbols which make up strings of the
language
Non-terminals / Variables
▶ A finite set of symbols used to generate the strings.
▶ They never appear in the language.
Start symbol
▶ The variable used to start every derivation
8/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Definitions
Production rules
▶ Sometimes called substitution or derivation rules
▶ Define strings of variables and terminals which can be
substituted for a variable:
Variable →
A variable can have many rules:
Noun → girl
Noun → ball
Noun → quokka
They can be written together:
Noun → girl | ball | quokka
9/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Definitions
Production rules
▶ Sometimes called substitution or derivation rules
▶ Define strings of variables and terminals which can be
substituted for a variable:
Variable →
A variable can have many rules:
Noun → girl
Noun → ball
Noun → quokka
They can be written together:
Noun → girl | ball | quokka
9/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Definitions
Production rules
▶ Sometimes called substitution or derivation rules
▶ Define strings of variables and terminals which can be
substituted for a variable:
Variable →
A variable can have many rules:
Noun → girl
Noun → ball
Noun → quokka
They can be written together:
Noun → girl | ball | quokka
9/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Another example
S → T | (S · S ) | (λT .S )
T → a | b | …
This is a grammar for lambda calculus expressions
▶ The variables are S ,T
▶ S is the start variable
▶ The terminals are a, b, …, (, ), λ, ., · (i.e. atoms and operators)
10/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Some common notational conventions
If not stated otherwise:
▶ A,B ,C , … and S are variables
▶ S is the start variable
▶ a, b, c, … are terminals
▶ …,X ,Y ,Z are either terminals or variables
▶ …w , x , y , z are strings of terminals only
▶ α, β, γ, … are strings of terminals and/or variables
11/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Context-free Grammar (CFG)
A context-free grammar is a grammar where every production rule
has the form A → α
▶ A is a variable
▶ α is a string of terminals and/or variables (possibly ϵ)
Context-free grammars describe context-free languages
Example:
{anbn | n ∈ N } is not a regular language (no finite automata
exists recognising it), but we can prove that it is a context-free
language, because the following grammar generates it:
S → aSb | ε
12/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Context-free Grammar (CFG)
A context-free grammar is a grammar where every production rule
has the form A → α
▶ A is a variable
▶ α is a string of terminals and/or variables (possibly ϵ)
Context-free grammars describe context-free languages
Example:
{anbn | n ∈ N } is not a regular language (no finite automata
exists recognising it), but we can prove that it is a context-free
language, because the following grammar generates it:
S → aSb | ε
12/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Context-free Grammar (CFG)
A context-free grammar is a grammar where every production rule
has the form A → α
▶ A is a variable
▶ α is a string of terminals and/or variables (possibly ϵ)
Context-free grammars describe context-free languages
Example:
{anbn | n ∈ N } is not a regular language (no finite automata
exists recognising it), but we can prove that it is a context-free
language, because the following grammar generates it:
S → aSb | ε
12/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
CFG: Formal Definition
A context-free grammar G is a 4-tuple (V ,T ,P ,S ) where:
▶ V is a finite set of variables
▶ T is a finite set of terminals
▶ P is a finite set of production rules in the form α → β where
α ∈ V and β ∈ {V ∪ T ∪ {ε}}⋆
▶ S ∈ V is a special variable called the Start Symbol
13/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G1
S → 01
S → 0S1
More formally, G1 = (T ,V ,S ,P) where:
T =
{0, 1}
V =
{S}
S =
S
P =
{
S → 01
S → 0S1
}
14/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G1
S → 01
S → 0S1
More formally, G1 = (T ,V ,S ,P) where:
T = {0, 1}
V =
{S}
S =
S
P =
{
S → 01
S → 0S1
}
14/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G1
S → 01
S → 0S1
More formally, G1 = (T ,V ,S ,P) where:
T = {0, 1}
V = {S}
S =
S
P =
{
S → 01
S → 0S1
}
14/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G1
S → 01
S → 0S1
More formally, G1 = (T ,V ,S ,P) where:
T = {0, 1}
V = {S}
S = S
P =
{
S → 01
S → 0S1
}
14/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G1
S → 01
S → 0S1
More formally, G1 = (T ,V ,S ,P) where:
T = {0, 1}
V = {S}
S = S
P = {
S → 01
S → 0S1
}
14/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G2
S → NounPhrase VerbPhrase
NounPhrase → the Noun
VerbPhrase → Verb NounPhrase
Noun → girl | ball
Verb → likes | sees
More formally, G2 = (T ,V ,S ,P) where:
T =
{the, girl, ball, likes, sees}
V =
{S ,NounPhrase,VerbPhrase,Noun,Verb}
S =
S
P =
(set of seven rules above)
15/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G2
S → NounPhrase VerbPhrase
NounPhrase → the Noun
VerbPhrase → Verb NounPhrase
Noun → girl | ball
Verb → likes | sees
More formally, G2 = (T ,V ,S ,P) where:
T = {the, girl, ball, likes, sees}
V =
{S ,NounPhrase,VerbPhrase,Noun,Verb}
S =
S
P =
(set of seven rules above)
15/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G2
S → NounPhrase VerbPhrase
NounPhrase → the Noun
VerbPhrase → Verb NounPhrase
Noun → girl | ball
Verb → likes | sees
More formally, G2 = (T ,V ,S ,P) where:
T = {the, girl, ball, likes, sees}
V = {S ,NounPhrase,VerbPhrase,Noun,Verb}
S =
S
P =
(set of seven rules above)
15/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G2
S → NounPhrase VerbPhrase
NounPhrase → the Noun
VerbPhrase → Verb NounPhrase
Noun → girl | ball
Verb → likes | sees
More formally, G2 = (T ,V ,S ,P) where:
T = {the, girl, ball, likes, sees}
V = {S ,NounPhrase,VerbPhrase,Noun,Verb}
S = S
P =
(set of seven rules above)
15/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G2
S → NounPhrase VerbPhrase
NounPhrase → the Noun
VerbPhrase → Verb NounPhrase
Noun → girl | ball
Verb → likes | sees
More formally, G2 = (T ,V ,S ,P) where:
T = {the, girl, ball, likes, sees}
V = {S ,NounPhrase,VerbPhrase,Noun,Verb}
S = S
P = (set of seven rules above)
15/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Language of a Grammar
Let w be a string over T .
w ∈ L(G) if and only if it is possible to derive w from S
Notation:
α ⇒ β denotes that α derives β in one step
α ⇒+ β means it derives it in one or more steps
The language of a grammar G = (V ,T ,P ,S ) is the set
L(G) = {s | s ∈ T ⋆ and S ⇒+ s}
If two grammars generate the same langauge, then they are
equivalent.
16/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Language of a Grammar
Let w be a string over T .
w ∈ L(G) if and only if it is possible to derive w from S
Notation:
α ⇒ β denotes that α derives β in one step
α ⇒+ β means it derives it in one or more steps
The language of a grammar G = (V ,T ,P ,S ) is the set
L(G) = {s | s ∈ T ⋆ and S ⇒+ s}
If two grammars generate the same langauge, then they are
equivalent.
16/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Language of a Grammar
Let w be a string over T .
w ∈ L(G) if and only if it is possible to derive w from S
Notation:
α ⇒ β denotes that α derives β in one step
α ⇒+ β means it derives it in one or more steps
The language of a grammar G = (V ,T ,P ,S ) is the set
L(G) = {s | s ∈ T ⋆ and S ⇒+ s}
If two grammars generate the same langauge, then they are
equivalent.
16/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Language of a Grammar
Let w be a string over T .
w ∈ L(G) if and only if it is possible to derive w from S
Notation:
α ⇒ β denotes that α derives β in one step
α ⇒+ β means it derives it in one or more steps
The language of a grammar G = (V ,T ,P ,S ) is the set
L(G) = {s | s ∈ T ⋆ and S ⇒+ s}
If two grammars generate the same langauge, then they are
equivalent.
16/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Derivation of a string
▶ Begin with the start symbol
▶ Repeatedly replace one variable with the right hand side of
one of its productions
▶ … until the string is composed only of terminal symbols
Example, derivation of 000111 from this grammar:
S → 0S1 | ε S ⇒
0S1
⇒ 00S11
⇒ 000S111
⇒ 000111
17/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Derivation of a string
▶ Begin with the start symbol
▶ Repeatedly replace one variable with the right hand side of
one of its productions
▶ … until the string is composed only of terminal symbols
Example, derivation of 000111 from this grammar:
S → 0S1 | ε S ⇒
0S1
⇒ 00S11
⇒ 000S111
⇒ 000111
17/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Derivation of a string
▶ Begin with the start symbol
▶ Repeatedly replace one variable with the right hand side of
one of its productions
▶ … until the string is composed only of terminal symbols
Example, derivation of 000111 from this grammar:
S → 0S1 | ε S ⇒ 0S1
⇒
00S11
⇒ 000S111
⇒ 000111
17/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Derivation of a string
▶ Begin with the start symbol
▶ Repeatedly replace one variable with the right hand side of
one of its productions
▶ … until the string is composed only of terminal symbols
Example, derivation of 000111 from this grammar:
S → 0S1 | ε S ⇒ 0S1
⇒ 00S11
⇒ 000S111
⇒
000111
17/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Derivation of a string
▶ Begin with the start symbol
▶ Repeatedly replace one variable with the right hand side of
one of its productions
▶ … until the string is composed only of terminal symbols
Example, derivation of 000111 from this grammar:
S → 0S1 | ε S ⇒ 0S1
⇒ 00S11
⇒ 000S111
⇒ 000111
17/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Leftmost and Rightmost Derivations
Leftmost derivation: always derive the leftmost variable first
Rightmost derivation: always derive the rightmost variable first
Example: “the girl sees the ball”
S ⇒ NounPhrase VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl Verb NounPhrase
⇒ the girl sees NounPhrase
⇒ the girl sees the Noun
⇒ the girl sees the ball
S ⇒ NounPhrase VerbPhrase
⇒ NounPhrase Verb NounPhrase
⇒ NounPhrase Verb the Noun
⇒ NounPhrase Verb the ball
⇒ NounPhrase sees the ball
⇒ the Noun sees the ball
⇒ the girl sees the ball
18/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Context-Free Languages
A language is context-free if it is generated by a CFG
The syntax of most programming languages are context-free.
S → while E do S
S → if E then S else S
S → I := E
S → {SL}
L → ;SL | ε
E → … (description of an expression)
I → … (description of an identifier)
19/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Context-Free Languages
A language is context-free if it is generated by a CFG
The syntax of most programming languages are context-free.
S → while E do S
S → if E then S else S
S → I := E
S → {SL}
L → ;SL | ε
E → … (description of an expression)
I → … (description of an identifier)
19/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Context-Free Languages
A language is context-free if it is generated by a CFG
{Regular Languages} ⊂ {Context-Free Languages}
▶ The union of two CFL is also context-free
▶ The concatenation of two CFL is also context-free
▶ The star closure of a CFL is also context-free
20/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example
Consider the grammar G :
S → AB
A → ε | aA
B → ε | bB
What is L(G)?
S ⇒ AB
⇒ aAB
⇒+ aaaaAB
⇒ aaaaB
⇒ aaaabB
⇒+ aaaabbbbbbB
⇒ aaaabbbbbb
i.e. L(G) = L(a⋆b⋆) = {anbm | n ≥ 0,m ≥ 0}
21/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example
Consider the grammar G :
S → AB
A → ε | aA
B → ε | bB
What is L(G)?
S ⇒ AB
⇒ aAB
⇒+ aaaaAB
⇒ aaaaB
⇒ aaaabB
⇒+ aaaabbbbbbB
⇒ aaaabbbbbb
i.e. L(G) = L(a⋆b⋆) = {anbm | n ≥ 0,m ≥ 0}
21/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example
Consider the grammar G :
S → AB
A → ε | aA
B → ε | bB
What is L(G)?
S ⇒ AB
⇒ aAB
⇒+ aaaaAB
⇒ aaaaB
⇒ aaaabB
⇒+ aaaabbbbbbB
⇒ aaaabbbbbb
i.e. L(G) = L(a⋆b⋆) = {anbm | n ≥ 0,m ≥ 0}
21/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example
Consider the grammar G :
S → AB
A → ε | aA
B → ε | bB
What is L(G)?
S ⇒ AB
⇒ aAB
⇒+ aaaaAB
⇒ aaaaB
⇒ aaaabB
⇒+ aaaabbbbbbB
⇒ aaaabbbbbb
i.e. L(G) = L(a⋆b⋆) = {anbm | n ≥ 0,m ≥ 0}
21/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
More examples
Describe the language generated
1. S → aSa | bSb | ε
2. S → aS | bS | a
3. S → SS | bS | a
4. S → aT | bT | ε
T → aS | bS
5. S → aSa | bSb | a | b
22/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
More examples
Give grammars generating these languages
1. {ban+1b | n ≥ 0}
2. Odd-length strings in {a, b}⋆ with middle symbol a
3. Even-length strings in {a, b}⋆ with matching middle symbols
4. Binary strings containing more 0’s than 1’s
5. Strings over {a, b} with at least three a’s
23/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Constructing grammars
Let M and N be two languages whose grammars have disjoint sets
of non-terminals (rename them if necessary). Let SM and SN be
their start symbols.
Then we can construct a grammar recognising the following
languages, with a new start symbol S :
▶ Union: the grammar for M ∪N starts with S → SM | SN
▶ Concatenation: the grammar for MN starts with S → SMSN
▶ Star closure: the grammar for M ⋆ starts with S → SMS | ε
All other productions remain unchanged (aside for renaming of
variables as needed)
24/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Constructing grammars
Let M and N be two languages whose grammars have disjoint sets
of non-terminals (rename them if necessary). Let SM and SN be
their start symbols.
Then we can construct a grammar recognising the following
languages, with a new start symbol S :
▶ Union: the grammar for M ∪N starts with S → SM | SN
▶ Concatenation: the grammar for MN starts with S → SMSN
▶ Star closure: the grammar for M ⋆ starts with S → SMS | ε
All other productions remain unchanged (aside for renaming of
variables as needed)
24/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Constructing grammars
Let M and N be two languages whose grammars have disjoint sets
of non-terminals (rename them if necessary). Let SM and SN be
their start symbols.
Then we can construct a grammar recognising the following
languages, with a new start symbol S :
▶ Union: the grammar for M ∪N starts with S → SM | SN
▶ Concatenation: the grammar for MN starts with S → SMSN
▶ Star closure: the grammar for M ⋆ starts with S → SMS | ε
All other productions remain unchanged (aside for renaming of
variables as needed)
24/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Constructing grammars
Let M and N be two languages whose grammars have disjoint sets
of non-terminals (rename them if necessary). Let SM and SN be
their start symbols.
Then we can construct a grammar recognising the following
languages, with a new start symbol S :
▶ Union: the grammar for M ∪N starts with S → SM | SN
▶ Concatenation: the grammar for MN starts with S → SMSN
▶ Star closure: the grammar for M ⋆ starts with S → SMS | ε
All other productions remain unchanged (aside for renaming of
variables as needed)
24/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Constructing grammars
Let M and N be two languages whose grammars have disjoint sets
of non-terminals (rename them if necessary). Let SM and SN be
their start symbols.
Then we can construct a grammar recognising the following
languages, with a new start symbol S :
▶ Union: the grammar for M ∪N starts with S → SM | SN
▶ Concatenation: the grammar for MN starts with S → SMSN
▶ Star closure: the grammar for M ⋆ starts with S → SMS | ε
All other productions remain unchanged (aside for renaming of
variables as needed)
24/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Using the union rule
Let L = {ε, a, b, aa, bb, …, an , bn , …}
Then L = M ∪N where M = {an | n ≥ 0},N = {bn | n ≥ 0}
So a grammar GM of M is
SM → ε | aSM
and a grammar GN of N is
SN → ε | bSN
Using the union rule we get:
S → SM | SN
SM → ε | aSM
SN → ε | bSN
25/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Using the union rule
Let L = {ε, a, b, aa, bb, …, an , bn , …}
Then L = M ∪N where M = {an | n ≥ 0},N = {bn | n ≥ 0}
So a grammar GM of M is SM → ε | aSM
and a grammar GN of N is
SN → ε | bSN
Using the union rule we get:
S → SM | SN
SM → ε | aSM
SN → ε | bSN
25/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Using the union rule
Let L = {ε, a, b, aa, bb, …, an , bn , …}
Then L = M ∪N where M = {an | n ≥ 0},N = {bn | n ≥ 0}
So a grammar GM of M is SM → ε | aSM
and a grammar GN of N is SN → ε | bSN
Using the union rule we get:
S → SM | SN
SM → ε | aSM
SN → ε | bSN
25/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Using the union rule
Let L = {ε, a, b, aa, bb, …, an , bn , …}
Then L = M ∪N where M = {an | n ≥ 0},N = {bn | n ≥ 0}
So a grammar GM of M is SM → ε | aSM
and a grammar GN of N is SN → ε | bSN
Using the union rule we get:
S → SM | SN
SM → ε | aSM
SN → ε | bSN
25/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Using the concatenation rule
Let L = {ambn | m ≥ 0,n ≥ 0}
Then L = MN where M = {am | m ≥ 0},N = {bn | n ≥ 0}
So a grammar GM of M is SM → ε | aSM
and a grammar GN of N is SN → ε | bSN
Using the concatenation rule we get:
S → SMSN
SM → ε | aSM
SN → ε | bSN
26/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Using the concatenation rule
Let L = {ambn | m ≥ 0,n ≥ 0}
Then L = MN where M = {am | m ≥ 0},N = {bn | n ≥ 0}
So a grammar GM of M is SM → ε | aSM
and a grammar GN of N is SN → ε | bSN
Using the concatenation rule we get:
S → SMSN
SM → ε | aSM
SN → ε | bSN
26/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Using the star closure rule
Let L be strings consisting of 0 or more occurrences of aa or bb,
i.e. (aa | bb)⋆
Then L = M ⋆ where M = {aa, bb}
So a grammar GM of M is
SM → aa | bb
Using the star closure rule we get:
S → SMS | ε
SM → aa | bb
27/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Using the star closure rule
Let L be strings consisting of 0 or more occurrences of aa or bb,
i.e. (aa | bb)⋆
Then L = M ⋆ where M = {aa, bb}
So a grammar GM of M is SM → aa | bb
Using the star closure rule we get:
S → SMS | ε
SM → aa | bb
27/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Using the star closure rule
Let L be strings consisting of 0 or more occurrences of aa or bb,
i.e. (aa | bb)⋆
Then L = M ⋆ where M = {aa, bb}
So a grammar GM of M is SM → aa | bb
Using the star closure rule we get:
S → SMS | ε
SM → aa | bb
27/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Parsing
Given a sentence, the problem of parsing is determining how the
grammar generates it.
i.e. To discover the correct derivation of the sentence, or the
correct parse tree
28/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Parse Tree
A parse tree is a tree labelled by symbols from the CFG
▶ root = the start symbol
▶ interior node = a variable
▶ leaf node = a terminal or ε
▶ children of X = the right hand side of a production rule for
X , in order
Example parse tree for “0011” in
S → 0S1 | 01
An in-order traversal of the leaf
nodes retrieves the string
S
S0 1
0 1
29/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Parse Tree
A parse tree is a tree labelled by symbols from the CFG
▶ root = the start symbol
▶ interior node = a variable
▶ leaf node = a terminal or ε
▶ children of X = the right hand side of a production rule for
X , in order
Example parse tree for “0011” in
S → 0S1 | 01
An in-order traversal of the leaf
nodes retrieves the string
S
S0 1
0 1
29/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Parse Tree or Derivation Tree
The parse tree defines the (syntactic) meaning of a string in the
grammar’s language
S
S
·
S
x
S
·
S
y z
S → S · S
S → x | y | z
This parse tree implies
that the expression
means x · (y · z )
30/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Parse Tree or Derivation Tree
The parse tree defines the (syntactic) meaning of a string in the
grammar’s language
S
S
·
S
x
S
·
S
y z
S → S · S
S → x | y | z
This parse tree implies
that the expression
means x · (y · z )
30/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Natural Language Processing (NLP) example
S → NounPhrase VerbPhrase
NounPhrase → ComplexNoun | ComplexNoun PrepPhrase
VerbPhrase → ComplexVerb | ComplexVerb PrepPhrase
PrepPhrase → Prep ComplexNoun
ComplexNoun → Article Noun
ComplexVerb → Verb | Verb NounPhrase
Article → a | the
Noun → girl | dog | stick | ball
Verb → chases | sees
Prep → with
31/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Simple example
Is the string “a ball” accepted by this grammar?
We have no choice but start by deriving
S ⇒ NounPhrase VerbPhrase
All the production rules for VerbPhrase produce a ComplexVerb,
which in turn must produce a Verb.
Therefore all strings in the language contain a verb. “a ball” does
not contain a verb, so it cannot be accepted by the grammar.
32/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Simple example
Is the string “a ball” accepted by this grammar?
We have no choice but start by deriving
S ⇒ NounPhrase VerbPhrase
All the production rules for VerbPhrase produce a ComplexVerb,
which in turn must produce a Verb.
Therefore all strings in the language contain a verb. “a ball” does
not contain a verb, so it cannot be accepted by the grammar.
32/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Simple example
Is the string “a ball” accepted by this grammar?
We have no choice but start by deriving
S ⇒ NounPhrase VerbPhrase
All the production rules for VerbPhrase produce a ComplexVerb,
which in turn must produce a Verb.
Therefore all strings in the language contain a verb. “a ball” does
not contain a verb, so it cannot be accepted by the grammar.
32/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Simple example
Is the string “a ball” accepted by this grammar?
We have no choice but start by deriving
S ⇒ NounPhrase VerbPhrase
All the production rules for VerbPhrase produce a ComplexVerb,
which in turn must produce a Verb.
Therefore all strings in the language contain a verb. “a ball” does
not contain a verb, so it cannot be accepted by the grammar.
32/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Ambiguity: example
Ambiguity: several meanings for the same sentence.
“The girl chases the dog with a stick” has two leftmost derivations
Sentence ⇒ NounPhrase VerbPhrase
⇒ ComplexNoun VerbPhrase
⇒ Article Noun VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl ComplexVerb
⇒ the girl Verb NounPhrase
⇒ the girl chases NounPhrase
⇒ the girl chases ComplexNoun PrepPhrase
⇒ the girl chases Article Noun PrepPhrase
⇒ the girl chases the Noun PrepPhrase
⇒ the girl chases the dog PrepPhrase
⇒ the girl chases the dog Prep ComplexNoun
⇒ the girl chases the dog with ComplexNoun
⇒ the girl chases the dog with Article Noun
⇒ the girl chases the dog with a Noun
⇒ the girl chases the dog with a stick
Sentence ⇒ NounPhrase VerbPhrase
⇒ ComplexNoun VerbPhrase
⇒ Article Noun VerbPhrase
⇒ the Noun VerbPhrase
⇒ the girl VerbPhrase
⇒ the girl ComplexVerb PrepPhrase
⇒ the girl Verb NounPhrase PrepPhrase
⇒ the girl chases NounPhrase PrepPhrase
⇒ the girl chases Article Noun PrepPhrase
⇒ the girl chases the Noun PrepPhrase
⇒ the girl chases the dog PrepPhrase
⇒ the girl chases the dog Prep ComplexNoun
⇒ the girl chases the dog with ComplexNoun
⇒ the girl chases the dog with Article Noun
⇒ the girl chases the dog with a Noun
⇒ the girl chases the dog with a stick
33/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Ambiguity: example
Ambiguity: several meanings for the same sentence.
“The girl chases the dog with a stick” has two leftmost derivations
Sentence ⇒+ the girl VerbPhrase
⇒ the girl ComplexVerb
⇒+ the girl chases the dog with a stick
Sentence ⇒+ the girl VerbPhrase
⇒ the girl ComplexVerb PrepPhrase
⇒+ the girl chases the dog with a stick
Who has the stick?
34/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
First Leftmost Derivation Tree
Sentence
NounPhrase VerbPhrase
CmplxNoun
Article Noun
the girl
CmplxVerb
Verb
chases
NounPhrase
CmplxNoun PrepPhrase
Article Noun Prep CmplxNoun
Article Noun
the dog with the stick
35/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Second Leftmost Derivation Tree
Sentence
NounPhrase VerbPhrase
CmplxNoun CmplxVerb PrepPhrase
Article Noun Verb NounPhrase Prep CmplxNoun
CmplxNoun Article Noun
Article Noun
the girl chases the dog with a stick
36/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Ambiguous Grammars
Definition:
A string is ambiguous on a given grammar if it has two different
parse trees. Otherwise, it is unambigous.
Definition:
A grammar is ambiguous if it contains an ambiguous string.
Each parse tree has only one leftmost derivation, so this is
equivalent to saying that the string has two distinct leftmost
derivations.
Similarly for rightmost derivations.
37/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Ambiguous Grammars
Definition:
A string is ambiguous on a given grammar if it has two different
parse trees. Otherwise, it is unambigous.
Definition:
A grammar is ambiguous if it contains an ambiguous string.
Each parse tree has only one leftmost derivation, so this is
equivalent to saying that the string has two distinct leftmost
derivations.
Similarly for rightmost derivations.
37/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Ambiguous Grammars
Definition:
A string is ambiguous on a given grammar if it has two different
parse trees. Otherwise, it is unambigous.
Definition:
A grammar is ambiguous if it contains an ambiguous string.
Each parse tree has only one leftmost derivation, so this is
equivalent to saying that the string has two distinct leftmost
derivations.
Similarly for rightmost derivations.
37/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Is this grammar ambiguous?
E → E − E
E → a | b | c
Rightmost derivations of a − b − c:
E ⇒ E − E
⇒ E − c
⇒ E − E − c
⇒ E − b − c
⇒ a − b − c
i.e. (a − b)− c
E ⇒ E − E
⇒ E − E − E
⇒ E − E − c
⇒ E − b − c
⇒ a − b − c
i.e. a − (b − c)
38/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Is this grammar ambiguous?
E → E − E
E → a | b | c
Rightmost derivations of a − b − c:
E ⇒ E − E
⇒ E − c
⇒ E − E − c
⇒ E − b − c
⇒ a − b − c
i.e. (a − b)− c
E ⇒ E − E
⇒ E − E − E
⇒ E − E − c
⇒ E − b − c
⇒ a − b − c
i.e. a − (b − c)
38/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Is this grammar ambiguous?
E → E − E
E → a | b | c
Rightmost derivations of a − b − c:
E ⇒ E − E
⇒ E − c
⇒ E − E − c
⇒ E − b − c
⇒ a − b − c
i.e. (a − b)− c
E ⇒ E − E
⇒ E − E − E
⇒ E − E − c
⇒ E − b − c
⇒ a − b − c
i.e. a − (b − c)
38/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Is this grammar ambiguous?
E → E − E
E → a | b | c
Rightmost derivations of a − b − c:
E
E − E
E − E
a b
c
i.e. (a − b)− c
E
E−E
E − E
b c
a
i.e. a − (b − c)
39/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Removing ambiguity (example)
Suppose we want a − b − c to always mean (a − b)− c?
Introduce a new nonterminal symbol T :
E → E − T | T
T → a | b | c
Now the only rightmost derivation is:
E ⇒ E − T
⇒ E − c
⇒ E − T − c
⇒ E − b − c
⇒ T − b − c
⇒ a − b − c
E
E − T
E − T
T b
c
a
40/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Removing ambiguity (example)
Suppose we want a − b − c to always mean (a − b)− c?
Introduce a new nonterminal symbol T :
E → E − T | T
T → a | b | c
Now the only rightmost derivation is:
E ⇒ E − T
⇒ E − c
⇒ E − T − c
⇒ E − b − c
⇒ T − b − c
⇒ a − b − c
E
E − T
E − T
T b
c
a
40/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Removing ambiguity (example)
Suppose we want a − b − c to always mean (a − b)− c?
Introduce a new nonterminal symbol T :
E → E − T | T
T → a | b | c
Now the only rightmost derivation is:
E ⇒ E − T
⇒ E − c
⇒ E − T − c
⇒ E − b − c
⇒ T − b − c
⇒ a − b − c
E
E − T
E − T
T b
c
a
40/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Removing ambiguity (example)
Suppose we want a − b − c to always mean (a − b)− c?
Introduce a new nonterminal symbol T :
E → E − T | T
T → a | b | c
Now the only rightmost derivation is:
E ⇒ E − T
⇒ E − c
⇒ E − T − c
⇒ E − b − c
⇒ T − b − c
⇒ a − b − c
E
E − T
E − T
T b
c
a
40/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Removing ambiguity (example)
Suppose we want a − b − c to always mean (a − b)− c?
Introduce a new nonterminal symbol T :
E → E − T | T
T → a | b | c
Now the only rightmost derivation is:
E ⇒ E − T
⇒ E − c
⇒ E − T − c
⇒ E − b − c
⇒ T − b − c
⇒ a − b − c
E
E − T
E − T
T b
c
a
40/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Removing ambiguity (example)
Suppose we want a − b − c to always mean (a − b)− c?
Introduce a new nonterminal symbol T :
E → E − T | T
T → a | b | c
Now the only rightmost derivation is:
E ⇒ E − T
⇒ E − c
⇒ E − T − c
⇒ E − b − c
⇒ T − b − c
⇒ a − b − c
E
E − T
E − T
T b
c
a
40/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Removing ambiguity (example)
Suppose we want a − b − c to always mean (a − b)− c?
Introduce a new nonterminal symbol T :
E → E − T | T
T → a | b | c
Now the only rightmost derivation is:
E ⇒ E − T
⇒ E − c
⇒ E − T − c
⇒ E − b − c
⇒ T − b − c
⇒ a − b − c
E
E − T
E − T
T b
c
a
40/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Removing ambiguity (example)
Suppose we want a − b − c to always mean (a − b)− c?
Introduce a new nonterminal symbol T :
E → E − T | T
T → a | b | c
Now the only rightmost derivation is:
E ⇒ E − T
⇒ E − c
⇒ E − T − c
⇒ E − b − c
⇒ T − b − c
⇒ a − b − c
E
E − T
E − T
T b
c
a
40/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Removing ambiguity (example)
Suppose we want a − b − c to always mean (a − b)− c?
Introduce a new nonterminal symbol T :
E → E − T | T
T → a | b | c
Now the only rightmost derivation is:
E ⇒ E − T
⇒ E − c
⇒ E − T − c
⇒ E − b − c
⇒ T − b − c
⇒ a − b − c
E
E − T
E − T
T b
c
a
40/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Recursion
If a variable X can generate a string containing X itself, then it is
recursive
▶ left-recursive: it occurs at the start of the string X ⇒+ Xβ
▶ right-recursive: it occurs at the end of the string X ⇒+ αX
▶ self-embedding: it occurs in between: X ⇒+ αXβ
A grammar is recursive if any of its variables is recursive
A grammar for an infinite language must contain at least one
recursive variable
41/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Recursion
If a variable X can generate a string containing X itself, then it is
recursive
▶ left-recursive: it occurs at the start of the string X ⇒+ Xβ
▶ right-recursive: it occurs at the end of the string X ⇒+ αX
▶ self-embedding: it occurs in between: X ⇒+ αXβ
A grammar is recursive if any of its variables is recursive
A grammar for an infinite language must contain at least one
recursive variable
41/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Recursion
If a variable X can generate a string containing X itself, then it is
recursive
▶ left-recursive: it occurs at the start of the string X ⇒+ Xβ
▶ right-recursive: it occurs at the end of the string X ⇒+ αX
▶ self-embedding: it occurs in between: X ⇒+ αXβ
A grammar is recursive if any of its variables is recursive
A grammar for an infinite language must contain at least one
recursive variable
41/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Recursion
If a variable X can generate a string containing X itself, then it is
recursive
▶ left-recursive: it occurs at the start of the string X ⇒+ Xβ
▶ right-recursive: it occurs at the end of the string X ⇒+ αX
▶ self-embedding: it occurs in between: X ⇒+ αXβ
A grammar is recursive if any of its variables is recursive
A grammar for an infinite language must contain at least one
recursive variable
41/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Recursion
If a variable X can generate a string containing X itself, then it is
recursive
▶ left-recursive: it occurs at the start of the string X ⇒+ Xβ
▶ right-recursive: it occurs at the end of the string X ⇒+ αX
▶ self-embedding: it occurs in between: X ⇒+ αXβ
A grammar is recursive if any of its variables is recursive
A grammar for an infinite language must contain at least one
recursive variable
41/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Recursion
If a variable X can generate a string containing X itself, then it is
recursive
▶ left-recursive: it occurs at the start of the string X ⇒+ Xβ
▶ right-recursive: it occurs at the end of the string X ⇒+ αX
▶ self-embedding: it occurs in between: X ⇒+ αXβ
A grammar is recursive if any of its variables is recursive
A grammar for an infinite language must contain at least one
recursive variable
41/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Balanced Parentheses
This grammar generates the language of balanced parentheses:
B → (B) | BB | ε
Show that it is ambiguous.
42/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Remove left recursion
Original grammar is left-recursive: B → (B) | BB | ε
An equivalent grammar without left-recursion: B → (B)B | ε
Left parsing of ()()() is now deterministic:
Remaining input Derivation steps
()()() B start symbol
()()() (B)B B → (B)B
)()() B)B matching terminals
)()() )B B → ε
()() B matching terminals
… … …
43/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Clean grammars
▶ No circular definitions: A1 ⇒ A2 ⇒ … ⇒ An ⇒ A1
All the A’s can generate the same set of strings, therefore
there is no reason to distinguish between them. They should
be reduced to a single variable.
▶ No useless variables:
A variable is useless if it cannot appear in the derivation of any
string. i.e. there is no derivation S ⇒+ αXβ ⇒+ σ where σ
is a string of terminals. Useless variables can be removed
without affecting the language generated by the grammar.
▶ No null productions (except for the start symbol)
44/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Clean grammars
▶ No circular definitions: A1 ⇒ A2 ⇒ … ⇒ An ⇒ A1
All the A’s can generate the same set of strings, therefore
there is no reason to distinguish between them. They should
be reduced to a single variable.
▶ No useless variables:
A variable is useless if it cannot appear in the derivation of any
string. i.e. there is no derivation S ⇒+ αXβ ⇒+ σ where σ
is a string of terminals. Useless variables can be removed
without affecting the language generated by the grammar.
▶ No null productions (except for the start symbol)
44/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Clean grammars
▶ No circular definitions: A1 ⇒ A2 ⇒ … ⇒ An ⇒ A1
All the A’s can generate the same set of strings, therefore
there is no reason to distinguish between them. They should
be reduced to a single variable.
▶ No useless variables:
A variable is useless if it cannot appear in the derivation of any
string. i.e. there is no derivation S ⇒+ αXβ ⇒+ σ where σ
is a string of terminals. Useless variables can be removed
without affecting the language generated by the grammar.
▶ No null productions (except for the start symbol)
44/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Types of grammars
We are interested in 4 classes of grammars, depending on the type
of production rules that they allow:
Type 0 (unrestricted) χ → α
Type 1 (context-sensitive) χ → α where 1 ≤ |χ| ≤ |α|
Type 2 (context-free) A → α
Type 3 (regular) A → ωB and A → ω
χ arbitrary string of one or more symbols
α arbitrary string of symbols, possibly null
A,B non-terminal symbols
ω arbitrary string of terminal symbols
Recall the Chomsky Hierarchy from week 1!
45/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Context-free Grammars
▶ Generate Context-Free Languages
▶ Very important class of languages in CS (compilers, NLP, etc.)
▶ All rules are in the form A → α
▶ Closed under Union, Concatenation and Star Closure
▶ String derivation (left-most, right-most)
▶ Ambiguous grammars
▶ Clean grammars
Next lecture:
▶ Push-Down Automata
▶ Parsing
46/46
Outline
outline
Grammars
introduction
definition
example
definitions
CFG
definition
definition
Derivation
definitions
CFL
definition
examples
construction
Parsing
definition
Ambiguity
NLP example
definition
example
removing ambiguity (example)
Recursion
recursion
example of removing ambiguity
Grammars
clean grammars
types of grammars
Review
Review