Advertentie | |
|
04-10-2006, 13:08 | |||||||||||
Even antwoorden. Sorry dat het zo lang duurde.
Citaat:
Citaat:
Citaat:
Maar ik gok een terminal. Citaat:
Citaat:
Dat wist ik niet eens. Ik heb er nog nooit iemand over gehoord en ik heb op andere scholen opgaven gezien waar je zeker zo'n 3 à 4 geneste IF's had, minimaal. Citaat:
Even bewust je iteratie overslaan, daar kom ik zo wel tot. Citaat:
2. Staat niet in de opgave, maar moet misschien wel... Weet ik eigenlijk niet. 3. Ja, maar dat zei ik hierboven al. Citaat:
Citaat:
En analoog daaraan mag ik een non-terminal met een or-clause opsplitsen in twee verschillende non-terminals? bv: <stat> ::= <expr> ; | <forstat> | <ifstat> naar: <stat> ::= <expr> ; <stat> ::= <forstat> <stat> ::= <ifstat> Worden dingen zo makkelijker voor beginners, of moet ik toch maar met die or-clause erin blijven werken? Citaat:
Bij <expr> zetten we immers ook identifier neer? Zelfde geldt dan toch voor <stat>? Of is dat juist die laatste iteratie? Zoja, dan zou dit hem moeten zijn: FIRST(<forstat>) = {FOR} FIRST(<stat>) = {FOR, IF, IDENTIFIER} FIRST(<expr0>) = {ε, IDENTIFIER} FIRST(<expr>) = {IDENTIFIER} FIRST(<factor>) = {IDENTIFIER, (} FIRST(<ifstat>) = {IF} FIRST(<optional-else>) = {ε, ELSE} alhoewel ik er nog niet ben, wil je in ieder geval heel erg bedanken voor de hulp. Ik had er echt wat aan. edit: We zijn wat vergeten. <factor> Kan met een IDENTIFIER beginnen, maar ook met (. Immers, <factor> ::= IDENTIFIER | ( <expr> ) Toen ik dat als <factor> ::= IDENTIFIER <factor> ::= ( <expr> ) herschreef, viel me dat ineens op. Ik heb het hierboven al verbeterd. edit2: Ik heb nu de volgende Follower sets: FOLLOW(<forstat>) = {(, ε, identifier, for, if, $} FOLLOW(<stat>) = {ε, else} FOLLOW(<expr0>) = {;, )} FOLLOW(<expr>) = {;, +, )} FOLLOW(<factor>) = {identifier} FOLLOW(<ifstat>) = {(} FOLLOW(<optional-else>) = {for, if, identifier} Dit lijkt mij goed, alhoewel ik bang ben dat ik iets over het hoofd zie. Ik heb nu ook bepaald dat deze grammatica niet LL(1) is, dus dat moet ik nu doen (mbv een keyword FI. Waar staat dat voor? Einde IF?).
__________________
Bad spelling and grammar make me [sic].
Laatst gewijzigd op 04-10-2006 om 15:06. |
04-10-2006, 21:00 | |
Rob,
Je schreef: "Ik heb het voorbeeld dan ook niet verzonnen. Het origineel staat hier: http://www.cs.uiuc.edu/class/fa05/c...0sets%22" Aha! Bedankt! Daar heb ik wat aan. (Link werkte niet, maar als ik van daar verder zoek op ' example "first and follow sets" ' vind ik de pdf die jij bedoelt.) |
04-10-2006, 21:13 | ||||
Citaat:
Citaat:
De stappen voor het maken van Follower Sets? Die staan in dat PDFje waar ik naar linkte (zie hier en hoop dat ie het doet. ). In het kort: Je kijkt wat voor terminal er na een nonterminal komt, en schrijft dat op in die follow set. zoals in het PDFje: <S> ::= IF <E> THEN <S>; [...nog meer zooi, maar het gaat om het idee...] Dan is de followset van <S>: FOLLOW(<S>): {;, $} en die van <E>: FOLLOW(<E>): {THEN} Citaat:
Ja, zover was ik al. Ik had al snel genoeg door dat non-terminals daar met een uppercase waren en terminals allemaal lowercase waren. Ach, dat omschakelen maak ik me niet zo druk om. Daar heb ik zelden moeite mee gehad. Zo terug, even die first sets maar weer eens bekijken!
__________________
Bad spelling and grammar make me [sic].
|
Ads door Google |
04-10-2006, 22:26 | ||||
Citaat:
In <ifstat> komt ( alleen maar voor na IF. En IF is geen non-terminal. Dus je mag regel 2 van het algoritme hier niet toepassen (wederom: aangenomen dat we alleen maar follower sets bouwen voor non-terminals). Citaat:
Citaat:
Het zag er zo leesbaar uit, zo leesbaar kon een echte programmeertaal toch niet zijn? |
04-10-2006, 22:42 | ||
Citaat:
Noch via regel 1, noch via regel 2 kun je een ε in een follower set krijgen. En via regel 3 krijg je alleen dingen in follower sets die reeds in een andere follower set aanwezig zijn. Ik krijg trouwens een *veel* korter rijtje voor FOLLOW (<forstat>) ... ----- Nu moet ik er eigenlijk wel bij zeggen, dat ik enkel vanuit de beschrijving van het algoritme (p18) heb gewerkt; de voorbeelden die er na staan heb ik nog niet doorgewerkt. ----- Misschien moet ik toch eens nadenken over een andere naam. "NietVrolijk" past niet echt bij zo'n leuk onderwerp... |
04-10-2006, 22:46 | |||||
Citaat:
En ik neem aan dat de follow-sets alleen voor non-terminals gebouwd worden. Ik wist iig niet dat het ook voor terminals kon. Citaat:
Citaat:
Even kijken naar die regels: 1. Stop $ in FIRST(<S>), waar S start symbool is. Dan krijg ik dus FIRST(<forstat>) = {$} 2. Als er een productie <X> ::= α<Y>β bestaat, voeg dan FIRST(<β>) (maar niet ε) toe aan FOLLOW(<Y>) 3. Als er een productie <X> ::= α<Y> bestaat, of bestaat er een productie <X> ::= α<Y>β waar ε een subset is van First(<β>), voeg dan Follow(<X>) toe aan Follow(<Y>). Het probleem bij die regels van hun, is dat ik niet weet of α en β hier nou non-terminals of terminals zijn. Even kijken wat mijn school voor regels heeft. Citaat:
__________________
Bad spelling and grammar make me [sic].
Laatst gewijzigd op 04-10-2006 om 22:49. |
Advertentie |
|
04-10-2006, 23:38 | ||
Citaat:
<forstat> ::= FOR ( <expr0> ; <expr0> ; <expr0> ) <stat> maar ook op <expr> ::= <expr> + <factor> of op <ifstat> ::= IF ( <expr> ) <stat> <optional-else> Merk op, dat het hier in feite 4 verschillende regels betreft. De eerste zegt iets over Followers(<z>). Dat vertelt ons dus iets over Followers (<stat>) en Followers (<factor>) en Followers (<optional-else>) De tweede regel vertelt ons iets over Followers(<y>). In ons geval dus Followers (<expr0>), Followers (<expr0>), Followers(<expr>), Followers(<expr>) en Followers (<stat>). De derde regel vertelt ons iets over Followers(<y>) maar alleen als ε in First(<z>) zit. In ons geval dus alleen Followers(<stat>). De vierde regel vertelt ons iets over Followers(<x>), maar alleen als ε in First(<y>) zit. Dat komt in bovengenoemde 3 regels dus niet voor. |
05-10-2006, 00:05 | ||||||
Citaat:
of op een non-terminal die er zo uitziet: <a> ::= <y> + <z> of op <a> ::= ELSE <x>. Citaat:
Citaat:
Citaat:
Citaat:
Dan krijg ik dit: FOLLOW(<forstat>) = {$} FOLLOW(<stat>) = {ε, ELSE, $} FOLLOW(<expr0>) = {FOR, IF, IDENTIFIER, (} FOLLOW(<expr>) = {IDENTIFIER, (} FOLLOW(<factor>) = {IDENTIFIER, (} FOLLOW(<ifstat>) = {} FOLLOW(<optional-else>) = {} <ifstat> en <optional-else> zijn nog leeg. Hoort dit? Wat mij de volgende vraag geeft (jaja, ik blijf bezig. ): Hoe bepaal ik dan Followers van <ifstat> ::= IF ( <expr> ) <stat> <optional-else> <optional-else> ::= ε | ELSE <stat> en <forstat> ::= FOR ( <expr0> ; <expr0> ; <expr0> ) <stat>? Of zijn die er gewoon niet? Of worden die followers in andere Follow-sets beschreven?
__________________
Bad spelling and grammar make me [sic].
|
05-10-2006, 07:30 | ||||
Citaat:
Bijoorbeeld: Als je <a> ::= <x><y><z> wilt toepassen op <a> ::= if( <p> ) <q> <r>, kun je bijvoorbeeld denken aan: Schrijf if( <p> ) als <x>, <q> als <y> en <r> als <z> of: Schrijf if( als <x>, <p> als <y> en <q><r> als <z> of zelfs: Schrijf if( <p> )<q> als <x>, <r> als <y> en ε als <z> of: Schrijf if( <p> )<q> als ε als <y> en <x>, <r> als <z>. Uiteraard komt er dan in veel gevallen niets zinnigs uit. Citaat:
Maar ik ben nog niet tevreden: Ik zie bijvoorbeeld een ε in een van de regels staan. En ik denk dat dat niet mag. Verder staat er volgens mij veel te veel bij FOLLOW(<expr0>). Ik zie <expr0> namelijk slechts in *een* productieregel staan. En in die productieregel staat er steeds een terminal achter <expr0>. Dus je "weet" eigenlijk al wat er uiteindelijk in FOLLOW(<expr0>) terecht zal komen. Dus telkens als je een stap doet waardoor er iets anders in Follow(<expr0>) terecht zou komen, weet je dat er ergens in die stap (of eerder) een fout zit! Citaat:
Hier staat o.a.: <optional-else> ::= ELSE <stat> Dit is van de vorm <a> ::= <x><y><z> Neem maar <x>=ε, <y>=ELSE, <z>=<stat>. Je kunt dan deze regel toepassen: <a> ::= <x><y><z> --> Followers(<z>) bevat Followers(<a>) Dus als je eenmaal iets in FOLLOW(<optional-else>) hebt staan, kun je dat ook elders gebruiken. Hoe krijgen we nou iets in FOLLOW(<optional-else>)? Als je eens goed naar jullie regels kijkt, zie je dat er nergens iets wordt toegevoegd aan Followers(<a>), maar alleen maar aan Followers(<x>), Followers(<y>) of Followers(<z>). We moeten dus kijken naar productieregels waarin <optional-else> rechts van de ::= staat. Dat is dus deze regel: <ifstat> ::= IF ( <expr> ) <stat> <optional-else> Daar zul je dus deze regel op moeten toepassen: <a> ::= <x><y><z> --> Followers(<z>) bevat Followers(<a>) Je moet dus eerst iets weten over Followers(<ifstat>) Je moet dus op zoek naar een regel waarin <ifstat> rechts van de ::= staat. Dat is dus deze regel: <stat> ::= <expr> ; | <forstat> | <ifstat> Daarbij gaat het natuurlijk om: <stat> ::= <ifstat> Daarop kun je deze regel toepassen: <a> ::= <x><y><z> --> Followers(<z>) bevat Followers(<a>) En dan een tijdje doorrekenen ... |
05-10-2006, 11:45 | ||||
Citaat:
Citaat:
Citaat:
Even stap voor stap opschrijven wat ik doe: 1. $ komt in Followers(<startsymbool>) 2. <a> ::= <x>y --> Followers(<x>) bevat y 3. <a> ::= <x><y><z> --> Followers(<z>) bevat Followers(<a>) 4. <a> ::= <x><y><z> -->; Followers(<y>) bevat Starters(<z>) muv ε 5. <a> ::= <x><y><z>, met Starters(<z>) bevat ε --> Followers(<y>) bevat Followers(<a>) 6. <a> ::= <x><y><z>, met Starters(<y>) bevat ε --> Followers(<x>) bevat Starters(<z>) Na stap 1: $ komt in Followers(<startsymbool>) FOLLOW(<forstat>) = {$} FOLLOW(<stat>) = {} FOLLOW(<expr0>) = {} FOLLOW(<expr>) = {} FOLLOW(<factor>) = {} FOLLOW(<ifstat>) = {} FOLLOW(<optional-else>) = {} Na stap 2: <a> ::= <x>y --> Followers(<x>) bevat y FOLLOW(<forstat>) = {$} FOLLOW(<stat>) = {} FOLLOW(<expr0>) = {;, )} FOLLOW(<expr>) = {;, +, )} FOLLOW(<factor>) = {} FOLLOW(<ifstat>) = {} FOLLOW(<optional-else>) = {} (Hier laat ik de + bij factor even weg. Een <factor> kan een <expr> zijn gevolgd door een plus, maar dat is impliciet gegeven. Ik doe nu alleen de expliciete dingen.) Na stap 3: <a> ::= <x><y><z> --> Followers(<z>) bevat Followers(<a>) FOLLOW(<forstat>) = {$} FOLLOW(<stat>) = {$} FOLLOW(<expr0>) = {;, )} FOLLOW(<expr>) = {;, +, )} FOLLOW(<factor>) = {;, +, )} FOLLOW(<ifstat>) = {$} FOLLOW(<optional-else>) = {$} (Deze regel is alleen op de productie van <forstat>, <stat>, <expr> en <ifstat> te gebruiken) Na stap 4: <a> ::= <x><y><z> -->; Followers(<y>) bevat Starters(<z>) muv ε FOLLOW(<forstat>) = {IF, $} FOLLOW(<stat>) = {$} FOLLOW(<expr0>) = {FOR, IF, IDENTIFIER, (, ;, )} FOLLOW(<expr>) = {IDENTIFIER, (, ;, +, )} FOLLOW(<factor>) = {;, +, )} FOLLOW(<ifstat>) = {ELSE, $} FOLLOW(<optional-else>) = {$} (Door deze regel krijg ik zoveel bij expr0... In <forstat> staat <forstat> ::= FOR ( <expr0> ; <expr0> ; <expr0> ) <stat>, wat ik lees als <a> ::= FOR ( <y> ; <y> ; <y> ) <z>, wat geeft dat FOLLOW(<y>) = {FIRST(<z>)} en FIRST(<z>) = {FOR, IF, IDENTIFIER, (}). Na stap 5: <a> ::= <x><y><z>, met Starters(<z>) bevat ε --> Followers(<y>) bevat Followers(<a>) FOLLOW(<forstat>) = {IF, $} FOLLOW(<stat>) = {ELSE, $} FOLLOW(<expr0>) = {FOR, IF, IDENTIFIER, (, ;, )} FOLLOW(<expr>) = {IDENTIFIER, (, ;, +, )} FOLLOW(<factor>) = {;, +, )} FOLLOW(<ifstat>) = {ELSE, $} FOLLOW(<optional-else>) = {$} (Deze regel is alleen op <ifstat> toe te passen. Het is de enige die aan die vorm voldoet...). Na stap 6: <a> ::= <x><y><z>, met Starters(<y>) bevat ε --> Followers(<x>) bevat Starters(<z>) Deze is niet zinnig op iets toe te passen. Ook niet op <forstat> wat ik eerst dacht. Nu ik hiermee klaar ben, moet ik zeker gaan itereren? Terug naar stap 3! Dat geeft dit: FOLLOW(<forstat>) = {IF, $} FOLLOW(<stat>) = {IF, ELSE, $} FOLLOW(<expr0>) = {FOR, IF, IDENTIFIER, (, ;, )} FOLLOW(<expr>) = {IDENTIFIER, (, ;, +, )} FOLLOW(<factor>) = {IDENTIFIER, (, ;, +, )} FOLLOW(<ifstat>) = {IF, ELSE, $} FOLLOW(<optional-else>) = {IF, ELSE, $} Stappen 4,5 & 6 voegen volgens mij niets meer toe. Nog een keer alles. Dit voegt niets meer toe, en dit is dan mijn uiteindelijke lijst: FOLLOW(<forstat>) = {IF, $} FOLLOW(<stat>) = {IF, ELSE, $} FOLLOW(<expr0>) = {FOR, IF, IDENTIFIER, (, ;, )} FOLLOW(<expr>) = {IDENTIFIER, (, ;, +, )} FOLLOW(<factor>) = {IDENTIFIER, (, ;, +, )} FOLLOW(<ifstat>) = {IF, ELSE, $} FOLLOW(<optional-else>) = {IF, ELSE, $} Maar ik moet gaan. Ik ben zondagavond wel weer terug, en dan reageer ik weer. Prettig weekend en bedankt tot zover!
__________________
Bad spelling and grammar make me [sic].
Laatst gewijzigd op 05-10-2006 om 12:31. |
08-10-2006, 14:31 | ||
Citaat:
De regel luidt: 4. <a> ::= <x><y><z> -->; Followers(<y> ) bevat Starters(<z> ) muv ε Dus met andere woorden: Als er een non-terminal midden in een productieregel staat, mag je Starters("de combinatie van alles wat achter die non-terminal staat) toevoegen aan Followers("die betreffende non-terminal"). In dit geval gaat het om de volgende productieregel: <forstat> ::= FOR ( <expr0> ; <expr0> ; <expr0> ) <stat> Hierin komt <expr0> 3 keer voor. We kunnen regel 4 dus 3 keer toepassen: Eerste keer regel 4 toepassen: <forstat> ::= FOR ( <expr0> ; <expr0> ; <expr0> ) <stat> Op grond van deze regel mogen we het volgende aan Followers(<expr0>) toevoegen: Starters( ; <expr0> ; <expr0> ) <stat> ), en dat is natuurlijk {;}. Tweede keer regel 4 toepassen: <forstat> ::= FOR (<expr0> ; <expr0> ; <expr0> ) <stat> Op grond van deze regel mogen we het volgende aan Followers(<expr0>) toevoegen: Starters( ; <expr0> ) <stat> ), en dat is wederom {;}. Derde keer regel 4 toepassen: <forstat> ::= FOR (<expr0> ; <expr0> ; <expr0> ) <stat> Op grond van deze regel mogen we het volgende aan Followers(<expr0>) toevoegen: Starters( ) <stat> ), en dat is wederom {)}. Merk op, dat dit de resultaten zijn die je al bij stap 2 hebt opgeschreven. Diezelfde fout maak ik ook steeds. Maar dat maakt voor het eindresultaat natuurlijk geen verschil. --------------------- Als je het bovenstaande toepast, zul je zien dat in jouw uitwerking de terminals FOR, IF en identifier overal wegvallen. Tenslotte kun je regel 2 nog een keer toepassen op de productieregel voor <stat>. En dan zou je op hetzelfde uit moeten komen als wat ik heb. |
12-10-2006, 23:29 | |
Weinig tijd voor gehad, helaas. Wel naar gekeken, gelukkig en ik begin het te snappen. Dat deel wat jij uitlegde met expr0 had ik zelf echt niet opgekomen.
Maar ik begin nu andere vakken te krijgen, en ik moet voor dit vak een programma schrijven dat BNF herkent, parsed en dan verteld waarom iets niet LL(1) is. Dan mag ik dat dus gaan programmeren. Ik wacht wel even op de antwoorden zodat we kunnen zien of we het goed hebben gedaan. Meestal snap ik het met de antwoorden wel (vooral met deze thread!).
__________________
Bad spelling and grammar make me [sic].
|
13-10-2006, 23:12 | |
Rob hier. Dit is blijkbaar het antwoord:
De starter-sets waren correct. De follow-sets waren als volgt (en degene die ik had, waren best wel fout, eigenlijk...): FOLLOW(<forstat>) = {$, ELSE} FOLLOW(<stat>) = {$, ELSE} FOLLOW(<expr0>) = {;, )} FOLLOW(<expr>) = {;, )} FOLLOW(<expr-tail>) = {;, )} (waar deze vandaan komt, weet ik niet. Hij stond niet eens in de opgave!) FOLLOW(<factor>) = {;, ), **** FOLLOW(<ifstat>) = {$, ELSE} FOLLOW(<optional-else>) = {$, ELSE} Ik ben, zo te zien, ergens flink de mist in gegaan. Had jij dit als antwoord, of toch iets anders?
__________________
Sort zegt het en Sort is de baas. © Not for Sale | Hertog Jan.<3 | Stem BLANCO!! | ST!
|
14-10-2006, 01:16 | |
Ik had ook nog een + in FOLLOW (<expr0> ) (fout!)
en een + in FOLLOW ( <expr> ) (volgens mij wel goed) Ik denk dat ik bij <expr0> regel 3 een keer verkeerd om heb toegepast. Als je regel 4 toepast op <expr> ::= <expr> + <factor> dan zie je dat + ook in FOLLOW ( <expr> ) moet zitten. |
Ads door Google |
14-10-2006, 11:07 | ||
Oh, wacht even. =x
Citaat:
Dus ik ben het op zich wel met je eens over die + die er bij <expr> nog bij moet (als je het niet herschrijft, natuurlijk). Beetje krom dat ze eerst herschrijven en dan de follow-sets bepalen.
__________________
Sort zegt het en Sort is de baas. © Not for Sale | Hertog Jan.<3 | Stem BLANCO!! | ST!
Laatst gewijzigd op 14-10-2006 om 11:09. |
14-10-2006, 12:07 | |
Daar ben ik het niet helemaal mee eens.
<expr> ::= <factor> <expr-tail> <expr-tail> ::= ε | + <factor> <expr-tail> is volgens mij equivalent met <expr> ::= <factor> + <expr> | <factor>........................(1) en dat is toch echt iets anders als <expr> ::= <expr> + <factor> | <factor>........................(2) ------------- Kijk bijvoorbeeld eens naar de expressie a + b + c Volgens productieregel (1) moet je dan eerst b + c berekenen, en daarna a + "uitkomst van b + c". Volgens productieregel (2) moet je echter eerst a + b berekenen, en daarna "uitkomst van a + b" + c. Als voor + de associatieve eigenschap *niet* geldt, zit je dus so wie so al fout! Ook als de associatieve eigenschap *wel* geldt zijn deze productieregels niet echt aan elkaar gelijk. Denk maar eens aan de neveneffecten. Kijk bijvoorbeeld bij de "gewone optelling" eens naar: (x++) + y + (++x) Volgens productieregel (1) is de uitkomst 2x+y+1. Volgens productieregel (2) is de uitkomst 2x+y+2. ----------------- Eenzelfde verschil zit overigens ook al tussen beide interpretaties van x++ + ++x Dus in programmeertalen als C is de optelling in wezen niet commutatief! Dat geldt waarschijnlijk voor de hele Algol-familie (java, Pascal, C++, etc). ============= Nu ik er nog even iets beter over na denk, klopt het bovenstaande niet helemaal. De productieregel schrijft namelijk niets voor over de volgorde van *uitrekenen*, maar alleen over welke "uitkomsten" eerst met elkaar vermenigvuldigd moeten worden. Dus bij a + b + c zal bij productieregel (1) gelden dat je de *uitkomst* van a moet optellen met de "uitkomst" van b. De bijbehorende semantische regels zullen dan waarschijnlijk voorschrijven dat *eerst* a moet worden uitgerekend, en daarna pas b+c. Kortom: Productieregel (1) en (2) zijn *niet* gelijkwaardig als de optelling niet associatief is. Over commutativiteit valt hier niets te zeggen. |
15-10-2006, 21:50 | |
Ik vrees dat mijn vorige post niet erg duidelijk was.
Laat ik het eens anders formuleren: Er wordt in wezen beweerd dat: <expr> ::= <expr> - <factor> | <factor>................(1) equivalent is met: <expr> ::= <factor> <expr-tail>............................(2a) <expr-tail> ::= ε | - <factor> <expr-tail>................(2b) Laten we dit eens uitproberen op de expressie 5 - 3 - 2 Zoals we weten, is aftrekken niet associatief en ook niet commutatief. Dit is dus een mooie test-case. Productieregel 1 zegt dan: De expressie 5 - 3 - 2 bestaat uit de expressie 5 - 3, gevolgd door de terminal -, gevolgd door de factor 2. En de expressie 5 - 3 bestaat uit de expressie 5, gevolgd door de terminal -, gevolgd door de factor 3. Nu heeft 5 - 3 natuurlijk als resultaat 2. Het resultaat van expressie 5 - 3 - 2 is dus 2 - 2, en dat is 0. Productieregel 2 zegt echter: (2a) De expressie 5 - 3 - 2 bestaat uit de factor 5, gevolgd door de expressiontail - 3 - 2. (2b) De expressiontail - 3 - 2 bestaat uit de terminal -, gevolgd door de factor 3, gevolgd door de expressiontail - 2. (2b) De expressiontail - 2 bestaat uit de terminal -, gevolgd door de factor 2, gevolgd door de expressiontail ε. Semantisch gezien is de expressiontail een soort functie (het wiskundige begrip, niet het begrip uit computertalen) die je loslaat op de factor die er voor staat. Hierbij zal de gebruiker van de programmeertaal er doorgaans vanuit gaan dat <factor> <expr-tail> in (2a) hetzelfde betekent als <factor> <expr-tail> in (2b). Dat betekent dus dat expressiontail - 2 overeenkomt met de functie f(x) = x-2. Als we deze f loslaten op de factor 3, krijgen we dus als resultaat f(3) = 3-2 = 1. Dat betekent dus dat expressiontail - 3 - 2 overeenkomt met de functie g(x) = x-1. Als we deze f loslaten op de factor 5, krijgen we dus als resultaat g(5) = 5-1 = 4. Het resultaat van expressie 5 - 3 - 2 is dus 4. Kortom, grammatica-fragment (2) *suggereert* een betekenis die niet overeenkomt met de betekenis van productieregel (1). |
17-10-2006, 12:20 | |
Wat jij zegt klopt wel. Waar ik eigenlijk meer op doelde is: Er staat niet in de opdracht dat dat moest, doe het dan ook niet. Dat maakt het alleen maar nog onoverzichtelijker voor mij dan het al is. En waarschijnlijk ook voor de anderen.
Weetje, ik zat laatst na te denken over dit vak en ik kwam tot de simpele conclusie dat ik eigenlijk totaal geen idee heb van wat ik nou aan het doen ben en hoe dit in verband staat met programmeertalen die ik al ken. En ik ga het toch maar vragen, want ik wil het gewoon weten. Wat doe ik nu eigenlijk? Ik kan nu wel van een grammatica first en follow sets bepalen (nouja... kan... ) en aan de hand daarvan bepalen of die wel of niet LL(1) is. Maar ik snap niet wat dit met compilers, en dus, met programmeertalen te maken heeft. Ik zie die hele link niet, eigenlijk. Zou je 't uit kunnen leggen, want ik wil het weten, maar ergens klikt het allemaal niet echt.
__________________
Bad spelling and grammar make me [sic].
|
17-10-2006, 20:25 | |
Tja, dat is een goede vraag.
En ik kan hem niet echt beantwoorden, want daarvoor is het allemaal te ver weggezakt. Wij gebruikten bovendien andere termen, ik weet bijvoorbeeld niet wat LL(1) inhoudt. Voor zover ik mij herinner, werkten wij met een indeling van grammatica's in 4 types (van Van Wijngaarden, meen ik - maar het zou ook Noah Chomski kunnen zijn). Een van die vier types werd bijvoorbeeld gevormd door de "reguliere talen". Met grammatica's van het laagste type kon je niet veel beginnen. Maar met reguliere grammatica's kon dat wel. Daarbij kon je vervolgens weer onderscheid maken tussen links-regulier en rechts-regulier. -------------------------- Als een grammatica niet "netjes" in elkaar zit, krijg je bijvoorbeeld problemen met geneste IFs. Een voorbeeld daarvan zie je in deze opgave. Bijvoorbeeld in mijn bericht van 03-10-2006 @ 07:56. Aan de vorm van deze grammatica kun je "zien" dat er zulk soort meerduidigheden in zitten. Laatst gewijzigd op 17-10-2006 om 21:00. |
17-10-2006, 20:38 | |
Een vertaalprogramma (compiler of interpreter of zo) zal doorgaans de tekst van voor naar achter doorlopen (sommige compilers moeten dat meer dan 1 keer doen). En je wilt dan, dat de compiler herkent wat de programmeur bedoeld heeft.
Probeer je eens voor te stellen, dat jij een compiler bent. En stel, dat je een (correct) programma van bovenstaande grammatica voorgeschoteld krijgt. Je weet dan, dat je een <forstat> moet verwerken. Je leest dus om te beginnen de terminals FOR en ( in. Je weet, dat er vervolgens een <expr0> volgt, en daarna een terminal ; . Je weet, dat een <expr0> bestaat uit ofwel niets, ofwel een <expr>. Je weet, dat een <expr> niet kan beginnen met een ;, want ; is geen element van FIRST(<expr>). Dus: - als het volgende teken een ; is, ben je de eerste <expr0> gepasseerd. - als het volgende teken *geen* ; is, ben je dus bezig een <expr> te verwerken. |
17-10-2006, 20:59 | |
Problemen kunnen zich eigenlijk alleen maar voordoen, indien je voor een keuze staat.
Dus als er twee of meer productieregels bestaan voor een symbool, of als een productieregel een | bevat. (Dat komt natuurlijk op hetzelfde neer). Het wordt al meteen iets lastiger, indien twee keuzemogelijkheden op dezelfde manier beginnen. Bijvoorbeeld: <symb_1> = <symb_2> <symb_3> <symb_1> = <symb_2> <symb_4> Op het moment dat je binnen zo'n symb_1 een symb_2 aan het verwerken bent, weet je nog niet in welke productieregel je bezig bent. En dat is lastig. Enerzijds omdat je (als compiler) bruikbare foutmeldingen wilt geven. En anderzijds omdat je (als compiler) moet weten wat je het vertaalde programma moet laten doen. Deze situatie doet zich vaak vermomd voor: <symb_1> = <symb_2> | <symb_3> ... <symb_2> = <symb_4> <symb_5> ... <symb_3> = <symb_4> <symb_6> (Merk op dat je pas echt in de problemen zit, als vervolgens bijvoorbeeld blijkt dat een <symb_6> uit een <symb_5> kan bestaan) Daarom is het handig, als je grammatica's enigzins kunt analyseren. Veelal zul je bijvoorbeeld als compilerbouwer een grammatica zo willen herformuleren, dat je er makkelijker een compiler voor kunt bouwen. Maar tegelijkertijd wil je toch zo dicht bij de oorspronkelijke grammatica blijven, dat je goed kunt communiceren met de gebruiker (lees: de programmeur). En natuurlijk wil je ---voordat je begint met het schrijven van een compiler--- al weten of de grammatica eenduidig is. Zo niet, dan zul je een of andere beslissing moeten nemen. In veel gevallen komt dat neer op terugkoppelen naar de opdrachtgever. Als de opdrachtgever de opsteller van de grammatica is, zou hij/zij bijvoorbeeld de grammatica kunnen verbeteren. Of hij/zij kan stellen, dat in zo'n situatie altijd gekozen moet worden voor een bepaalde productieregel (waarbij jij als compilerbouwer dan doorgaans een warning zult genereren, zodat de programmeur ziet welke onduidelijkheid hij/zij geproduceerd heeft ---tenzij hij/zij de warnings niet leest, nauurlijk). |
18-10-2006, 00:23 | |||
Citaat:
Een LL(1) parser is een parser die de grammatica van Links naar rechts inleest, overal de Leftmost derivation van neemt en 1 token look-ahead heeft. LL(1), dus. Een LL(1) grammatica is pas LL(1) als - er geen links-recursieve betrekkingen in voorkomen - als de doorsnede van de Starter sets, behorend bij de verschillende productieregels voor één nonterminal, leeg is - en als de doorsnede van Starters en Followers set van een nonterminal met een leeg alternatief leeg is. Zoals je ziet komt dit overeen met wat jij in je laatste post zei. Citaat:
De rest van je post begrijp ik wel, dus het heeft naar mijn mening weinig nut om te quoten. Je geeft dan ook precies de reden waarom wij focusen op LL(1) grammatica's. Helaas ben ik geen compilerbouwer, maar een programmeur. Dus ik heb weinig interesse mbt hoe deze dingen werken, als ze maar werken. Ik zal mijn vraag even iets anders stellen, en iets algemener: Wat is een grammatica? Hoe maakt een grammatica deel uit van een compiler en dus van de programmeertaal waar die compiler voor is?
__________________
Bad spelling and grammar make me [sic].
|
18-10-2006, 07:00 | |
Voor mijn gevoel is een grammatica een soort beschrijving van hoe de taal is.
In de meeste gevallen kun je aan de grammatica al grotendeels zien wat de bijbehorende semantiek is. De punten waar de semantiek afwijkt van wat gebruikelijk is, worden doorgaans goed genoeg beschreven. Als ik kennismaak met een nieuwe taal (waarbij er hetzij geen tutorial bestaat, hetzij geen tijd beschikbaar wordt is om de tutorial door te lezen), dan beperk ik mij doorgaans tot het lezen van een korte inleiding, het bekijken van wat voorbeeldcode, en het vluchtig doorlezen van de grammatica. Als er vervolgens geen goed naslagwerk voorhanden is, gebruik ik de grammatica als naslagwerk. Als er *wel* een naslagwerk bestaat, zal ik daarin veelvuldig teruggrijpen naar de grammatica. ------- Een compiler kun je opbouwen aan de hand van een grammatica (tenminste, als die grammatica aan bepaalde eisen voldoet). Wij werkten destijds met CDL2 (een voorloper van CDL3). Die taal is zelfs zo opgezet dat het vertaalprogramma er zelfs (min of meer) uitziet als een grammatica. --------- Kijk bijvoorbeeld eens naar de productieregel <stat> ::= <forstat> | <ifstat> | <expr> ; Daar staat dus: Een <stat> is een <forstat>, of een <ifstat>, of een <expr> gevogd door een ';'. Een procedure die "probeert" een <stat> te verwerken, zal dus in eerste instantie een procedure aanroepen die probeert een <forstat> te verwerken. - Indien het lukt om de forstat te verwerken, kun je het resultaat gebruiken voor de verwerking van de <stat> - Indien het *niet* lukt om de forstat te verwerken, zal de betreffende procedure alle neveneffecten moeten terugdraaien. Vervolgens zal de oorspronkelijke procedure proberen een <ifstat> te laten verwerken. Als ook dat niet lukt, dan zal de procedure proberen een <expr> te laten verwerken. Als ook dat niet lukt, dan zal de procedure afsluiten met de boodschap dat het verwerken van de <stat> niet gelukt is (na eerst de neveneffecten te hebben teruggedraaid). |
18-10-2006, 07:15 | |
Bekijk vervolgens de productieregel:
<ifstat> ::= IF ( <expr> ) <stat> <optional-else> FI <optional-else> ::= ε | ELSE <stat> De procedure die een <ifstat> verwerkt, zal eerst kijken of het volgende symbool een IF is. Zoniet, dan zorgt de procedure er voor, dat de volgende procedure weer op de oorspronkelijke plaats begint te lezen (= terugdraaien van de neveneffecten), en meldt vervolgens dat het verwerken van de ifstat niet gelukt is. Is het lezen van de IF wel gelukt, dan *weten* we (vrijwel zeker) dat de programmeur een conditional clause heeft willen gebruiken. Dat kunnen we alvast gebruiken in *elke* foutmelding die we geven tijdens het verwerken van deze <ifstat>. We verwerken het haakje, en proberen vervolgens de <expr> te verwerken. Daarbij hanteren we als extra voorwaarde, dat het resultaat hetzij een boolean is, hetzij gecast kan worden naar een boolean. Als we een interpreter maken, bepaalt het resultaat of we uiteindelijk verdergaan met de then-tak of de else-tak. Als we een compiler maken, bepaalt het resultaat een stukje van het vertaalde programma. Stel bijvoorbeeld dat de doeltaal assembler is, dan heeft de <expr>-procedure een stukje code gegenereerd dat een boolean achterlaat op de stack. We voegen dan een stukje code toe een waarde van de stack haalt, en naar een locaal label L1 springt indien de waarde FALSE was. Vervolgens laten we de <stat>-procedure code genereren voor het THEN part. We voegen dan een stukje code toe die naar een locaal label L2 springt. We voegen locaal label L1 toe. We laten de <optional-else>-procedure code genereren voor het optionele else part. We verwerken de FI en voegen locaal label L2 toe. En tenslotte melden we terug dat het verwerken van de <ifstat> geslaagd is. Vaak is de doeltaal een tussentaal. Laten we eens aannemen dat die tussentaal de vorm heeft van een grammaticale boom. In dat geval weten we dus, dat we een IF-node moeten maken. We roepen de <expr>-procedure aan, en plaatsen het resultaat in de IF-tak van de IF-node. We roepen de <stat>-procedure aan, en plaatsen het resultaat in de THEN-tak van de IF-node. We roepen de <optional-else>-proceudre aan, en plaatsen het resultaat in de ELSE-tak van de IF-node. We verwerken de FI. Tenslotte geven we een verwijzing naar de IF-node terug als resultaat (plus de melding dat het verwerken van de <ifstat> geslaagd is). |
18-10-2006, 11:33 | |
Ja, okay. Het begint nu wel te dagen wat het precies is en waarvoor het dient.
Dus, in het kort: Een grammatica is een strenge, abstracte weergave van wat wel en niet mag in een programmeertaal? Dan rest mij nog 1 vraag: Als ik een programma schrijf en compile, waar wordt het dan vergeleken met de grammatica? Ik bedoel: Ik neem aan dat source code ergens mee moet worden vergeleken om te zien of deze well-formed is en ik neem ook aan dat dit vergeleken wordt met de grammatica die die taal beschrijft. Heb ik het dan goed als ik het proces zo omschrijf: - Schrijf source code - compiler lexicaliseert (scanned dus de code en creeërt tokens) - compiler bekijkt of de tokens niet clashen met de grammatica voor die taal (checked dus de syntax) - compiler doet de semantieke analyse - compiler gaat de synthese fase en voert de rest uit - compiler spuugt object code uit Zo komt het op mij over. Die laatste paar stappen zijn mij niet bekend en daar doen we op het moment ook niets mee. Die first en follow sets kijk ik later nog wel even naar. Aangezien ik het toch moet programmeren, komt het vast wel weer aan de orde. MAW: We zijn nog niet klaar! btw: De opdracht is nu wat duidelijker... We moeten beginnen met de BNF notatie (die moet je wel kennen, aangezien die heel oud is) te vangen in een grammatica. Ik heb nu het volgende (toegegeven: Ik vond deze toevallig, maar dan in EBNF notatie. Ik heb 'm BNF gemaakt om aan de opdracht te voldoen): Code:
<syntax> ::= <rule> <syntax> <syntax> ::= <rule> <syntax> ::= ε <rule> ::= <identifier> <definedas> <expression> <expression> ::= <term> <expression> ::= <term> <expression> <term> ::= <factor> <term> <term> ::= <factor> <factor> ::= <identifier> <factor> ::= <quoted_symbol> <factor> ::= "(" <expression> ")" <identifier> ::= <letter> <identifier> <identifier> ::= <letter> | <digit> <quoted_symbol> ::= <quoted_symbol> <letter> <quoted_symbol> ::= <letter> <letter> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "10" <definedas> ::= "::=" Dit was trouwens de originele EBNF notatie: Code:
<syntax> ::= { <rule> } <rule> ::= <identifier> "::=" <expression> <expression> ::= <term> { "|" <term> } <term> ::= <factor> { <factor> } <factor> ::= <identifier> | <quoted_symbol> | "(" <expression> ")" | "[" <expression> "]" | "{" <expression> "}" <identifier> ::= <letter> { <letter> | <digit> } <quoted_symbol> ::= """ { <letter> } """ <letter> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "10"
__________________
Bad spelling and grammar make me [sic].
|
18-10-2006, 20:22 | |
Rob,
Het klopt inderdaad "ongeveer". Een paar verschillen: (waarbij ik er even vantui ga dat de accolades betekenen: 0 of meer keer). <quoted_symbol> Volgens de originele grammatica bestaat die uit 0 of meer letters, ingesloten door quotes. Volgens jouw vertaling bestaat die uit 1 of meer letters, zonder quotes. <identifier> Volgens de originele grammatica bestaat die uit een letter, gevolgd door 0 of meer keer een cijfer of een letter. Volgens jouw vertaling bestaat die uit ofwel een letter gevolgd door 0 of meer keer een cijfer of een letter, ofwel uit een enkel cijfer. <factor> Volgens de originele grammatica bestaat die uit ofwel een identifier ofwel een quoted_symbol ofwel een expression tussen haakjes ofwel een expression tussen vierkante haken ofwel een expression tussen accolades. Volgens jouw vertaling bestaat die uit ofwel een identifier ofwel een quoted_symbol ofwel een expression tussen haakjes. <term> OK. <expression> Volgens de originele grammatica bestaat die uit een of meer termen, gescheiden door een verticale streep. Volgens jouw vertaling bestaat die uit een of meer termen. <rule> OK. <syntax> OK. Ik heb even van onder naar boven gewerkt, omdat ik dan de grammatica iets beter begrijp. Je kunt jouw werk (bijvoorbeeld) ook in die volgorde corrigeren. |
18-10-2006, 20:30 | ||
Citaat:
De semantiek speelt hierbij ook nog een rol. Bijvoorbeeld bij een conditional clause staat vaak in de grammatica alleen maar dat de "conditie" een expressie is. Maar in werkelijkheid weet je, dat het resultaat van die expressie gecast moet kunnen worden naar een boolean. --------- In de praktijk zal in de grammatica gekozen zijn voor "betekenisvolle" namen. En daardoor "weet" je na het lezen (of bestuderen) van de grammatica al een heleboel over wat het allemaal betekent. Hierdoor is het ook mogelijk, een grammatica top-down te lezen. Je kunt namelijk uit de gebruikte namen al grotendeels afleiden wat er (waarschijnlijk) verderop in de grammatica zal staan. |
18-10-2006, 20:48 | ||
Citaat:
Semantische checks kun je bijvoorbeeld grotendeels uitvoeren tijdens de syntaxcheck. Soms kan dat pas gedurende runtime - dan moet je dus eigenlijk code meegenereren die die check in runtime uitvoert. Tijdens het checken van de syntax bepaal je eigenlijk al precies welke programmastructuren er gebruikt worden. En die informatie heb je later ook precies nodig voor het maken van het vertaalde programma in de doeltaal. Die stappen kun je dus *ook* combineren. Of je kunt de informatie die uit de syntaxcheck komt wegschrijven als tussenresultaat. In dat geval wil je zo veel mogelijk informatie wegschrijven, dus in feite het volledige programma. In feite vertaal je het programma dan naar een "tussentaal". --- Een voorbeeld van hoe je tijdens een syntaxcheck code genereert, is te vinden in mijn bericht van 18-10-2006 @ 08:15. Daarin staat ook een voorbeeld van hoe je tijdens een syntaxcheck een programma in een tussentaal kunt genereren. --- Het resultaat schrijf je doorgaans niet weg zolang er nog errors voorkomen. Daarom lijkt het voor de programmeur alsof *eerst* de syntax wordt gechecked, en daarna pas code wordt gegenereerd. Maar soms gebeurt dat dus tegelijkertijd. |
Advertentie |
|
|
|
Soortgelijke topics | ||||
Forum | Topic | Reacties | Laatste bericht | |
Games |
daikatana 64 qghp | 18 | 17-08-2003 15:14 | |
Games |
Golden Sun (probleem) Ieke | 13 | 21-08-2002 17:51 | |
Psychologie |
Emotie versus Rede proycon | 5 | 26-03-2002 11:22 | |
Levensbeschouwing & Filosofie |
evolutie mitsj | 96 | 14-03-2002 19:18 | |
Levensbeschouwing & Filosofie |
Intelligent Design legatus | 28 | 08-02-2002 18:34 | |
Verhalen & Gedichten |
The winter.. striking it's first victim Kazanka | 4 | 07-01-2002 17:19 |