Hoofdstuk 5: Context-vrije talen
1 Context-vrije grammatica’s
Grammatica = constructieve manier om een taal te beschrijven
Definitie:
Een grammatica 𝐺 = (𝑉, 𝑇, 𝑆, 𝑃) is context-vrij als alle productieregels van volgende vorm zijn
𝐴→𝑥
Met 𝐴 ∈ 𝑉 en 𝑥 ∈ (𝑉 ∪ 𝑇)∗
Opmerking: Elke reguliere grammatica is ook een context-vrije grammatica.
Definitie context-vrije taal:
Een taal L is context-vrij indien een context-vrije grammatica G bestaat waarvoor geldt dat L(G) = L.
Opmerking: dezelfde taal zal vaak ook kunnen voorgesteld worden door een grammatica die niet
context-vrij is. Dit betekent echter niet dat de taal niet context-vrij is!!
1.1 Bewijzen context-vrij
Bewijs dat 𝐿 = {𝑎𝑛 𝑏𝑚 : 𝑛 ≠ 𝑚} een context-vrije taal is.
• Stel 𝐿= = {𝑎𝑛 𝑏𝑚 : 𝑛 = 𝑚}. Van deze taal hebben we bewezen dat ze niet regulier is door
middel van de pompstelling.
• Stel 𝐿𝑟𝑎𝑛𝑑 = 𝑎∗ 𝑏 ∗ . Deze taal is regulier aangezien we ze voorstellen door middel van een
reguliere expressie.
Nu is 𝐿= = 𝐿𝑟𝑎𝑛𝑑 − 𝐿. We weten dat het verschil van 2 reguliere talen weer een reguliere taal is.
Maar we weten dat 𝐿= zeker niet regulier is en 𝐿𝑟𝑎𝑛𝑑 zeker wel dus kunnen we afleiden dat L niet
regulier is.
CV want regulier
CV want CV grammatica voor te vinden
Niet CV
CV want unie van 2 CV talen
CV want CV grammatica voor te vinden
1
, 1.2 Why care?
• Many concepts in programming languages require a context-free language. E.g., "correct
brackets”
• Syntax of (programming) languages often given as a context-free grammar(Backus–Naur
form (BNF))
• Implications on parsing, compiler design, ...
2 Derivations
In elke stap in een derivation moeten 2 keuzes gemaakt worden:
• Welke variabele gaan we vervangen?
o Heeft geen invloed op eindresultaat (CV!)
• Welke regel gaan we gebruiken om deze variabele mee te vervangen
o Kan aanleiding geven tot ambiguity
▪ ∃𝑤 ∈ 𝐿: ∃ 𝑣𝑒𝑟𝑠𝑐ℎ𝑖𝑙𝑙𝑒𝑛𝑑𝑒 𝑝𝑎𝑟𝑠𝑒 𝑡𝑟𝑒𝑒𝑠 𝑣𝑜𝑜𝑟 𝑤
2.1 Leftmost en rightmost derivations
Definitie leftmost derivation:
Een derivation is leftmost als in iedere stap steeds de meest linkse variabele in de sentential form
vervangen wordt.
Definitie rightmost derivation:
Een derivation is rightmost als in iedere stap steeds de meest rechtse variabele in de sentential form
vervangen wordt.
2.2 Derivation trees/parse trees
2
1 Context-vrije grammatica’s
Grammatica = constructieve manier om een taal te beschrijven
Definitie:
Een grammatica 𝐺 = (𝑉, 𝑇, 𝑆, 𝑃) is context-vrij als alle productieregels van volgende vorm zijn
𝐴→𝑥
Met 𝐴 ∈ 𝑉 en 𝑥 ∈ (𝑉 ∪ 𝑇)∗
Opmerking: Elke reguliere grammatica is ook een context-vrije grammatica.
Definitie context-vrije taal:
Een taal L is context-vrij indien een context-vrije grammatica G bestaat waarvoor geldt dat L(G) = L.
Opmerking: dezelfde taal zal vaak ook kunnen voorgesteld worden door een grammatica die niet
context-vrij is. Dit betekent echter niet dat de taal niet context-vrij is!!
1.1 Bewijzen context-vrij
Bewijs dat 𝐿 = {𝑎𝑛 𝑏𝑚 : 𝑛 ≠ 𝑚} een context-vrije taal is.
• Stel 𝐿= = {𝑎𝑛 𝑏𝑚 : 𝑛 = 𝑚}. Van deze taal hebben we bewezen dat ze niet regulier is door
middel van de pompstelling.
• Stel 𝐿𝑟𝑎𝑛𝑑 = 𝑎∗ 𝑏 ∗ . Deze taal is regulier aangezien we ze voorstellen door middel van een
reguliere expressie.
Nu is 𝐿= = 𝐿𝑟𝑎𝑛𝑑 − 𝐿. We weten dat het verschil van 2 reguliere talen weer een reguliere taal is.
Maar we weten dat 𝐿= zeker niet regulier is en 𝐿𝑟𝑎𝑛𝑑 zeker wel dus kunnen we afleiden dat L niet
regulier is.
CV want regulier
CV want CV grammatica voor te vinden
Niet CV
CV want unie van 2 CV talen
CV want CV grammatica voor te vinden
1
, 1.2 Why care?
• Many concepts in programming languages require a context-free language. E.g., "correct
brackets”
• Syntax of (programming) languages often given as a context-free grammar(Backus–Naur
form (BNF))
• Implications on parsing, compiler design, ...
2 Derivations
In elke stap in een derivation moeten 2 keuzes gemaakt worden:
• Welke variabele gaan we vervangen?
o Heeft geen invloed op eindresultaat (CV!)
• Welke regel gaan we gebruiken om deze variabele mee te vervangen
o Kan aanleiding geven tot ambiguity
▪ ∃𝑤 ∈ 𝐿: ∃ 𝑣𝑒𝑟𝑠𝑐ℎ𝑖𝑙𝑙𝑒𝑛𝑑𝑒 𝑝𝑎𝑟𝑠𝑒 𝑡𝑟𝑒𝑒𝑠 𝑣𝑜𝑜𝑟 𝑤
2.1 Leftmost en rightmost derivations
Definitie leftmost derivation:
Een derivation is leftmost als in iedere stap steeds de meest linkse variabele in de sentential form
vervangen wordt.
Definitie rightmost derivation:
Een derivation is rightmost als in iedere stap steeds de meest rechtse variabele in de sentential form
vervangen wordt.
2.2 Derivation trees/parse trees
2
