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 {0n 1n | 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 = {0n 1n | n > 0}, which we already
know is not regular
How does it derive 000111?
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 = {0n 1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S
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 = {0n 1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S ⇒ 0S1 using rule S → 0S1
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 = {0n 1n | 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
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 = {0n 1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S ⇒ 0S1
⇒ 00S11 ⇒ 000111
using rule S → 0S1 using rule S → 0S1 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?
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 sees the girl, the ball likes the girl, the ball sees the girl,
the girl likes the ball, the girl sees the ball, the ball likes the ball,
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 →
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
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: They can be written together:
Noun → girl Noun → girl | ball | quokka Noun → ball
Noun → 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 ε)
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
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:
{an bn | 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
More formally, G1 = (T,V,S,P) where: T=
V= S= P=
S → 01 S → 0S1
14/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G1
More formally, G1 = (T,V,S,P) where: T = {0, 1}
V= S= P=
S → 01 S → 0S1
14/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G1
More formally, G1 = (T,V,S,P) where: T = {0, 1}
V ={S} S=
P=
S → 01 S → 0S1
14/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Example G1
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
More formally, G1 = (T,V,S,P) where: T = {0, 1}
V ={S} S=S
P={
S → 01 S → 0S1 }
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=
V= S= P=
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= P=
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=
P=
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=
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
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
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}
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
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 ⇒
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 ⇒
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 ⇒
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
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:
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
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 → SM SN
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 → SM SN ▶ Star closure: the grammar for M ⋆ starts with S → SM S | ε
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 and a grammar GN of N is
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}
SoagrammarGM ofM isSM →ε|aSM and a grammar GN of N is
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}
SoagrammarGM ofM isSM →ε|aSM andagrammarGN ofN isSN →ε|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}
SoagrammarGM ofM isSM →ε|aSM andagrammarGN ofN isSN →ε|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
LetL={ambn |m≥0,n≥0}
ThenL=MN whereM ={am |m≥0},N ={bn |n≥0}
SoagrammarGM ofM isSM →ε|aSM andagrammarGN ofN isSN →ε|bSN
26/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Using the concatenation rule
LetL={ambn |m≥0,n≥0}
ThenL=MN whereM ={am |m≥0},N ={bn |n≥0}
SoagrammarGM ofM isSM →ε|aSM andagrammarGN ofN isSN →ε|bSN
Using the concatenation rule we get:
S → SM SN 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
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} SoagrammarGM ofM isSM →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} SoagrammarGM ofM isSM →aa|bb
Using the star closure rule we get:
S → SM S | ε 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
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
S
0S1
01
Example parse tree for “0011” in
S → 0S1 | 01
An in-order traversal of the leaf nodes retrieves the string
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
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
SS
SS
x·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?
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
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.
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 ComplexVerb
the girl VerbPhrase
⇒+ the girl chases the dog with a stick
Sentence ⇒+
⇒ the girl ComplexVerb PrepPhrase
⇒+ the girl chases the dog with a stick Who has the stick?
the girl VerbPhrase
34/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
First Leftmost Derivation Tree
Sentence NounPhrase VerbPhrase
CmplxNoun Article Noun
Verb
CmplxVerb
NounPhrase
CmplxNoun PrepPhrase Article Noun Prep CmplxNoun
Article Noun
the dog with the stick
the girl
chases
35/46
Outline Grammars CFG Derivation CFL Parsing Ambiguity Recursion Grammars Review
Second Leftmost Derivation Tree
Sentence NounPhrase VerbPhrase
CmplxNoun Article Noun
CmplxVerb PrepPhrase
Verb NounPhrase Prep CmplxNoun
Article Noun
chases the dog with
CmplxNoun Article Noun
the girl
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.
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.
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:
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
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−E ⇒E−c ⇒E−E−E ⇒E−E−c ⇒E−E−c ⇒E−b−c ⇒E−b−c ⇒a−b−c ⇒a−b−c
i.e. (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: EE
E−EE−E
E−EcaE−E
ab bc
i.e. (a −b)−c 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?
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
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
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
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
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
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
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
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⇒E−T ⇒E−cE−T
⇒E−T−c ⇒E−b−c ⇒T−b−c ⇒a−b−c
E−T Tb
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
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 β
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
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 β
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
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
(B )B B)B )B
B
…
start symbol
B → (B)B matching terminals 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.
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.
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) Type 2 (context-free) Type3(regular)
χ → α
χ → α where 1 ≤ |χ| ≤ |α| A → α
A→ωB andA→ω
χ
α A, B ω
arbitrary string of one or more symbols arbitrary string of symbols, possibly null 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.)
▶ AllrulesareintheformA→α
▶ 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