Talen en automaten/2011-12/producten/C
C
Asli Tokbay
Talen en automaten 2011-12
|
13:50 A |
Beschrijving
De programmeer taal C is oorspronkelijk ontwikkeld als een basis voor het Unix besturings systeem tussen 1969 en 1973. De standaard C die wij nu kennen (C89) is een specificatie van het American National Standards Institute (ANSI) gebaseerd op C specificatie voor Unix. Uitbreidingen op deze standaard zijn C99 en C11.
De taal zelf is gebaseerd op de programmeer taal B. Wij zullen hier alleen de onderdelen van C bespreken die nodig zijn voor onze bewijzen. Alle statements worden afgesloten met een ';'. Programma's zijn opgebouwd uit functies waarbij 'main' meestal het beginpunt aanduid. Een functie definitie en implementatie zien er als volgt uit.
<source lang=c>
int functie_naam(char* parameter, short andere_parameter);
//implementatie
int functie_naam(char* parameter, short andere_parameter)
{
}
</source>
Binnen de '{' en '}' kan code geschreven worden die uitgevoerd word als de functie aangeroepen word. Om de flow van het programma te beïnvloeden kan er onder andere gebruik gemaakt worden van een 'if' statement. Als een vergelijking waar is zal de code binnen de haken uitgevoerd worden.
<source lang=c>
if (test == true)
{
}
</source>
Een if statement kan binnen zijn code blok een nieuw if statement bevatten. Binnen een code blok kan een functie aangeroepen worden door zijn naam te schrijven gevolgt door '(' en ')' met daartussen zijn parameters.
Referenties:
ANSI C specificatie, http://eli-project.sourceforge.net/c_html/c.html
C achtergrond informatie, http://en.wikipedia.org/wiki/C_%28programming_language%29
Regulier?
Stel dat C regulier is. Dan is er voor elk woord 'w' bestaande uit de woorden x, y en z waarvoor geld dat x yi z met i >= 1 ook onderdeel is van C.
w = if (test) { }
x = Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lambda}
y = if (test) {
z = }
Dit is onderdeel van C, voor een reguliere taal zou nu gelden dat de volgende woorden ook in C zouden moeten zitten.
if (test) { if (test) { }
if (test) { if (test) { if (test) { }
Dit is geen geldige C code omdat elke '{' een corresponderende '}' moet hebben. Dit toont aan dat C geen reguliere taal is.
Contextvrij?
Definitie: context vrije taal wordt gegenereerd door context vrije grammatica.
context vrije grammatica Bestaat uit (Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma} , V, P, S) Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma} - alfabet, V eindig
hoeveelheid variabelen, P staten, S begin staat.
Een context vrije taal laag geen dubbele betekenissen toe. Een woord moet in elke context dezelfde betekenis hebben, als een taal hier niet aan voldoet dan is het niet context vrij.
Te bewijzen:
C is wel/niet context vrij.
Bewijs:
Hier is geen gebruik gemaakt van pumping lemma maar van voorbeelden.
Stel er is een stuk code in C. Als het context vrij is kan je altijd afleiden wat
dat stukje code hoort te doen.
Bijvoorbeeld:
<source lang=c>
A = B();
</source> Het is hieruit niet te zien of B() een functie is of iets anders.
Een andere voorbeeld is:
<source lang=c>
foo bar(int(x));
</source>
Afhankelijk van de context kan dit meerdere dingen betekenen en is dit stukje code
niet context vrij.
Het wordt niet in de grammatica beschreven.
Er is een tegenbewijs gevonden dus C is niet context vrij.
Referenties
Context vrije talen, http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/node37.html
