Kontextfri grammatik

Från Rilpedia

Texten från svenska Wikipedia

Kontextfri grammatik är en särskild typ av formell grammatik. Kontextfri grammatik förkortas ofta med CFG (av 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 --> läser
N --> barnet

Denna lilla grammatik kan bara generera satsen "Barnet läser" genom att S(startsymbol) 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(läser) och ett substantiv(barnet) så följden blir att den bara kan generera frasen "barnet läser".