Hulp
Deze pagina aan uw boek toevoegen
Boek weergeven (27 pagina's)
Pagina's suggererenTalen en automaten/2011-12/producten/Foo
Foo
Mark Vijfvinkel, Aram Verstegen
Talen en automaten 2011-12
|
14:15 A |
 |
Beschrijving[1]
Foo is een esoterische taal gebaseerd op BrainFuck. Het is in 2008 ontwikkeld door "Feky" [2]. De taal maakt gebruik van een eendimensionale array in combinatie met een pointer. Verder zijn er een stack en kopieeroperaties aanwezig. De stack wordt voornamelijk gebruikt voor rekenkundige operaties en loops. Programma's in Foo stoppen als de interpreter aan het einde van het bestand komt (EOF).
Er wordt gebruik gemaakt van de volgende operators:
| Teken | Betekenis |
|---|---|
| " | Alles tussen deze tekens wordt afgedrukt naar stdout. |
| & | Zet de waarde van de geselecteerde cel in de array om naar een andere waarde. Gevolgd door een nummer (&55) levert dit de waarde 55 in de cel. Zonder nummer wordt er een waarde van de stack gepopped. |
| @ | Vergelijkbaar met '&' alleen wordt er een waarde op de stack gepushed. |
| < | Verlaag de array pointer met één. |
| > | Verhoog de array pointer met één. |
| $ | Drukt een enkele waarde af. Er zijn drie mogelijkheden: druk af als integer (i), druk af als hexadecimaal integer (h) en als ASCII karakter (c). Als er niks wordt gespecificeerd wordt er een foutmelding gegeven door de interpreter. |
| +, -, *, /, % | Rekenkundige operators, deze worden toegepast op het huidige element in de array. |
| # | Pauzeert de uitvoering van het programma voor opgegeven aantal seconden. |
| ( | Begin van een loop, als dit gevolgd wordt door een nummer dan wordt die loop uitgevoerd zolang de waarde in de cel ongelijk is aan de opgegeven waarde. Als er geen nummer is opgegeven dan wordt de loop uitgevoerd zolang de waarde in de cel ongelijk is aan nul. |
| ) | Einde van de loop, er wordt teruggesprongen naar de laatste '(' en als de waarde van de cel gelijk is aan het eerder opgegeven nummer, dan wordt verder gegaan met de rest van code. |
Voorbeeld programma in Foo: Countdown loop
&10(0#1-1$i$c10)"boom!"$c10
Regulier?
Aan de hand van de beschrijving en het voorbeeld wordt duidelijk dat er een afhankelijkheid zit in de haakjes. Een correct programma moet namelijk evenveel openingshaakjes als sluitingshaakjes bevatten. Dit doet vermoeden dat de taal Foo, vanaf nu 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 L} waarschijnlijk niet-regulier is.
Om dit formeel te bewijzen maken we gebruik van het pomp-lemma. Hiervoor stellen we eerst dat 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 L} wel regulier is. Dat zou betekenen dat er een automaat (DFA) is met 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 k} toestanden die een woord 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 z \in L} accepteert.
Voor elke 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 z} met 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 lengte(z) \ge k } , kunnen we 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 z} schrijven als 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 z = uvw } , met 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 lengte(uv) \le k } , 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 lengte(v) > 0} en dus 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 u v^i w \in L} , met 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 i \ge 0} .
We kiezen een string 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 z} die er als volgt uit ziet:
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 (^k...)^k} waarbij ... vervangen wordt door geldige code die voldoet aan de bovenstaande beschrijving, dit is voor het bewijs niet interessant. Waarbij 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 z} voldoet aan de eigenschap 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 lengte(z) \ge k} .
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 z} kunnen we opdelen in 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 uvw} , waarbij 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 uv} onderdeel is van de eerste 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 k} letters van 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 z} .
Als we 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 v} gaan pompen met lengte 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 j} , waarbij 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 0 < j \le k} dan krijgen we 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 uv^2w} . Dit kunnen we weer schrijven als 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 (^k (^j ... )^k} .
Hieraan kunnen we zien dat er meer openingshaakjes zijn dan sluithaakjes. Dit toont aan dat de string niet pompbaar is en dus niet voldoet aan de pompstelling. Dit betekent dat de taal 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 L} , en dus Foo, niet regulier is.
Contextvrij?
Nu we weten dat Foo niet regulier is en dat we het aantal haakjes moeten bijhouden in een soort geheugen, kunnen we vermoeden dat Foo waarschijnlijk contextvrij is. Om dit formeel te bewijzen moeten we een contextvrije grammatica of PDA maken die de taal beschrijft of herkent.
We maken de volgende grammatica:
S --> "A"S | &V | @V | <S | >S | $F | +V | -V | *V | /V | %V | #V | (S) | λ A --> characters(a..z, A..Z, 0..9, interpunctie)AS | λ V --> 0..9VS | λ F --> iS | hS | cS | iVS | hVS | cVS
Hier hebben we de nonterminals gegroepeerd in A (alphabet), V, (values) en F (format strings). Alle basisoperaties volgen uit de definitie van S (statement).
Aan deze grammatica is te zien dat het aantal openingshaakjes gelijk blijft aan het aantal sluitingshaakjes. Bij de non-terminal 'S' kan namelijk gekozen worden voor (S), waarmee de haakjes direct zijn afgesloten, om vervolgens weer iets uit 'S' te kiezen. We kunnen dit blijven doen en iedere keer zullen er een '(' en ')' gegenereerd worden.
Hiermee hebben we dus aangetoond dat Foo beschreven kan worden aan de hand van een contextvrije grammatica. Dus Foo is daardoor een contextvrije taal.
