For faster navigation, this Iframe is preloading the Wikiwand page for Contextvrije grammatica.

Contextvrije grammatica

Uit Wikipedia, de vrije encyclopedie

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

waarbij V een niet-terminaal symbool is en w een string, die mogelijk leeg is, met terminale en niet-terminale symbolen. Dit soort formele grammatica's worden contextvrij genoemd omdat de manieren waarop een niet-terminaal symbool kan worden herschreven 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 of EBNF worden gebruikt. Ze worden ook gebruikt voor het analyseren van de zinsbouw (syntaxis) van natuurlijke talen.[1]

Formele definitie

Een contextvrije grammatica G is een vier-tupel met de eigenschappen

  • is een eindige verzameling variabelen
  • is het alfabet van de taal, een eindige verzameling symbolen
  • , d.w.z. dat hetzelfde symbool niet zowel in als mag liggen
  • is een eindige deelverzameling van

Daarin is de Kleene-ster van dat wil zeggen, de eindige rijtjes die uit elementen van bestaan.

De elementen van worden de niet-terminale symbolen of variabelen genoemd. Dit zijn de hulpsymbolen die gebruikt worden bij het genereren van een zin. De elementen van worden de terminale symbolen genoemd, het zijn de symbolen die voorkomen in een zin van de taal. Er geldt dat Het symbool heet het startsymbool. De elementen van worden productieregels genoemd en meestal geschreven in de vorm , waarbij en . De grammatica produceert via de productieregels uit de formele taal van woorden bestaande uit de letters, symbolen uit het alfabet .

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

Voorbeeld

Een eenvoudige contextvrije grammatica met twee productieregels is met als productieregels :

Het enige niet-terminale symbool is , dit is hierdoor ook het startsymbool, en de terminale symbolen zijn en . Via de afleiding

kan bijvoorbeeld het woord uit deze grammatica worden afgeleid. In het algemeen genereert de grammatica de niet-reguliere taal , dat wil zeggen alle tekenreeksen die uit een of meer 's gevolgd door precies evenveel 's bestaan.

{{bottomLinkPreText}} {{bottomLinkText}}
Contextvrije grammatica
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Wikiwand 2.0 is here 🎉! We've made some exciting updates - No worries, you can always revert later on