Kontextfri grammatik

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2018-12) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Kontextfri grammatik, även sammanhangsfri 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å kallade 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ögerled 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.

En restriktionsfri grammatik tillåter även terminala symboler i vänsterledet, och kan beskriva mer komplexa språk än en sammanhangsfri grammatik.

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".