Kontextfri grammatik

Från Wikipedia
Hoppa till: navigering, sök

Kontextfri grammatik, även restriktionsfri 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.

Exempel[redigera | redigera wikitext]

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