Kontextfri grammatik
Wikipedia
Kontextfri grammatik är en särsild typ av formell grammatik. Kontextfri grammatik förkortas ofta med CFG (ev eng. context-free grammar).
Kontextfri grammatik beskrevs först av Noam Chomsky i den s.k. Chomskyhierarkin.
Det går att skapa mycket effektiva parsrar för kontextfri grammatik.
Det finns en uppsjö av sätt att skriva en kontextfri grammatik på men det vanligaste är en uppsättning regler med ett vänster och ett höger-led där vänsterledet består av en icke-terminal symbol (Fraskategori) och där högerledet består av en eller flera terminala eller icke-terminala symboler som vänsterledet kan skrivas om till.
Exempel: S --> NP VP
NP --> N
VP --> V
V --> dör
N --> pojken
Denna lilla grammatik kan bara generera satsen "pojken dör" genom att S(startymbol) får skrivas om till NP(nominalfras) följd av en VP(Verbfras). NP får skrivas om till ett N(Substantiv) och VP får skrivas om till V(Verb). Grammatiken tillåter bara ett verb(dör) och ett substantiv(pojken) så följden blir att den bara kan generera frasen "pojken dör".
