First and Follow Sets.

[Rob]

Ik snap er, helaas, heel weinig van.

Het toevoegen van de non-terminals gaat nog, maar daarna snap ik het niet echt meer. Ik moet de first en follow sets van de volgende grammatica bepalen:

G(<forstat>):

<forstat> ::= FOR ( <expr0> ; <expr0> ; <expr0> ) <stat>
<stat> ::= <expr> ; | <forstat> | <ifstat>
<expr0> ::= ε | <expr>
<expr> ::= <expr> + <factor> | <factor>
<factor> ::= IDENTIFIER | ( <expr> )
<ifstat> ::= IF ( <expr> ) <stat> <optional-else>
<optional-else> ::= ε | ELSE <stat>


Op het moment heb ik:
FIRST(<forstat>) = {for}
FIRST(<stat>) = {;}
FIRST(<expr0>) = {ε}
FIRST(<expr>) = {****
FIRST(<factor>) = {identifier}
FIRST(<ifstat>) = {if}
FIRST(<optional-else>) = {ε, else}

Daarna moet ik kijken welke producties met een non-terminal beginnen (stat en expr, dus), maar ik snap niet hoe ik verder moet werken, voornamelijk vanwege de manier waarop stat en expr gedefinieerd zijn (ik vind dan ook geen voorbeelden die wel zo opgebouwd zijn).

Kan iemand dit rustig en stap voor stap uitleggen?

Rob,

Een <expr> begint altijd met een <factor>.
En een <factor> kan beginnen met een IDENTIFIER (wat dan meteen de hele factor is) of met een (.
Dus een <expr> zal uiteindelijk altijd beginnen met een IDENTIFIER of een (.

Voor het statement heb je drie mogelijkheden.
Voor het tweede en derde geval (for statement resp. if statement) zie je vast wel hoe het verder gaat...

Rob,

Misschien toch eerst een beetje uitleg:

<expr> ::= <expr> + <factor> | <factor>

Hier staat in feite:
Een expressie bestaat uit
een factor,
of een factor plus een factor,
of een factor plus een factor plus een factor,
of ...
(Dus in feite een som van een of meer factoren - wat we normaal gesproken overigens "termen" noemen).

<factor> ::= IDENTIFIER | ( <expr> )

Hier staat in feite:
Een factor is
ofwel een identifier,
ofwel een expressie tussen haakjes.
(En we wisten al dat een expressie bestond uit een 'som' van een of meer factoren).

[Rob]

Hey NietVrolijk,

Bedankt, maar het probleem is niet dat ik niet begrijp hoe de grammatica is opgebouwd. Ik snap wel hoe ik bv <expr> ::= <expr> + <factor> | <factor> moet lezen, maar ik snap dus niet echt hoe ik er een first set van moet maken, omdat ik geen voorbeelden kan vinden die first sets opbouwen van zulke grammatica.

Ik vind voornamelijk wat makkelijkere situaties waar helemaal geen or-clause in zit en waar een non-terminal met een non-terminal begint en die non-terminal met een terminal.

De eerste stap is de lijst met symbolen maken (gedaan in mijn eerste post), de tweede alle terminals toevoegen die aan de start van producties staan (ook gedaan).
Daarna moet ik kijken welke terminals beginnen met non-terminals en die toevoegen aan de symbolen die met die non-terminal beginnen.

*jat voorbeeld*

E ::= E + E
E ::= P id
P ::= * P
P ::= ε

First(E) is na stap 2 leeg (begint niet met terminals)
Volgens stap drie van het maken van First sets moet ik First(P id) toevoegen aan First(E) wat E = {*, id} geeft.

Deze stap snap ik niet (en waarom wordt ε weggelaten in E = {*, id}?), en ik begrijp al helemaal niet wat ik moet doen als ze er een or-clause ingooien (zoals in mijn voorbeeld).

Erm, even een klein vraagje:
Stel, ik heb het volgende:

<P> ::= * P
<P> ::= ε

Mag ik dan het volgende zeggen?

<P> ::= * P | ε

Of is dat fout?

Rob,


Het moet voor mij van heel ver weg komen. Het is ongeveer 25 jaar geleden dat ik deze stof geleerd heb (tijdens colleges compilerbouw, meen ik), dus het is behoorlijk ver weggezakt.
Ik kan dus hier en daar de mist ingaan v.w.b. notatie.

Je zegt dat de tweede stap bestaat uit het opnoemen van alle terminals die aan het begin van een productie staan.
Volgens maak je bij die stap wat fouten.

Je schrijft bijvoorbeeld:
FIRST(<expr> ) = {****
Echter, de definitie zegt: <expr> ::= <expr> + <factor> | <factor>
Een expression zal volgens deze grammatica dus altijd met een factor beginnen, en nooit met een +.

-------------------

Laten we even naar je voorbeeld kijken.

P ::= * P
P ::= ε

Indien '*' een terminal is, staat hier in feite:
P bestaat uit 1 of meer '*', gevolgd door niets.
Of korter:
P bestaat uit 1 of meer '*'.

Indien '*' hier iets anders betekent, zul je me eerst even moeten vertellen wat dat is.

---

E ::= E + E
E ::= P id

Dit vind ik niet bepaald een eenvoudig voorbeeld.

Ik kan hiermee bijvoorbeeld het volgende bouwen:
E = E + E = P id + E = P id + E + E = P id + P id + P id.
maar ook:
E = E + E = E + P id = E + E + P id = P id + P id + P id.

Maar als ik nu opschrijf "P id + P id + P id", weet jij niet of ik nu de bovenste of de onderste bedoel.

Dat zou wel onmiddellijk duidelijk zijn als er zou staan:
E ::= E + P id
E ::= P id
Of juist indien er zou staan:
E ::= P id + E
E ::= P id


---

Overigens gebruik je in dit voorbeeld een andere notatie als in je vraag.

In je vraag schrijf je bijvoorbeeld:
<stat> ::= <expr> ; | <forstat> | <ifstat>

In de notatie die je gebruikt bij het voorbeeld zou je dat opschrijven als:
<stat> ::= <expr> ;
<stat> ::= <forstat>
<stat> ::= <ifstat>
Volgens mij kun je die twee notaties niet door elkaar gebruiken.

Rob,


Er zit overigens een storende fout in de opgave.
(Ik had in onderstaand stukje het niet-relevante deel van de grammatica grijs willen maken, maar ik weet niet hoe dat moet. Daarom maak ik in plaats daarvan het wel-relevante deel even bold.)

<forstat> ::= FOR ( <expr0> ; <expr0> ; <expr0> ) <stat>
<stat> ::= <expr> ; | <forstat> | <ifstat>
<expr0> ::= ε | <expr>
<expr> ::= <expr> + <factor> | <factor>
<factor> ::= IDENTIFIER | ( <expr> )
<ifstat> ::= IF ( <expr> ) <stat> <optional-else>
<optional-else> ::= ε | ELSE <stat>

Dat betekent dat ik volgens deze grammatica het volgende mag schrijven:
IF (gevonden) IF (groot) doe_iets ; ELSE doe_iets_anders ;
In dat geval zijn er wederom twee manieren waarop ik dit geproduceerd kan hebben.
In het ene geval betekent het, dat 'doe_iets_anders' moet worden uitgevoerd indien 'gevonden AND NOT groot', in het andere geval betekent het dat 'doe_iets_anders' moet worden uitgevoerd indien NOT groot.
Binnen bedrijven is het veelal verboden om geneste IFs te gebruiken.
Het gebruik van geneste IFs in de THEN-tak leidt altijd tot misverstanden en mag dus eigenlijk nooit - maar dat wist je vermoedelijk al.

Rob,


Je schrijft:
"De eerste stap is de lijst met symbolen maken (gedaan in mijn eerste post), de tweede alle terminals toevoegen die aan de start van producties staan (ook gedaan).
Daarna moet ik kijken welke terminals beginnen met non-terminals en die toevoegen aan de symbolen die met die non-terminal beginnen."

Dit begrijp ik niet helemaal.
Ik zal er voorlopig even vanuit gaan dat je bedoelt:
"Daarna moet ik kijken welke met welke terminals de non-terminals en die toevoegen aan de eerder gemaakte lijst."

Als je bij stap twee een nieuwe lijst maakt en daar het resultaat aan toevoegt, krijg je aan lijst met alle symbolen waarmee je kunt beginnen.
Ik zal maar even aannemen dat dat de bedoeling is.
Een compiler (of interpreter of parser) zal op zo'n moment willen weten vanuit welke productieregel het terminaal symbool geproduceerd is. (Een menselijke lezer doet dat in wezen ook, maar dan op een iets hoger niveau.)

Ik krijg na de tweede stap:
FIRST(<forstat> ) = {FOR}
FIRST(<stat> ) = ...
FIRST(<expr0> ) = {ε}
FIRST(<expr> ) = ...
FIRST(<factor> ) = {identifier}
FIRST(<ifstat> ) = {if}
FIRST(<optional-else> ) = {ε, ELSE}
Hierbij zou ik op een of andere manier het volgende willen onthouden:
<stat> begint met een <expr> of met een <forstat> of met een <ifstat>
<expr0> kan ook nog beginnen met een <expr>
<expr> begint met een <factor>

Voor de derde stap levert dat volgens mij in een eerste iteratie:
FIRST(<forstat> ) = {FOR}
FIRST(<stat> ) = {FOR, IF}
FIRST(<expr0> ) = {ε}
FIRST(<expr> ) = {identifier}
FIRST(<factor> ) = {identifier}
FIRST(<ifstat> ) = {IF}
FIRST(<optional-else> ) = {ε, ELSE}
<stat> kan ook nog beginnen met een <expr>
<expr0> kan ook nog beginnen met een <expr>
Ik heb namelijk in de eerste iteratie al gezien dat een factor altijd met een identifier begint.

In de tweede iteratie kun je dan het lijstje afmaken voor <stat> en <expr0>.

Rob,


Ik zie nu dat ik misschien wel een beetje teveel heb voorgezegd.

Maar er blijft nog voldoende werk over:
- Je moet de tweede iteratieslag nog uitvoeren.
- Je moet nog aantonen dat een expression inderdaad altijd met een factor begint.
- En je moet het geheel nog vertalen naar een notatie die bij jullie geaccepteerd wordt.

Wellicht kun je nog bonuspunten krijgen als je de fout in de opgave kunt aantonen. Waarschijnlijk moet je dan wel twee syntax-boompjes tekenen waarmee je aantoont dat je op twee totaal verschillende manieren tot dezelfde programmatekst kunt komen.

Rob,


Ik geloof dat ik nu begin te begrijpen wat een first set is.

Dus nu kunnen we terug naar jouw voorbeeld.

"E ::= E + E
E ::= P id
P ::= * P
P ::= ε

First(E) is na stap 2 leeg (begint niet met terminals)
Volgens stap drie van het maken van First sets moet ik First(P id) toevoegen aan First(E) wat E = {*, id} geeft.

Deze stap snap ik niet (en waarom wordt ε weggelaten in E = {*, id}?), en ik begrijp al helemaal niet wat ik moet doen als ze er een or-clause ingooien (zoals in mijn voorbeeld)."

In stap 2 vind je:
P = {*, ε}
Dus P kan beginnen met een *, of anders bestaat P uit niets (want ε was immers een lege string).

E begint altijd met een <P>, gevolgd door een id.
Als P begint met een *, dan begint E dus (in dit geval) ook met een ster.
Bestaat P uit niets (ε), dan begint E (in dit geval) dus met id.
En daarom is First(E) = {*, id}.

Rob,


Je vroeg:
"Stel, ik heb het volgende:

<P> ::= * P
<P> ::= ε

Mag ik dan het volgende zeggen?

<P> ::= * P | ε

Of is dat fout?"


Volgens mij kan dat wel. Waarschijnlijk moet je in die notatie dan wel < en > om die P heen zetten.
Dat wordt dan:
<P> ::= * <P> | ε

[Rob]

Even antwoorden. Sorry dat het zo lang duurde.

Het moet voor mij van heel ver weg komen. Het is ongeveer 25 jaar geleden dat ik deze stof geleerd heb (tijdens colleges compilerbouw, meen ik), dus het is behoorlijk ver weggezakt.
Ik kan dus hier en daar de mist ingaan v.w.b. notatie.

Ach, dat geeft niet, ik ben al blij dat er iemand is die reageert!

Je zegt dat de tweede stap bestaat uit het opnoemen van alle terminals die aan het begin van een productie staan.
Volgens maak je bij die stap wat fouten.

Je schrijft bijvoorbeeld:
FIRST(<expr> ) = {****
Echter, de definitie zegt: <expr> ::= <expr> + <factor> | <factor>
Een expression zal volgens deze grammatica dus altijd met een factor beginnen, en nooit met een +.

Ja, nu je het zegt. Mijn fout. Dankje voor het vertellen.

Indien '*' een terminal is, staat hier in feite:
P bestaat uit 1 of meer '*', gevolgd door niets.
Of korter:
P bestaat uit 1 of meer '*'.

Indien '*' hier iets anders betekent, zul je me eerst even moeten vertellen wat dat is.

Ik weet niet wat * is. Dat voorbeeld vond ik in een PDF file die het beter wist uit te leggen van de spullen van mijn docent.
Maar ik gok een terminal.

Overigens gebruik je in dit voorbeeld een andere notatie als in je vraag.

Ik heb het voorbeeld dan ook niet verzonnen. Het origineel staat hier: http://www.cs.uiuc.edu/class/fa05/cs...llow%20sets%22

Er zit overigens een storende fout in de opgave.
(Ik had in onderstaand stukje het niet-relevante deel van de grammatica grijs willen maken, maar ik weet niet hoe dat moet. Daarom maak ik in plaats daarvan het wel-relevante deel even bold.)

[...]

Binnen bedrijven is het veelal verboden om geneste IFs te gebruiken.
Het gebruik van geneste IFs in de THEN-tak leidt altijd tot misverstanden en mag dus eigenlijk nooit - maar dat wist je vermoedelijk al.

Ja, die opgave is expres fout, in de zin van: Hij's niet LL(1). We moeten dus eerst bepalen waarom die niet LL(1) is mbf First en Follow Sets. Dan herschrijven tot die LL(1) is, dan in EBNF herschrijven en dan de syntaxdiagrammen schrijven.

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.

Als je bij stap twee een nieuwe lijst maakt en daar het resultaat aan toevoegt, krijg je aan lijst met alle symbolen waarmee je kunt beginnen.
Ik zal maar even aannemen dat dat de bedoeling is.
Een compiler (of interpreter of parser) zal op zo'n moment willen weten vanuit welke productieregel het terminaal symbool geproduceerd is. (Een menselijke lezer doet dat in wezen ook, maar dan op een iets hoger niveau.)

Dat is, inderdaad, de bedoeling van First sets.
Even bewust je iteratie overslaan, daar kom ik zo wel tot.

Ik zie nu dat ik misschien wel een beetje teveel heb voorgezegd.

Maar er blijft nog voldoende werk over:
- Je moet de tweede iteratieslag nog uitvoeren.
- Je moet nog aantonen dat een expression inderdaad altijd met een factor begint.
- En je moet het geheel nog vertalen naar een notatie die bij jullie geaccepteerd wordt.

1. Klopt.
2. Staat niet in de opgave, maar moet misschien wel... Weet ik eigenlijk niet.
3. Ja, maar dat zei ik hierboven al.

In stap 2 vind je:
P = {*, ε}
Dus P kan beginnen met een *, of anders bestaat P uit niets (want ε was immers een lege string).

E begint altijd met een <P>, gevolgd door een id.
Als P begint met een *, dan begint E dus (in dit geval) ook met een ster.
Bestaat P uit niets (ε ), dan begint E (in dit geval) dus met id.
En daarom is First(E) = {*, id}

Ooooh. Ik kon dat verband al niet echt leggen, maar het begint nu wel duidelijk te worden hoe het zit, ja. Nu moet het toch niet meer zo moeilijk zijn.

Volgens mij kan dat wel. Waarschijnlijk moet je in die notatie dan wel < en > om die P heen zetten.
Dat wordt dan:
<P> ::= * <P> | ε

Ja, okay. Maar ik ging even door met dat voorbeeld.
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?

Ik krijg na de tweede stap:
FIRST(<forstat> ) = {FOR}
FIRST(<stat> ) = ...
FIRST(<expr0> ) = {ε}
FIRST(<expr> ) = ...
FIRST(<factor> ) = {identifier}
FIRST(<ifstat> ) = {if}
FIRST(<optional-else> ) = {ε, ELSE}
Hierbij zou ik op een of andere manier het volgende willen onthouden:
<stat> begint met een <expr> of met een <forstat> of met een <ifstat>
<expr0> kan ook nog beginnen met een <expr>
<expr> begint met een <factor>

Voor de derde stap levert dat volgens mij in een eerste iteratie:
FIRST(<forstat> ) = {FOR}
FIRST(<stat> ) = {FOR, IF}
FIRST(<expr0> ) = {ε}
FIRST(<expr> ) = {identifier}
FIRST(<factor> ) = {identifier}
FIRST(<ifstat> ) = {IF}
FIRST(<optional-else> ) = {ε, ELSE}
<stat> kan ook nog beginnen met een <expr>
<expr0> kan ook nog beginnen met een <expr>
Ik heb namelijk in de eerste iteratie al gezien dat een factor altijd met een identifier begint.

Moet FIRST(<expr0>) dan niet = {ε, identifier} worden? Je zegt dat een <expr0> kan beginnen met een <expr> en dat die begint met een <factor> en een <factor> begint met een identifier.
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?).

Om even met dat laatste te beginnen:
FI wordt in sommige programmeertalen (bijvoorbeeld Algol 68) gebruikt om het einde van een IF clause aan te geven.
Bij andere talen wordt bijvoorbeeld END_IF gebruikt, of iets in die geest.

Rob,

Je schrijft:
"We zijn wat vergeten. <factor> Kan met een IDENTIFIER beginnen, maar ook met (. "

Klopt.
Had ik over het hoofd gezien.

Overigens,

Nu we First (<factor>) hebben gecorrigeert, kloppen een aantal andere regels ook niet meer.
Er was namelijk ook een non-termnal die met <factor> kon beginnen.

En als je die hebt verbetert, klopt nog steeds niet alles.

---

Wellicht is het een goed idee, om de stappen nog eens vanaf het begin over te doen (zal inmiddels een heel stuk sneller gaan, en is toch weer een goede oefening).

---

Zou je even kunnen aangeven, wat de stappen zijn voor het maken van de follower sets?
Dan kan ik nog even lekker mee rekenen.

Rob,


Je vroeg:
"<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?"


Persoonlijk vind ik die eerste notatie duidelijker.
Je ziet dan tenminste meteen, dat er drie verschillende invullingen zijn.


Je kunt het best gewoon de notatie gebruiken die bij jullie op de opleiding gebruikt wordt.
Als je dan een pdf van elders raadpleegt, zul je er rekening mee moeten houden, dat er daar wellicht een andere notatie gebruikt wordt.

Zulke zaken zul je later in de praktijk vaak genoeg tegenkomen.
In elk bedrijf zijn er weer andere standaarden waaraan een programma moet voldoen, in elk bedrijf gelden weer andere richtlijnen voor de op te leveren documentatie, in elk bedrijf zijn er weer andere regels voor het goed laten keuren van een functioneel ontwerp, in elk bedrijf zul je weer om moeten schakelen naar de daar gebruikte unix-variant, in elk bedrijf zul je je programmatuur weer met een andere tool moeten maken, in vrijwel elk bedrijf zul je weer opnieuw merken dat Word zich opeens heel anders gedraagt dan in alle voorgaande bedrijven waar je een klus hebt gehad, in elk bedrijf werkt de email weer een beetje anders, bij elk bedrijf moet je je uren weer net iets anders declareren, etc.

Denk nog maar eens terug aan de moeite die je moest doen om je eerste programmeertaal te leren.
En hoeveel makkelijker de tweede was (zelfs als het een heel ander soort was).
En hoe je vanaf de derde of vierde taal elke nieuwe taal zonder problemen kon opnemen.

Rob,


Over die geneste IFs:


Zolang je enkel in de ELSE-tak nest, is er eigenlijk geen probleem.
Het is dan op elk moment duidelijk, op basis van welke conditie er nu onderscheid wordt gemaakt.
Je hebt dan in feite een soort "cascade", of een soort case-clause of zo.
Er zijn daarbij maar twee probleempjes:
1. Op het eind moet je het juiste aantal conditional clauses aflsuiten. Was vroeger een probleem (wij moesten elk programma bij de tweede poging clean-compiled krijgen), maar tegenwoordig gaat het allemaal zo snel dat je de compiler gewoon kunt gebruiken om het juiste aantal END-IF's te bepalen.
2. Als je (zoals de meeste mensen) een codeerstijl hebt waarbij je inspringt, kom je na 3 of 4 geneste IFs al snel ruimte te kort.


Als je nest in de THEN-tak, wordt het vanaf dat moment bij *elke* ELSE lastig om te begrijpen bij welke voorwaarde die ELSE hoorde.
In principe kun je dat bepalen door terug te tellen, maar dat wil je niet continu blijven doen, anders kom je tijd te kort om die expressie nog te kunnen begrijpen.


Als je nest in zowel de THEN tak als in de ELSE tak, heb je vrijwel onmiddellijk spaghetti.


Bedenk, dat het niet voldoende is dat jezelf begrijpt wat je hebt opgeschreven;
Daarnaast moet:
- de persoon die de testsets en de uitkomstvoorspellingen schrijft het begrijpen
- de compiler het begrijpen
- de persoon die jouw code reviewt het begrijpen
- de persoon-die-defects-onderzoekt-die-wellicht-in-de-buurt-van-jouw-programma-zijn-ontstaan het begrijpen
- de persoon die checkt of jouw code de bedrijfsstandaarden volgt, het begrijpen
- jijzelf het drie maanden later nog begrijpen als je een wijziging op de software moet aanbrengen
- de persoon die een jaar later (als iedereen van jouw bedrijf 100km verderop bij een andere klant zit) de software moet onderhouden, het begrijpen.

Indien een van deze personen de code niet snapt (of niet zeker weet of de werking van deze code precies overeenkomt met de werking die in de documentatie staat), zal jouw expressie zonder meer geschrapt worden en vervangen door beter onderhoudbare code.

---

Of anders gesteld:
Wat zou je liever opschrijven tijdens een tentamen:
- een stuk code waarvan de docent onmiddellijk ziet dat de code correct is?
- of een ingenieus stuk code waar de docent eerst 15 minuten op moet zwoegen, voordat hij mag bedenken hoeveel punten hij jou geeft voor die opgave?

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.)

[Rob]

NietVrolijk schreef op 04-10-2006 @ 20:40 :
Om even met dat laatste te beginnen:
FI wordt in sommige programmeertalen (bijvoorbeeld Algol 68) gebruikt om het einde van een IF clause aan te geven.
Bij andere talen wordt bijvoorbeeld END_IF gebruikt, of iets in die geest.

Dus toch. Handig dat ze dat erbij zetten, zeg.

Overigens,

Nu we First (<factor> ) hebben gecorrigeert, kloppen een aantal andere regels ook niet meer.
Er was namelijk ook een non-termnal die met <factor> kon beginnen.

En als je die hebt verbetert, klopt nog steeds niet alles.

---

Wellicht is het een goed idee, om de stappen nog eens vanaf het begin over te doen (zal inmiddels een heel stuk sneller gaan, en is toch weer een goede oefening).

---

Zou je even kunnen aangeven, wat de stappen zijn voor het maken van de follower sets?
Dan kan ik nog even lekker mee rekenen.

Goed punt. Zometeen even doen.

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}

Persoonlijk vind ik die eerste notatie duidelijker.
Je ziet dan tenminste meteen, dat er drie verschillende invullingen zijn.


Je kunt het best gewoon de notatie gebruiken die bij jullie op de opleiding gebruikt wordt.
Als je dan een pdf van elders raadpleegt, zul je er rekening mee moeten houden, dat er daar wellicht een andere notatie gebruikt wordt.

Ja, die eerste is wel makkelijker, dat ben ik met je eens. Maar ik vind dat verwarrend met die sets bepalen.
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!

[Rob]

Okay, dat ging een stuk sneller. Volgens mij is dit ook vollediger:

FIRST(<forstat>) = {FOR}
FIRST(<stat>) = {FOR, IF, IDENTIFIER, (}
FIRST(<expr0>) = {ε, IDENTIFIER, (}
FIRST(<expr>) = {IDENTIFIER, (}
FIRST(<factor>) = {IDENTIFIER, (}
FIRST(<ifstat>) = {IF}
FIRST(<optional-else>) = {ε, ELSE}

Rob,


Je schreef:
"Dus toch. Handig dat ze dat erbij zetten, zeg."


Probleem is waarschijnlijk, dat dat voor mensen die die taal kennen voor de hand lijkt te liggen.


In Algol 68 begon en eindigde:
- een conditional clause met IF resp. FI
- een loop met DO resp. OD met eventueel een conditie er voor of na, uiteraard
- een gevalsonderscheiding met CASE resp. ESAC

Alleen tegenover de BEGIN stond om een of andere reden geen NIGEB, maar END.

Rob,


Ik denk dat je first sets nu correct zijn.

Volgens mij heb ik zojuist in die pdf gelezen, dat je die first sets nodig hebt bij het bepalen van de follow sets.
Dus de follow sets moet je nu eigenlijk ook opnieuw bepalen ...

[Rob]

Iemand heeft ooit tegen mij gezegd dat die dingen als FI en ESAC vooral gebruikt werden in pseudo-code. Ik wist niet dat het uit ALGOL 68 stamde.

Daar was ik ook mee bezig. Het gaat sowieso al een heel stuk sneller om the Follower sets te bepalen. Waar ik alleen op vastloop, zijn de Followers voor <FORSTAT> en <IFSTAT>. Zijn de ( symbolen in die twee non-terminals nou Followers of niet?
En de nonterminals die met een Terminal beginnen en daarna een non-terminal hebben.

Ik heb dus:
<optional-else> ::= ε
<optional-else> ::= ELSE <stat>

Zijn de waarden in First(<stat>) nou deel van waarden in Follow(<optional-else>)?

En dit zijn volgens mij de Follow sets:

FOLLOW(<forstat>) = {(, ε, FOR, IF, IDENTIFIER, $}
FOLLOW(<stat>) = {+, (, ;, ε, ELSE, )}
FOLLOW(<expr0>) = {+, ;, ), IDENTIFIER, (}
FOLLOW(<expr>) = {+, ;, ), IDENTIFIER, (}
FOLLOW(<factor>) = {+, ;, ), IDENTIFIER, (}
FOLLOW(<ifstat>) = {IDENTIFIER, FOR, IF, IDENTIFIER, ε, ELSE, (}
FOLLOW(<optional-else>) = {FOR, IF, IDENTIFIER, (}

Hier ben ik niet helemaal zeker over, trouwens.

Rob schreef op 04-10-2006 @ 22:44 :
Waar ik alleen op vastloop, zijn de Followers voor <FORSTAT> en <IFSTAT>. Zijn de ( symbolen in die twee non-terminals nou Followers of niet?

In <forstat> komt ( alleen maar voor na FOR. En FOR is geen non-terminal. Dus je mag regel 2 van het algoritme hier niet toepassen. Overigens: Als je die regel zou mogen toepassen, zou je ( moeten toevoegen aan Follow (FOR), niet aan Follow (<forstat>).
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).

Rob schreef op 04-10-2006 @ 22:44 :
En de nonterminals die met een Terminal beginnen en daarna een non-terminal hebben.

Ik heb dus:
<optional-else> ::= ε
<optional-else> ::= ELSE <stat>

Zijn de waarden in First(<stat>) nou deel van waarden in Follow(<optional-else>)?

Wederom: ELSE is geen non-terminal, dus je mag die regel hier niet toepassen.

Rob schreef op 04-10-2006 @ 22:44 :
Iemand heeft ooit tegen mij gezegd dat die dingen als FI en ESAC vooral gebruikt werden in pseudo-code. Ik wist niet dat het uit ALGOL 68 stamde.

Toen ik tijdens een COBOL-opleiding eens een stuk code in Algol 68 opschreef, waren mijn mede-cursisten er van overtuigd dat het pseudo-code was.

Het zag er zo leesbaar uit, zo leesbaar kon een echte programmeertaal toch niet zijn?

Rob schreef op 04-10-2006 @ 22:44 :
En dit zijn volgens mij de Follow sets:

FOLLOW(<forstat>) = {(, ε, FOR, IF, IDENTIFIER, $}
...

Kan volgens mij niet kloppen.

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...

[Rob]

NietVrolijk schreef op 04-10-2006 @ 23:26 :
In <forstat> komt ( alleen maar voor na FOR. En FOR is geen non-terminal. Dus je mag regel 2 van het algoritme hier niet toepassen. Overigens: Als je die regel zou mogen toepassen, zou je ( moeten toevoegen aan Follow (FOR), niet aan Follow (<forstat>).
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).

Maar wat moet ik dan met die ( doen? Dat deel ontgaat mij, eerlijk gezegd.
En ik neem aan dat de follow-sets alleen voor non-terminals gebouwd worden. Ik wist iig niet dat het ook voor terminals kon.

NietVrolijk schreef op 04-10-2006 @ 23:26 :
Wederom: ELSE is geen non-terminal, dus je mag die regel hier niet toepassen.

Wederom: Wat doe ik met die (? :p Of kijk ik iets over het hoofd en staat de ( in the FIRST sets al goed?

NietVrolijk schreef op 04-10-2006 @ 23:26 :
Toen ik tijdens een COBOL-opleiding eens een stuk code in Algol 68 opschreef, waren mijn mede-cursisten er van overtuigd dat het pseudo-code was.

Het zag er zo leesbaar uit, zo leesbaar kon een echte programmeertaal toch niet zijn?

Haha. :D Dan zag die jongen vast ook ALGOL 68. Wie weet. Wel handig, eigenlijk.

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.

Definitie: Followers(<a>) is set van alle terminalen die direct achter de nonterminaal <a> kunnen komen. “$” geeft het einde van het te parsen stuk code aan.
$ komt in Followers(<startsymbool>)
<a> ::= <x>y --> Followers(<x>) bevat y
<a> ::= <x><y><z> --> Followers(<z>) bevat Followers(<a>)
<a> ::= <x><y><z> -->; Followers(<y>) bevat Starters(<z>) muv ε
<a> ::= <x><y><z>, met Starters(<z>) bevat ε --> Followers(<y>) bevat Followers(<a>)
<a> ::= <x><y><z>, met Starters(<y>) bevat ε --> Followers(<x>) bevat Starters(<z>)

Da's eerlijk gezegd een stuk duidelijker dan dat PDF filetje. Even kijken ofik dat toe kan passen.

[Rob]

Helaas lukt het alleen niet echt. Ze gebruiken in de regels dingen die ik om de een of andere reden niet echt toe kan passen op mijn opgave, of er mee kan vergelijken.

<a> ::= <x><y><z> bijvoorbeeld. Ik heb nergens iets wat er op lijkt, dus hoe en waar moet ik 'em dan toepassen?

edit: Geniale naamwijziging. Het is wel leuk om mee te rommelen, maar je moet er wel uit kunnen komen. En dat lukt mij helaas nog niet.

Rob schreef op 05-10-2006 @ 00:11 :
<a> ::= <x><y><z> bijvoorbeeld. Ik heb nergens iets wat er op lijkt, dus hoe en waar moet ik 'em dan toepassen?

<a> ::= <x><y><z> zou je kunnen toepassen op:
<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.

[Rob]

WelVrolijk schreef op 05-10-2006 @ 00:38 :
<a> ::= <x><y><z> zou je kunnen toepassen op:
<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.

Ik snap dus nog niet echt hoe ik iets als <a> ::= <x><y><z> toe kan passen op een non-terminal die er zo uitziet: <a> ::= if( <x> ) <y> <z>
of op een non-terminal die er zo uitziet: <a> ::= <y> + <z> of op <a> ::= ELSE <x>.

WelVrolijk schreef op 05-10-2006 @ 00:38 :
De eerste zegt iets over Followers(<z>). Dat vertelt ons dus iets over Followers (<stat>) en Followers (<factor>) en Followers (<optional-else>)

Okay... Even kijken. Followers(<z>) bevat Followers(<a>). Dus, Followers(<stat>) bevat Followers(<forstat>), Followers(<factor>) bevat Followers(<expr>) en Followers(<optional-else>) bevat Followers(<ifstat>).

WelVrolijk schreef op 05-10-2006 @ 00:38 :
De tweede regel vertelt ons iets over Followers(<y>).
In ons geval dus Followers (<expr0>), Followers (<expr0>), Followers(<expr>), Followers(<expr>) en Followers (<stat>).

Followers(<y>) bevat Starters(<z>). Dus, Followers(<expr0>) bevat Starters(<stat>), Followers(<expr>) bevat Starters(<factor>) en Followers(<stat>) bevat Starters(<optional-else>).

WelVrolijk schreef op 05-10-2006 @ 00:38 :
De derde regel vertelt ons iets over Followers(<y>) maar alleen als ε in First(<z>) zit.
In ons geval dus alleen Followers(<stat>).

Stimmt. Followers(<stat>) bevat dus ook nog eens Followers(<ifstat>), als ik het goed heb.

WelVrolijk schreef op 05-10-2006 @ 00:38 :
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.

Hm, okay. Even toepassen...

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?

Rob schreef op 05-10-2006 @ 01:05 :
Ik snap dus nog niet echt hoe ik iets als <a> ::= <x><y><z> toe kan passen op een non-terminal die er zo uitziet: <a> ::= if( <x> ) <y> <z>
of op een non-terminal die er zo uitziet: <a> ::= <y> + <z> of op <a> ::= ELSE <x>.

Ik denk dat je "jullie" regels wat generieker moet toepassen.

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.

Rob schreef op 05-10-2006 @ 01:05 :
Hm, okay. Even toepassen...

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>) = {}

Dat ziet er al een stuk beter uit.
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!

Rob schreef op 05-10-2006 @ 01:05 :
<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>?

Laten we eens kijken naar <optional-else> ::= ε | ELSE <stat>.

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 ...

[Rob]

WelVrolijk schreef op 05-10-2006 @ 08:30 :
Ik denk dat je "jullie" regels wat generieker moet toepassen.

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.

Heh, daar ben ik héél slecht in. Ik denk altijd dat ik het fout doe zonder concrete voorbeelden.

WelVrolijk schreef op 05-10-2006 @ 08:30 :
Dat ziet er al een stuk beter uit.
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!

Ik weet niet of dat niet mag. Ik heb gewoon dat algoritme gevolgd.

WelVrolijk schreef op 05-10-2006 @ 08:30 :
Laten we eens kijken naar <optional-else> ::= ε | ELSE <stat>.

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 ...

Waarom denk ik daar zelf niet aan? Ik vind dit, eerlijk gezegd, wel lastig voor een opdracht waar we nog niet eens mee geoefend hebben en waar we maar een of twee voorbeelden van hebben gehad. =\


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!

[WelVrolijk]

Rob schreef op 05-10-2006 @ 12:45 :
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 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>) = {$}

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, (}).

Daar gaat het mis.

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.

[WelVrolijk]

Rob,


Het is overigens geen toeval dat we regel 2 en regel 4 steeds door elkaar gooien.

Beide regels zeggen in wezen hetzelfde.

Het belangrijkste is, dat je leert die situaties te herkennen.
Het gaat dus steeds om een non-terminal die niet aan het eind van een productieregel staat.
Door deze regel(s) kun je dan alles uit de First van "alles wat er achter staat" toevoegen (maar nooit de epsilon).


Regel 3 en regel 5 zijn ook verwant.

Bij regel 3 gaat het om een non-terminal die aan het eind van een productieregel staat.
Bij regel 5 gaat het om een non-terminal, waarvoor "alles wat er achterstaat" zou kunnen neerkomen op een lege string.
Door deze regel(s) kun je dan alles uit de Follower van "de non-terminal waar deze productieregel voor bedoeld is" toevoegen.

[Rob]

Hey. =)

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").

Ah. Ik dacht dat ik die ; en de ) juist niet toe mocht voegen omdat het geen non-terminals maar terminals waren.
Daarom snapte ik ook niet echt wat ik met dat soort statements aanmoest.

Ik werk morgen het resultaat wel uit en post dan wel weer. Nu hopen dat ik kan slapen. Ik reageer later dan ook wel op de rest.

[Rob]

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!).

[Sortjuh]

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?

[WelVrolijk]

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.

[Sortjuh]

Oh, wacht even. =x

Van deze grammatica is direct te bepalen dat de LL(1) eigenschap niet geldt, omdat <expr> links recursief is. De nonterminal <expr> beschrijft structuren die bestaan uit één <factor> gevolgd door nul of meer +<factor>. Dit kan in BNF ook worden beschreven met

<expr> ::= <factor> <expr-tail>
<expr-tail> ::= ε | + <factor> <expr-tail>

Maar dan nog: Er stond niet in dat je iets moest herschijven om de sets te bepalen.

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.

[WelVrolijk]

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.

[WelVrolijk]

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).

[Rob]

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.

[WelVrolijk]

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.

[WelVrolijk]

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.

[WelVrolijk]

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).

[Rob]

WelVrolijk schreef op 17-10-2006 @ 21: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.

Een LL(1) grammatica is een grammatica die aan de eisen van LL(1)-heid voldoet.
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.

WelVrolijk schreef op 17-10-2006 @ 21:25 :
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.

Ja, over die typen hebben we het al gehad, een beetje. Dan krijg je dingen zoals eindige automata, correct?

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?

[WelVrolijk]

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).

[WelVrolijk]

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).

[Rob]

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):

<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>     ::=  "::="

Zoals je ziet zijn de nonterminals de woorden omgeven door vishaken en letterlijke strings gequote en gebold om het overzichtelijk te houden.
Dit was trouwens de originele EBNF notatie:

<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"

Klopt dit ongeveer? Ik mag ervan uitgaan dat de EBNF notatie correct is, maar ik ben geen ster in nieuwe dingen vertalen.

[WelVrolijk]

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.

[WelVrolijk]

Rob schreef op 18-10-2006 @ 12:33 :
JDus, in het kort: Een grammatica is een strenge, abstracte weergave van wat wel en niet mag in een programmeertaal?

Niet precies.

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.

[WelVrolijk]

Rob schreef op 18-10-2006 @ 12:33 :
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.

Doorgaans worden de stappen iets meer gecombineerd.

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.