Talen en automaten/2011-12/producten/Shakespeare
Shakespeare
Max Tijssen, Simon van Raaij
Talen en automaten 2011-12
|
15:15 B |
 |
== Beschrijving ==
Onze case study gaat over de taal Shakespeare. Het is een esotorische taal met als doel om er uit te zien alsof het een door Shakespeare geschreven is.
Variabelen zijn allemaal van de vorm vectoren van signed integers, en worden gedeclareerd als karakters uit Shakespeare toneelstukken. Denk hierbij bijvoorbeeld aan karakters als Julia of Hamlet. De naam van deze karakters is belangrijk (mits ze uit een stuk van Shakespeare komen), alleen de vooraf aangegeven namen mogen gebruikt worden, anders zal het programma niet correct compilen (dit betekent dus dat er een bovengrens aan het aantal variabelen is).
De code wordt gedeclareerd door eerst een titel te geven. Alles voor de eerste punt wordt gezien als titel, en beschouwd als comment. Hierna volgt een lijst van karakters, met een beschrijving die geen feitelijke functie heeft, maar het er wel authentieker laat uitzien. Dit alles wordt gevolgd door de daadwerkelijk code.
De code bestaat uit Actes welke weer bestaan uit Scenes. Ze worden gedeclareerd door het woord “Act” of “Scene” gevolgd door een Romeins cijfer. Ze helpen de code leesbaar te houden, alsook als labels voor goto statements.
Nummers worden binnen de taal vertaald naar beschrijven. Ieder object heeft de waarde 1(voor iets positiefs, zoals sunshine, of iets neutraals zoals tree) of -1 (voor iets negatiefs zoals garbage). Daarnaast kun je aan voorwerpen beschrijvingen plakken, door ieder voorvoegsel wordt het object met 2 vermenigvuldigt.
Bijvoorbeeld:
Bright everlasting sunshine= 2*2*1=4
Smelly lying old intriguing garbage = 2*2*2*-1= - 8
Op deze objecten kan je berekeningen loslaten.
Bijvoorbeeld een manier om 1096 op een klein beetje overbodig lastige manier uit te drukken:
The sum of my shiny metal heavy ring and the square of your rusty old big weird bewitching cane and the cube of your jumpy little nephew= 2*2*2*1+(2*2*2*2*2*1)^2 + (2*2*1)^3= 8+32^2+4^3 = 8+1024+64= 1096.
Daarnaast kun je ook denken aan operatoren zoals worteltrekken of het verschil nemen.
Op deze manier zijn alle gehele getallen te produceren, al dan niet via een erg lange beschrijving.
Waardes aan karakters worden op een vergelijkbare manier toegeschreven, namelijk door het karakter door een ander te laten beschrijven.
Bijvoorbeeld: You amazing old man.
Hiermee wijs je direct een waarde aan iets toe, namelijk de waarde van het getal wat volgt na ‘You’, in dit geval wordt de waarde van de person waar tegen gesproken wordt dus vier.
Daarnaast kan je ook verwijzen naar de waarde van het doel op dit moment via woorden als ‘Thyself’ .
Voorbeeld:
You are a half-witted, hairy hog. You are as bad as the difference between yourself and the sum of a fine, fair flower and the sweetest, sunny, smooth summer’s day.
Dit komt neer op
X = -4
X = X – (4 + 8)
Dus wordt aan de persoon een waarde van 4-12=-16 toegekend.
Gezien de hoeveelheid karakters in de werken van Shakespeare niet oneindig is, is er besloten elk karakter de mogelijkheid te geven meer dan een waarde te laten onthouden. Dit wordt gedaan door simpele push en pop statements.
Als een karakter zegt “Remember me” dan wordt de waarde van dit karakter toegevoegd aan het geheugen de toegesprokene.
Als een karakter een zin zegt die begint met “Recall”, dan wordt de laatste waarde van de luisteraar z’n geheugen aan de luisteraar toegekend.
Output in deze taal wordt geregeld via twee zinnen: “ Open your heart” , in dit geval wordt de leterlijke numerieke waarde van de person waartegen gepraat wordt terug gegeven(dus niet van de person die praat, maar van het doelwit).
Dus bijvoorbeeld als er een scene is waarin Romeo en Julia spelen:
Juliet: You lovely amazing caring man.
Open your heart!
In dit geval word het getal 8 terug gegeven.
Daarnaast is er ook de zin “Speak your mind” in dit geval wordt het teken dat correspondeert met de huidige waarde van een karakter als output gegeven. Hieronder een voorbeeld om de letter ‘z’ te produceren. Hiervoor moet het karater de waarde 122(in ASCII codering) hebben.
Juliet:
You are as great as the sum of my everlasting eternal grateful satisfying neverending astounding love and your happy beautiful small great blinding smile and your amazing unbelievable pretty round big eyes.
Speak your mind!.
Een karakter kan natuurlijk alleen spreken als deze op het podium is. Dit wordt aangegeven met de Enter, Exit en Exeunt functies. Enter wordt gevolgd door een lijst van een of meer karakters. Exit, door een enkel karakter. En Exeunt (het meervoud van Exit) door een lijst van 2 of meer karakters. Indien er geen lijst volgt na Exeunt, wordt aangenomen dat iedereen het podium verlaat.
Voorbeeld:
[Enter Romeo and Hamlet]
[Exit Hamlet]
[Enter Juliet and Ophelia]
[Exeunt Romeo and Juliet]
Dit zou Ophelia op het podium laten.
Input statements worden geregeld op een vergelijkbare wijze als output statements: Om een getal op te vragen gebruik je “Listen to your heart”, om een character op te vragen “Open your mind”.
Goto statements worden ook uitgesproken door de karakters op de volgende wijze:
[Let us/We shall/We must] [return to/proceed to] [act/scene] X
Conditionele statements worden gemaakt door een karakter een vraag te laten stellen, en de ander de daadwerkelijke statement.
Voorbeeld:
Romeo:
Is the sum of me and Juliet better than a golden plum?
Hamlet:
If so, you are a lying bastard and we must return to scene III.
Dit kijkt of Romeo + Juliet groter is dan 2, en indien dat zo is wordt Romeo gelijk gesteld aan -2, en springt het programma naar scene 3 van dezelfde acte.
== Regulier? ==
Om te bewijzen dat Shakespeare niet regulier is zullen wij gebruik maken van het pumpin lemma. Eerst nemen we aan de taal wel regulier is, dit zou beteken dat er een woord z wat in de taal voorkomt , dus wat door een DFA met k toestanden moet kunnen worden gecreeerd, en lengte(z) > k.
Volgens het pomplemma betkekent dat dat je z op kunt delen in z=uvw waarbij v pompbaar is, dus:
z=uv i w met i >= 0 en lengt( uv) < k en lengte(z) > k.
Nu bewijzen we dat dit niet zo kan zijn doordat er een afhankelijkheid is tussen welke personages zich op het toneel bevinden. Een personage kan namelijk alleen het toneel betreden als hij zich daar niet al bevind, en hij kan er alleen vanaf gaan als hij er al stond, anders volgt er een runtime error en bevind het zich dus niet meer in correcte syntax.
Neem het voorbeeld :
z=[Enter Hamlet and Romeo and Juliet and....][Exeunt] totdat er k karakters genoemd zijn, die door exeunt daarna ook allemaal het toneel weer verlaten.
Volgens het pumpin lemma zou doordat in z=uvw uv<k moeten zijn , waardoor het pompbare deel zich ergens in het [Enter Hamlet and.....] moet bevinden, waardoor of er meerdere male [Enter Enter Enter....] zou zijn(wat geen correcte syntax is) of er zal een of meerdere karakters meerdere malen het toneel betreden.
Aangezien het geen correcte syntax is als er karakters meerdere malen het podium betreden bevind z zich hierdoor niet langer in de taal, en is er dus een woord z gevonden wat groters is dan k maar niet pompbaar, dit leid tot tegenspraak met de aanname dat Shakespeare regulier is en daaruit volgt dat Shakespeare niet regulier kan zijn.
== Contextvrij? ==
Om te bewijzen dat Shakespeare een contextvrije taal is, moet er een contextvrije grammatica gemaakt kunnen worden. De code bestaat allereerst uit één of meer actes:
S → ACTES
ACTES → ACTE ACTES || ACTE
Elke acte heeft een nummer, een titel en dan één of meer scenes:
ACTE –> acte TITEL SCENES
SCENES → SCENE SCENES || SCENE
Waarbij scenes als volgt zijn opgebouwd:
SCENE→scene TITEL [enter KARAKTERS ]
KARAKTERS → karakter KARAKTERS LEAVEKARAKTER(andere variabelen per karakter) || karakter BESCHRIJVINGEN LEAVEKARAKTER
BESCHRIJVINGEN → BESCHRIJVING BESCHRIJVINGEN || λ
BESCHRIJVING → VOORZETSEL zelfstandignaamwoord
VOORZETSEL → voorzetsel VOORZETSEL || λ
LEAVEKARAKTER → [exit karakter]
