Contextvrije grammatica

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een contextvrije grammatica is een formele grammatica waarbij alle productieregels de volgende vorm hebben:

V \rightarrow w

waarbij V een niet-terminaal symbool is en w een (mogelijk lege) string met terminale en niet-terminale symbolen. Dit soort formele grammatica's worden contextvrij genoemd omdat de manieren waarop een niet-terminaal symbool herschreven kan worden onafhankelijk zijn van de context waarin het zich bevindt. Contextvrije grammatica's genereren contextvrije talen.

Contextvrije grammatica's worden veel gebruikt bij het beschrijven en ontwerpen van programmeertalen en compilers, waarbij vaak de notatietechnieken Backus-Naur Form (BNF) of EBNF gebruikt worden. Ze worden ook gebruikt voor het analyseren van de syntaxis van natuurlijke talen.

Formele definitie[bewerken]

Een contextvrije grammatica G is een vier-tupel  (V, \Sigma, R, S\,) met de eigenschappen

  • V\, is een eindige verzameling variabelen
  • \Sigma\, is het alfabet van de taal, een eindige verzameling symbolen
  • V \cap \Sigma= \emptyset, d.w.z. dat hetzelfde symbool niet zowel in V als \Sigma mag liggen
  • S \in V
  • R\, is een eindige deelverzameling van V \times (V \cup \Sigma)^*

Daarin is (V \cup \Sigma)^* de Kleene-ster van V \cup \Sigma, dat wil zeggen, de eindige rijtjes die uit elementen van V \cup \Sigma bestaan.

De elementen van V worden de niet-terminale symbolen genoemd; dit zijn de hulpsymbolen die gebruikt worden bij het genereren van een zin. De elementen van \Sigma worden de terminale symbolen genoemd; het zijn de symbolen die voorkomen in een zin van de taal. Er geldt dat V \cap \Sigma= \empty. Het symbool S heet startsymbool. De elementen van R\, worden productieregels genoemd en meestal geschreven in de vorm A \to w, waarbij A \in V en w \in (V \cup \Sigma)^*. De grammatica G produceert via de productieregels uit R de formele taal L(G) van woorden bestaande uit de letters (symbolen) uit het alfabet \Sigma.

Volgens de definitie geldt voor een productieregel A \to w, dat A een niet-terminaal symbool is, dus niet omgeven door andere symbolen. Toepassing van de regel, waardoor A vervangen wordt door w, is dus onafhankelijk van de context.

Voorbeeld[bewerken]

Een eenvoudige contextvrije grammatica met twee productieregels is (\{S\},\{a,b\},S,R), met de productieregels:

SaSb
Sab

Het enige niet-terminale symbool is S (dit is hierdoor ook het startsymbool) en de terminale symbolen zijn a en b. Deze context-vrije grammatica genereert de niet-reguliere taal \{ a^n b^n : n \ge 1 \}, dat wil zeggen, alle tekenreeksen die bestaan uit een of meer a's gevolgd door precies evenveel b's.

Zie ook[bewerken]