First and Follow Sets.

[Rob]

Okay, bedankt voor je feedback!

Hier is mijn nieuwe BNF grammatica (btw, je had gelijk: iets tussen accolades is gelijk aan 0 of meer keer. Iets tussen blokhaken is optioneel)

<syntax>        ::=  <rule> <syntax>
<syntax>        ::=  <rule>
<syntax>        ::=  ε
<rule>          ::=  <identifier>  <definedas>  <expression>
<expression>    ::=  <term> "|" <expression>
<expression>    ::=  <term>
<term>          ::=  <factor> <term>
<term>          ::=  <factor>
<factor>        ::=  <identifier>
<factor>        ::=  <quoted_symbol>
<factor>        ::=  "("  <expression>  ")"
<identifier>    ::=  <letter>
<identifier>    ::=  <identifier> <optionalchar>
<optionalchar>  ::=  <letter> <optionalchar>
<optionalchar>  ::=  <digit> <optionalchar>
<optionalchar>  ::=  ε
<quoted_symbol> ::=  """ <letter> <quoted_symbol> """
<quoted_symbol> ::=  """ <letter> """
<quoted_symbol> ::=  ε
<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>     ::=  "::="

Merk op dat ik factor zo gehouden heb. De {} en [] worden alleen in EBNF notaties gebruikt en de onze moet BNF zijn. Vandaar het weglaten.
Volgens mij klopt ie zo wel wat meer, maar ik ben niet zeker over <identifier>. Dat gedoe met optionele characters is vervelend.

En de andere dingen zag ik gewoon over het hoofd.

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.

Okay... dus een grammatica geeft abstract weer wat op het gebied van de syntax geldig en niet geldig is?

Ja, dat van die fasen in de compiler staat in mijn boek(en) ook. Dat samenvoege ook.
Maar nou weet ik eigenlijk nog steeds niet waar de compiler gebruik maakt van de grammatica (als ie dat überhaupt doet).

Ergens is het wel leuk hoe dit werkt, maar het is zoveel voor een vak van drie weken.

[WelVrolijk]

Rob,


Je bent al een heel eind in de goede richting.
Toch zie ik nog twee probleempjes:

---

<optionalchar>

Dit is volgens jouw grammatica een serie van 0 of meer chars (waarbij een char een cijfer of een letter is).
Die naamgeving vind ik een beetje misleidend.

Als je zou schrijven:
<optionalchar> ::= <letter>
<optionalchar> ::= <digit>
<optionalchar> ::= ε
dan zou de naam niet langer misleidend zijn.
En samen met jouw productieregels voor <identifier> heb je dan nog steeds een kloppende set productieregels voor <identifier>

Echter: Er zijn dan een heleboel manieren om de identifier ab te produceren:
1. ab is een identifier, want a is een identifier (want a is een letter) en b is een optionalchar (want b is een letter)
2. ab = aεb is een identifier, want aε is een identifier en b is een optionalchar
3. ab = abε is een identifier, want ab is een identifier en ε is een optionalchar
4. ...

Er moet dus een elegantere oplossing bestaan...

(Hint: denk nog eens aan die expression-tail. Zoiets kan je hier ook gebruiken...)

---

<quoted_symbol>

Volgens jouw productieregels bestaat die uit:
- hetzij 1 of meer letters, omsloten door quotes
- hetzij niets.

Dat klinkt niet helemaal goed.
Ik zou verwachten:
- 1 of meer letters, omsloten door quotes
Of wellicht:
- 0 of meer letters, omsloten door quotes

[WelVrolijk]

Rob schreef op 18-10-2006 @ 22:28 :
Okay... dus een grammatica geeft abstract weer wat op het gebied van de syntax geldig en niet geldig is?

Nee.

De grammatica *is* de syntax.

Maar behalve de syntax zijn er nog wat regels waaraan je programma moet voldoen.

[WelVrolijk]

Rob schreef op 18-10-2006 @ 22:28 :
Ja, dat van die fasen in de compiler staat in mijn boek(en) ook. Dat samenvoege ook.
Maar nou weet ik eigenlijk nog steeds niet waar de compiler gebruik maakt van de grammatica (als ie dat überhaupt doet).

Ergens is het wel leuk hoe dit werkt, maar het is zoveel voor een vak van drie weken.

Pfff!!!

Compilerbouw in 3 weken?
Dat is wel *heel* intensief.

-----

Een compiler is een computerprogramma.

Je schrijft zo'n compiler voor een bepaalde taal
doorgaans aan de hand van de grammatica van die taal.

Daarvoor moet die grammatica aan bepaalde voorwaarden voldoen. Zo niet, dan pas je de grammatica zo aan dat hij *wel* aan die voorwaarden voldoet, en toch nog exact de taal beschrijft.

De compiler bestaat uit een set procedures, die elkaar aanroepen.
In principe schrijf je *een* procedure voor *elke* productieregel.

---

Bijvoorbeeld voor een conditional clause van de vorm
<ifstat> ::= IF ( <expr> ) <stat> <optional-else> FI
<optional-else> ::= ε | ELSE <stat>

1. Lees de IF en het (.
2. Roep de procedure aan die de <expr> verwerkt. Deze genereert code voor die expressie, die (straks tijdens runtime) een resultaat oplevert (de conditie).
3. Genereer alvast namen voor 2 labels (zeg L1 en L2).
4. Genereer code die naar L1 springt indien het resultaat (uit stap 2) FALSE was.
5. Roep de procedure aan die de <stat> verwerkt. Deze genereert code voor het THEN-part.
6. Genereer code die naar L2 springt.
7. Genereer code voor label L1.
8. Roep de procedure aan die de <optional-else> verwerkt. Deze genereert code voor het ELSE-part.
9. Genereer code voor label L2.
10. Lees de FI.

Nu heb je routine geschreven die een correcte conditional clause kan verwerken (tenminste, als de procedures voor <expr>, <stat> en <optional-else> al geschreven zijn).

---

Als je dat nou doet voor *alle* productieregels, dan heb je (in principe) een compiler geschreven.

[Rob]

WelVrolijk schreef op 18-10-2006 @ 23:32 :

<quoted_symbol>

Volgens jouw productieregels bestaat die uit:
- hetzij 1 of meer letters, omsloten door quotes
- hetzij niets.

Dat klinkt niet helemaal goed.
Ik zou verwachten:
- 1 of meer letters, omsloten door quotes
Of wellicht:
- 0 of meer letters, omsloten door quotes

Ja, je hebt gelijk. Ik was de """ om de epsilon vergeten.

WelVrolijk schreef op 18-10-2006 @ 23:32 :

<optionalchar>

Dit is volgens jouw grammatica een serie van 0 of meer chars (waarbij een char een cijfer of een letter is).
Die naamgeving vind ik een beetje misleidend.

Als je zou schrijven:
<optionalchar> ::= <letter>
<optionalchar> ::= <digit>
<optionalchar> ::= ε
dan zou de naam niet langer misleidend zijn.
En samen met jouw productieregels voor <identifier> heb je dan nog steeds een kloppende set productieregels voor <identifier>

Echter: Er zijn dan een heleboel manieren om de identifier ab te produceren:
1. ab is een identifier, want a is een identifier (want a is een letter) en b is een optionalchar (want b is een letter)
2. ab = aεb is een identifier, want aε is een identifier en b is een optionalchar
3. ab = abε is een identifier, want ab is een identifier en ε is een optionalchar
4. ...

Er moet dus een elegantere oplossing bestaan...

(Hint: denk nog eens aan die expression-tail. Zoiets kan je hier ook gebruiken...)

Ja, dat er iets eleganters bestond, wist ik al. Ik zat, zoals je ziet, al een beetje in de richting van expression-tail te denken.

Maar de mijne is best wel helemaal fout als ie zo is:

<identifier> ::= <letter>
<identifier> ::= <optionalchar> <identifier>
<optionalchar> ::= <letter>
<optionalchar> ::= <digit>
<optionalchar> ::= ε

Ik lees dan dat een identifier óf een letter is (gevolgd door niet), óf een optioneel karakter gevolgd door of een optioneel character of een identifier.

Zo voldoe ik totaal niet aan dit:
<identifier> ::= <letter> { <letter> | <digit> }

Even puzzelen...
<identifier> ::= <letter> { <letter> | <digit> }

is gelijk aan:
<identifier> ::= <letter> <tail>
<tail> ::= { <letter> | <digit> }

is gelijk aan:
<identifier> ::= <letter> <tail>
<tail> ::= <letter> <tail> | <digit> <tail> | ε

Volgens mij is die oplossing voor <identifier> veel beter?

Nee.

De grammatica *is* de syntax.

Maar behalve de syntax zijn er nog wat regels waaraan je programma moet voldoen.

Ja, dat snap ik. Ik bedoelde dus: "Een grammatica geeft syntactisch aan wat goed en fout is."

Pfff!!!

Compilerbouw in 3 weken?
Dat is wel *heel* intensief.

Ja. dat weten ze bij mij op school ook maar er is gewoon te weinig tijd, zeggen ze.
Ze hebben zelfs de uiterste deadline voor opdracht uitgesteld omdat bijna iedereen muurvast zit.

Een compiler is een computerprogramma.

Je schrijft zo'n compiler voor een bepaalde taal
doorgaans aan de hand van de grammatica van die taal.

Daarvoor moet die grammatica aan bepaalde voorwaarden voldoen. Zo niet, dan pas je de grammatica zo aan dat hij *wel* aan die voorwaarden voldoet, en toch nog exact de taal beschrijft.

De compiler bestaat uit een set procedures, die elkaar aanroepen.
In principe schrijf je *een* procedure voor *elke* productieregel.

[voorbeeld]

Ah, zo. Ja, het is er allemaal zo doorgeen gejaagd dat het bevatten gewoon moeilijk is.

Dus eigenlijk maak je een taal door eerst een grammatica op te stellen en aan de hand daarvan je compiler te bouwen (even grofweg).
Hah, als we zo door blijven gaan hoef ik het tentamen niet eens te leren.

[WelVrolijk]

Rob schreef op 19-10-2006 @ 00:54 :
Even puzzelen...
<identifier> ::= <letter> { <letter> | <digit> }

is gelijk aan:
<identifier> ::= <letter> <tail>
<tail> ::= { <letter> | <digit> }

is gelijk aan:
<identifier> ::= <letter> <tail>
<tail> ::= <letter> <tail> | <digit> <tail> | ε

Volgens mij is die oplossing voor <identifier> veel beter?

Ja!

Heel goed.
Alleen zou ik geneigd zijn, als naam bijvoorbeeld <identifier_tail> te gebruiken (of iets in die geest), zodat de lezer onmiddellijk ziet waar het bij hoort.
Dat is later ook makkelijker tijdens het bouwen van de compiler: Als je code zou moeten genereren, weet je vaak pas wat dat moet worden nadat je zowel het eerste stuk als de tail hebt teruggekregen.

Denk bijvoorbeeld aan de taal C. Daar kun je haakjes gebruiken om een expressie te openen, maar ook om een conditional expression te beginnen; Pas na het vraagteken weet je, dat je met een conditional expression bezig was:
Vergelijk maar eens:
x = ( a - b ) * c ;
met:
x = ( a ? 17 : 37 ) ;

[Rob]

WelVrolijk schreef op 19-10-2006 @ 07:26 :
Ja!

Heel goed.
Alleen zou ik geneigd zijn, als naam bijvoorbeeld <identifier_tail> te gebruiken (of iets in die geest), zodat de lezer onmiddellijk ziet waar het bij hoort.
Dat is later ook makkelijker tijdens het bouwen van de compiler: Als je code zou moeten genereren, weet je vaak pas wat dat moet worden nadat je zowel het eerste stuk als de tail hebt teruggekregen.

*glundert*

De leerkracht vond hem ook niet slecht. Ik ben wel te ver gegaan met dingen specificeren. Dat hele alfabet, definedas, digit en "|" worden bijvoorbeeld allemaal in de lexer gespecificeerd. dat moet ik dus nog verbeteren.

En hij moet, natuurlijk, LL(1) zijn. Maar dat doe ik later wel. En ik moet de namen voor de nonterminals verbeteren. Nouja, moet. Hij raadde het aan voor de duidelijkheid.

Ik post of vanavond nog, of anders zaterdag pas weer over hoe het verder gaat. Dank! =)

[Rob]

Nou, ik heb, hopelijk, zijn suggesties doorgevoerd. Of het goed is, weet ik niet. Misschien kun je mij dat vertellen?

<syntax>        ::=  <rule> <followrules>
<followrules>   ::=  <syntax>
<followrules>   ::=  e
<rule>          ::=  NONTERMINAL DEFINEDAS <expression>
<expression>    ::=  <term> OR <restexpr>
<expression>    ::=  <term>
<restexpr>      ::=  <expression>
<restexpr>      ::=  e
<term>          ::=  <factor> <restterm>
<term>          ::=  e
<restterm>      ::=  <term>
<restterm>      ::=  e
<factor>        ::=  TERMINAL | NONTERMINAL

Zoals je ziet heb ik iig alle directe recursiviteit eruit gehaald, want dat moest (helaas is het wel, naar mijn gevoel, indirect recursief geworden, maarja...).
De woorden in caps moeten in JFlex (de Java equivalent van Lex, de lexer) gedefinieerd worden, dus daar hoef je je niet echt druk om te maken.

[WelVrolijk]

Ik vind de namen <expression>, <term> en <factor> een beetje onduidelijk.

Ik zou eerder denken dat je met een <rule> een soort definitie geeft.
Of wellicht mag je "productie" gebruiken, het gaat immers om productieregels?

In plaats van <term> zou je wellicht iets kunnen gebruiken als alternatief of keuzemogelijkheid of zo.

[WelVrolijk]

Het volgende stukje vind ik verdacht:

<expression> ::= <term> OR <restexpr>
<expression> ::= <term>
<restexpr> ::= <expression>
<restexpr> ::= e

Dan kun je zaken krijgen als:
<structuur> ::= identifier |

En dat lijkt niet helemaal goed.
Ik denk dat een <expression> moet bestaan uit een of meer <term>en, gescheiden door de terminal die hier OR heet.

---

Ook het volgende stukje ziet er niet echt overtuigend uit:

<term> ::= <factor> <restterm>
<term> ::= e
<restterm> ::= <term>
<restterm> ::= e

Ik geloof niet dat een <term> leeg mag zijn.
Wel ε natuurlijk, maar dat is in dit geval natuurlijk een terminal.
Ik denk dat een <term> gewoon bestaat uit 1 of meer <factor>en.

[Sortjuh]

WelVrolijk schreef op 22-10-2006 @ 21:20 :
Ik vind de namen <expression>, <term> en <factor> een beetje onduidelijk.

Ik zou eerder denken dat je met een <rule> een soort definitie geeft.
Of wellicht mag je "productie" gebruiken, het gaat immers om productieregels?

In plaats van <term> zou je wellicht iets kunnen gebruiken als alternatief of keuzemogelijkheid of zo.

Goed punt. Het ging even om die recursiviteit eruit te werken. Ik verduidelijk het wel door <rule> iig te vervangen door <production>, of iets in die trant.

WelVrolijk schreef op 22-10-2006 @ 21:58 :
Het volgende stukje vind ik verdacht:

<expression> ::= <term> OR <restexpr>
<expression> ::= <term>
<restexpr> ::= <expression>
<restexpr> ::= e

Dan kun je zaken krijgen als:
<structuur> ::= identifier |

En dat lijkt niet helemaal goed.
Ik denk dat een <expression> moet bestaan uit een of meer <term>en, gescheiden door de terminal die hier OR heet.

---

Dat staat er toch? Er staat dat een <expression> óf een <term> is óf een <term> "|" <restexpression>, waarbij een <restexpr> dus weer een <expression> kan zijn (of leeg).
Wij moesten de "|" (dus het karakter zoals deze in de grammatica voorkomt) vervangen door OR en dit in de lexer definiëren als |.

WelVrolijk schreef op 22-10-2006 @ 21:58 :
Ook het volgende stukje ziet er niet echt overtuigend uit:

<term> ::= <factor> <restterm>
<term> ::= e
<restterm> ::= <term>
<restterm> ::= e

Ik geloof niet dat een <term> leeg mag zijn.
Wel ε natuurlijk, maar dat is in dit geval natuurlijk een terminal.
Ik denk dat een <term> gewoon bestaat uit 1 of meer <factor>en.

Dan staat het er toch goed? De term is hier of epsilon, of nog een term? Of heb ik die recursiviteit niet helemaaaaaal goed weggewerkt?

[WelVrolijk]

[code]<term> ::= <factor> <restterm>
<term> ::= e
<restterm> ::= <term>
<restterm> ::= e[\code]
Hier staat dat een <term> bestaat uit 0 of meer <factor>en.
Ik denk, dat een <term> bestaat uit 1 of meer <factor>en.

Merk overigens op, dat je hier twee keer een e gebruikt. Volgens mij is dat niet nodig voor het oplossen van recursie. Dus als je zoiets ziet (of in het algemeen: zodra je iets ziet wat er niet "elegant" uit ziet), kan het altijd handig zijn even te kijken wat er precies aan de hand is.

--------

Dat staat er toch? Er staat dat een <expression> óf een <term> is óf een <term> "|" <restexpression>, waarbij een <restexpr> dus weer een <expression> kan zijn (of leeg).

Ah.
Dan hangt het er even van af, wat je hier met e bedoelt.

Ik ben er van uitgegaan, dat e stond voor ε.
Maar wellicht bedoel je met e juist de terminal ε.
En dat is iets heel anders.

Ik zal er even opnieuw naar kijken, onder de aanname dat e staat voor de terminal ε.

[WelVrolijk]

Onder de aanname dat e staat voor de terminal ε:

<term> ::= <factor> <restterm>
<term> ::= e
<restterm> ::= <term>
<restterm> ::= e

Hier staat, dat <term> een epsilon is, of een <factor> gevolgd door een epsilon, of twee factoren gevolgd door een epsilon, of ...

Maar een <term> hoeft helemaal niet te eindigen op een epsilon!

Je zult eerst even moeten bedenken, of je wilt toestaan of een factor een epsilon mag zijn.

Als je dat toestaat, dan wordt de definitie van <term> heel eenvoudig:
Een term bestaat dan gewoon uit een of meer factoren.
Oftewel:

<term> ::= <factor> <restterm>
<restterm ::= <term>
<restterm ::= ε

Als een factor geen epsilon mag zijn, dan wordt het iets ingewikkelder.
Dit zou je bijvoorbeeld kunnen doen, indien je wilt dat een <term> bestaat uit ofwel een epsilon, ofwel een of meer factoren (dus zonder epsilon)
Dan krijg je iets als:

<term> ::= <factor> <restterm>
<term> ::= e
<restterm ::= <term>
<restterm ::= ε

Merk op dat dat net even iets anders is als:

<term> ::= <factor> <restterm>
<term> ::= e
<restterm ::= <term>
<restterm ::= e

De ε staat er in om de recursie op te lossen.
De e staat er in, omdat een term ook een epsilon mag zijn.
Dus ε staat voor de string "", en e staat voor de string "ε".

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

Nu kijken we nog even naar <expression>:

<expression> ::= <term> OR <restexpr>
<expression> ::= <term>
<restexpr> ::= <expression>
<restexpr> ::= e

Merk op, dat we er inmiddels al voor hebben gezorgd dat een <term> mag bestaan uit een epsilon.
Dan mogen we dus een <expressie> gewoon definieren als een of meer termen, gescheiden door de terminal OR. Daarmee hebben we de epsilon al afgevangen!

Hier heb je in feite twee keuzemogelijkheden:
Je kunt de OR in de <expression> stoppen, of in de <restexpr>.
Maak die keuze, en hou daar vervolgens aan vast!

Als je de OR in de <expression> stopt, krijg je:

<expression> ::= <term> OR <restexpr>
<expression> ::= <term>
<restexpr> ::= <expression>

Als je de OR in de <restexpr> stopt, krijg je:

<expression> ::= <term> <restexpr>
<restexpr> ::= OR <expression>
<restexpr> ::= ε

In het eerste geval kunnen beide productieregels van <expression> met <term> beginnen.
In het tweede geval zit je met een leeg alternatief.

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

Tja, nu zul je op een gegeven moment toch nog wat duidelijkere namen moeten invoeren.
Maar het kan handig zijn, dat niet te vroeg te doen.

Zoals je hierboven hebt gezien, is het heel moeilijk om ε en "ε" goed uit elkaar te blijven houden.
Op dezelfde manier kun je in de war raken, als je wilt praten over een alternatief voor <alternatief>, of een productieregel voor <productieregel> etcetera.

[Rob]

Verdomme. Post kwijt. Laptop viel uit. Nog een keer, dan maar. =\

WelVrolijk schreef op 23-10-2006 @ 06:31 :
[B]

<term> ::= <factor> <restterm>
<term> ::= e
<restterm> ::= <term>
<restterm> ::= e

Hier staat dat een <term> bestaat uit 0 of meer <factor>en.
Ik denk, dat een <term> bestaat uit 1 of meer <factor>en.

Merk overigens op, dat je hier twee keer een e gebruikt. Volgens mij is dat niet nodig voor het oplossen van recursie. Dus als je zoiets ziet (of in het algemeen: zodra je iets ziet wat er niet "elegant" uit ziet), kan het altijd handig zijn even te kijken wat er precies aan de hand is.

Ja, dat deed ik omdat een <term> ook ε (de terminal) mag zijn. Blijkbaar konden wij niet <x> ::= ε parsen, maar wel iets als <x> ::= <a><b>.

Ah.
Dan hangt het er even van af, wat je hier met e bedoelt.

Ik ben er van uitgegaan, dat e stond voor ε.
Maar wellicht bedoel je met e juist de terminal ε.
En dat is iets heel anders.

Ik zal er even opnieuw naar kijken, onder de aanname dat e staat voor de terminal ε.

Dat staat voor de terminal (dus ""). Als ik copy-paste verandert ie de ε in een e.

Dit zou je bijvoorbeeld kunnen doen, indien je wilt dat een <term> bestaat uit ofwel een epsilon, ofwel een of meer factoren (dus zonder epsilon)
Dan krijg je iets als:

<term> ::= <factor> <restterm>
<term> ::= e
<restterm ::= <term>
<restterm ::= ε

Dat is inderdaad de bedoeling. Maar ik merk nu dat ik de neiging heb om ε als een stop-character te gebruiken en niet als "dit mag leeg zijn".

Moet <term> ::= e niet <term> ::= ε zijn? Hij moet tenslotte of leeg zijn of uit meedere factoren bestaan.

offtopic: Het is trouwens wel verwarrend als je iets met zichzelf probeert te beschrijven...

Trouwens. Er staat ook in de grammatica dat een <factor> een TERMINAL | NONTERMINAL is. ε is een terminal, dus valt die dan niet onder <factor> ::= TERMINAL?

Merk op, dat we er inmiddels al voor hebben gezorgd dat een <term> mag bestaan uit een epsilon.
Dan mogen we dus een <expressie> gewoon definieren als een of meer termen, gescheiden door de terminal OR. Daarmee hebben we de epsilon al afgevangen!

[...]

Hier heb je in feite twee keuzemogelijkheden:
Je kunt de OR in de <expression> stoppen, of in de <restexpr>.
Maak die keuze, en hou daar vervolgens aan vast!

Dan vind ik die eerste beter, want daar vang je de epsilon al af met latere productieregels.

Dit is echt verwarrend en lastig om te doen. Vooral ε en "ε" uit elkaar houden is inderdaad niet makkelijk. Wat zou ik blij zijn als die grammatica af is. Dan is het ergste wat er nog moet komen het programmeren van de first en follow sets. ><

[Sortjuh]

Okay, ik heb iig antwoord van mijn docent. Ik heb de volgende grammatica opgestuurd gister:

    <syntax>        ::=  <rule> <followrules>
    <followrules>   ::=  <syntax>
    <followrules>   ::=  e
    <rule>          ::=  NONTERMINAL DEFINEDAS <expression>
    <expression>    ::=  <term> OR <restexpr>
    <expression>    ::=  <term>
    <restexpr>      ::=  <expression>
    <restexpr>      ::=  e
    <term>          ::=  <factor> <restterm>
    <term>          ::=  e
    <restterm>      ::=  <term>
    <restterm>      ::=  e
    <factor>        ::=  TERMINAL | NONTERMINAL

Ik kreeg de volgende feedback:

* de regel <term> ::= ε moet weg
* alternative mag niet leeg zijn, want dan kun je iets kriijgen als <a> | zonder iets achter de or.
* Je grammatica kan geen empty symbool in de invoer aan. Moet er nog wel bij!

Dus hij's in ieder geval bijna goed genoeg voor de opdracht.

Maar:
Hij kan toch wel <x> ::= ε aan vanwege de productie <term> ::= ε? Of zie ik dat verkeerd?

En de tweede regel klopt inderdaad. Die zag ik over het hoofd.

[WelVrolijk]

* Je grammatica kan geen empty symbool in de invoer aan. Moet er nog wel bij!

Wellicht betekent dat, dat een grammatica moet kunnen bestaan uit 0 of meer rules?
Volgens jouw definitie moet een grammatica bestaan uit 1 of meer rules.

[Sortjuh]

WelVrolijk schreef op 23-10-2006 @ 22:39 :
Wellicht betekent dat, dat een grammatica moet kunnen bestaan uit 0 of meer rules?
Volgens jouw definitie moet een grammatica bestaan uit 1 of meer rules.

Een empty symbool is opzich toch een rule, of niet?

[WelVrolijk]

Sortjuh schreef op 23-10-2006 @ 23:05 :
Een empty symbool is op zich toch een rule, of niet?

Niet volgens jouw grammatica.

En een empty symbol is iets anders als een lege string.

Voor zover ik weet is
<my_nonterminal> ::= ε
*wel* een geldige productieregel, en
<my_nonterminal> ::=
*niet*.

En ik denk dat
<nonterminal_1> ::= <nonterminal_3>

<nonterminal_3> ::= TERMINAL_1
*wel* een geldig grammatica-fragment is, en
<nonterminal_1> ::= <nonterminal_3>
ε
<nonterminal_3> ::= TERMINAL_1
*niet*.

Probeer eens netjes uit te werken, wat jouw grammatica met bovenstaande 4 fragmenten doet (bijvoorbeeld vanuit de productieregel voor <syntax>
---

Ik denk dat jouw docent bedoelt, dat jouw grammatica ook een "lege grammatica" (dus bestaande uit 0 rules) zou moeten kunnen verwerken.

Maar misschien bedoelt jouw docent gewoon, dat jouw grammatica geen epsilon kan verwerken?

Wat doet de lexer met een epsilon?

[WelVrolijk]

Wat doet de lexer eigenlijk met regelovergangen?

En hoe gaan BNF en EBNF om met regelovergangen?

Kennen BNF en EBNF manieren om het einde van een productieregel aan te geven?

[Sortjuh]

WelVrolijk schreef op 24-10-2006 @ 07:27 :
Niet volgens jouw grammatica.

En een empty symbol is iets anders als een lege string.

Voor zover ik weet is
<my_nonterminal> ::= ε
*wel* een geldige productieregel, en
<my_nonterminal> ::=
*niet*.

En ik denk dat
<nonterminal_1> ::= <nonterminal_3>

<nonterminal_3> ::= TERMINAL_1
*wel* een geldig grammatica-fragment is, en
<nonterminal_1> ::= <nonterminal_3>
ε
<nonterminal_3> ::= TERMINAL_1
*niet*.

Probeer eens netjes uit te werken, wat jouw grammatica met bovenstaande 4 fragmenten doet (bijvoorbeeld vanuit de productieregel voor <syntax>

Dat ben ik helemaal met je eens. Maar <x> ::= ε is toch een productieregel? Het is, als ik het goed heb, een productieregel die zegt dat die specifieke nonterminal leeg mag zijn als je 'm probeert te parsen.

WelVrolijk schreef op 24-10-2006 @ 07:27 :
Ik denk dat jouw docent bedoelt, dat jouw grammatica ook een "lege grammatica" (dus bestaande uit 0 rules) zou moeten kunnen verwerken.

Maar misschien bedoelt jouw docent gewoon, dat jouw grammatica geen epsilon kan verwerken?

Dit is wat ik terug kreeg van hem:

Als je een regel hebt als:
<a> ::= ε
moet jouw parser die kunnen verwerken.
In deze regel is ε een speciaal symbool, een terminaal symbool dus, net zo als OR dat ook is.
Je hebt dus 2 soorten empty:

* in je metagrammatica: <x> ::= ε, betekenis: de nonterminal x kan eventueel door helemaal niets vervangen worden.
* in je metagrammatica: <blabla> ::= EMPTY, betekenis: In je invoer wordt nu het empty symbool verwacht, net zoals bij OR in de invoer "|" wordt verwacht. Anders kun je geen regels parsen als : <x> ::= ε !!!

Daaruit neem ik aan dat hij bedoelt dat de grammatica allebei de mogelijkheden die je net aankaartte, aan moet kunnen.

WelVrolijk schreef op 24-10-2006 @ 07:27 :
Wat doet de lexer met een epsilon?

Ik heb geen enkel idee. Ik neem dat ie het vervangt door een token?

Wat doet de lexer eigenlijk met regelovergangen?

En hoe gaan BNF en EBNF om met regelovergangen?

Kennen BNF en EBNF manieren om het einde van een productieregel aan te geven?

Op alledrie kan ik geen antwoord geven. Dat is bij ons nooit behandelt. =\ Er is alleen gezegd dat we de dingen kunnen vangen in een grammatica en dat we grammatica's gebruiken om structuren te beschrijven.

[Sortjuh]

Hm, nou, de grammatica is eindelijk goedgekeurd (alhoewel dingen als <x> ::= <a>ε<b> wel geparsed kunnen worden terwijl dat eigenlijk niet de bedoeling is).

Blijkbaar moest ik ook een manier vinden om het einde van een productieregel aan te geven en ik heb besloten om dat simpelweg met een punt te doen.

At any rate: Deze grammatica is goedgekeurd:

<syntax>        ::=  <rule> <followrules>
<followrules>   ::=  <syntax>
<followrules>   ::=  ε
<rule>          ::=  NONTERMINAL DEFINEDAS <production> POINT
<production>    ::=  <term> OR <alternative>
<production>    ::=  <term>
<alternative>   ::=  <production>
<term>          ::=  <factor> <restterm> | <factor>
<restterm>      ::=  <term>
<restterm>      ::=  ε
<factor>        ::=  TERMINAL | NONTERMINAL | EMPTY | ε

Hier is <x> ::= ε een non-terminal die leeg mag zijn in de te parsen grammatica, <x> ::= EMPTY een nonterminal die er als <y> ::= ε uit moet zien in de te parsen grammatica, TERMINAL een terminal in de te parsen grammatica, NONTERMINAL een nonterminal in de te parsen grammatica, OR het or-teken in de te parsen grammatica, DEFINEDAS het ::= teken in de te parsen grammatica en POINT een . in de te parsen grammatica.

Nu moet de parser geschreven worden en, IMO het ergste deel, de pseudo + eigenlijke code om de first en follow sets te bepalen. In Java... Dus dat kan nog leuk worden.

Enig idee (met pseudo code) hoe je dat laatste aanpakt? Ik moet in ieder geval een manier vinden om de hele productieregel efficiënt op te slaan.
Is het misschien practisch om het deel van de productieregel dat na de ::= komt in een array op te slaan en vandaar verder te werken? Of zijn er betere manieren om een de productieregels op te slaan?

(edit: Ik moet toch echt eens leren op mijn eigen account te posten. )

Er zijn verschillende mogelijkheden.

---

Je zou bijvoorbeeld uit kunnen gaan van de grammatica.

Voordeel is de overzichtelijkheid, aangezien je je programma waarschijnlijk *ook* zult opbouwen aan de hand van de grammatica.

Een veel gebruikte methode is een syntax-boom.

In dit geval bestaat de Root uit een Syntax-node.

Een syntax-node bestaat uit twee takken:
1 - een rule-node
2 - een followrules-node

Een followrules-node bestaat uit een tak:
ofwel 1a - een syntax-node
ofwel 1b - een epsilon-node

Een rule-node bestaat uit twee takken:
1 - een NONTERMNIAL node
2 - een production node

etcetera.
Je kunt dan alles vangen in nodes met 0, 1 of 2 takken.

-----

Je zou ook gebruik kunnen maken van de mogelijkheden van Java.

Bijvoorbeeld:

Een syntax bestaat uit 1 of meer rules.
Dat kun je eenvoudig vangen in een geordende verzameling.

Een rule is dan een class bestaande uit (feitelijk) 2 velden.

Etcetera.


Voordeel van deze aanpak is dat je (gevoelsmatig) zeer dicht bij de betekenis blijft, en dat je optimaal gebruikt maakt van de ingebouwde mogelijkheden van Java.

Nadeel is dat je afwijkt van de grammatica die we net met zoveel moeite hebben opgesteld.


Dit laatste zou zeer zwaar moeten wegen, aangezien die grammatica inmiddels door de opdrachtgever is goedgekeurd!!!

[Sortjuh]

Ohja! Een Boomstructuur zou wel eens kunnen werken.
Maar misschien zijn de verzamelingen wat logischer. We moeten die sets namelijk gebruiken om de LL(1)-heid te bepalen van de grammatica (met name de union operator).

Het liefst blijf ik zo trouw mogelijk aan de grammatica, want dan wordt het coden van de first en follow sets waarschijnlijk makkelijker. Ik denk dat een boom dan het beste idee is? (zelf niet eens aan gedacht...)

[WelVrolijk]

Ik zou verwachten dat je aan elk van de knopen (of wellicht elk van de knopen die non-terminal is) een tweetal functie-members (sorry, ben de juiste terminologie kwijt, is alweer ruim 3 jaar geleden dat ik mijn Java-certificering haalde. methods?) heeft: "first()" en "follower()" die als resultaat een Set opleveren (of liever een child ervan die enkel Terminals als element kan hebben).

Zo'n knoop zal enkele members moeten hebben die de takken representeren.
Voor die boomstructuur heb je dus helemaal geen JTree nodig.

Als je echt iets met die boom wilt doen zal je toch een of andere boomtraversie moeten uitvoeren. Maar dat gaat bijna automatisch in Java (of andere object-georienteerde talen), want je zult tijdens het coderen "automatisch" alle takken afhandelen.

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

Hmmm...

Ik geloof dat ik in bovenstaand verhaal (over die first() en follower()) wellicht iets te optimistisch was.
Misschien moet je inderdaad die Sets "van buitenaf" vullen.

---

Als ik even terugdenk aan de algoritmes, denk ik dat het stuk rondom <term> en <restterm> cruciaal is.

Dus vanuit het algoritme gezien, zou je eigenlijk willen dat zo'n <term> zich gedraagt als een array (of eventueel als een linked list -- dubbelgelinkt).
Maar je kunt natuurlijk in de class Term gewoon een functiemember definieren die als resultaat een List heeft (namelijk de list die bestaat uit alle factoren achter elkaar -- oftewel "de" factor uit het object + de list van de restterm).
Dan heb je enerzijds de structuur van de grammatica mooi gevangen in de gegenereerde syntaxboom, en anderzijds gezorgd dat het algoritme eenvoudig te programmeren is.

[IvdSangen]

Ik zou je hiermee moeten kunnen helpen, maar ik ben de draad een beetje kwijtgeraakt bij het lezen ervan. Zou je even kunnen recapituleren wat op dit moment aan de orde is? Misschien dat ik je kan helpen.

[WelVrolijk]

IvdSangen schreef op 28-10-2006 @ 02:49 :
Ik zou je hiermee moeten kunnen helpen, maar ik ben de draad een beetje kwijtgeraakt bij het lezen ervan. Zou je even kunnen recapituleren wat op dit moment aan de orde is? Misschien dat ik je kan helpen.

Bij het lezen van de thread moet je in de gaten houden dat:

- we hier (uiteindelijk) niet praten over de syntax van een taal, maar over de syntax van een syntax
- we niet toewerken naar een compiler of interpreter die een programma moet vertalen, maar naar een parser die een BNF syntax moet verwerken
- het geheel af en toe vertroebeld wordt door vertaalslagen tussen "compilerbouw nu" en "compilerbouw begin 80-er jaren".
- er af en toe misverstanden zijn over het niveau van abstractie.

[IvdSangen]

Het enige probleem is dus nog dat iets als

A ::= x |

correct geparsed wordt: de lege string na een ``or''. Begrijp ik dat goed?

[WelVrolijk]

En wat betreft die verschillen tussen nu en toen:


De theorie is blijkbaar niet noemendswaardig veranderd.

In de notaties voor grammatica is wat meer eenheid gekomen.

Momenteel zijn er overal computers beschikbaar.
Destijds moesten we eerst naar de universiteit fietsen, vervolgens naar de terminalkamer, en daar wachten tot een van de terminals vrij kwam.
Daar konden we dan bijvoorbeeld bouwen aan compilers die gratis beschikbaar werden gesteld aan iedereen die rijk genoeg was om thuis een microcomputer te hebben.

Momenteel zijn de object-georienteerde talen zo ver gegroeid, dat je je bij het bouwen van een compiler kunt concentreren op de relevante zaken. In onze tijd moesten we veel aandacht besteden aan de algoritmen en datastructuren.

Wij werkten destijds met een speciale programmeertaal voor compilers, waardoor (het relevante deel van) de programma's er uitzag als de syntax van de programmeertaal (in ons geval in de Van Wijngaarden notatie).

Bij het schrijven van een compiler in Java zul je er *zelf* voor moeten zorgen dat de Classes die je bouwt dicht genoeg bij de grammatica liggen.
Tenzij je gebruik kunt maken van een voorgedefinieerde Class (bij voorkeur een abstracte).

[Sortjuh]

IvdSangen schreef op 28-10-2006 @ 02:49 :
Ik zou je hiermee moeten kunnen helpen, maar ik ben de draad een beetje kwijtgeraakt bij het lezen ervan. Zou je even kunnen recapituleren wat op dit moment aan de orde is? Misschien dat ik je kan helpen.

Nou, we zijn begonnen met het maken van First en Follow sets van de grammatica in mijn eerste post.
First set was gelukt, maar het toepassen van de Follow Sets regels liep niet helemaaaaaal goed (ik heb er door de drukte ook niet meer naar gekeken, dus ik kan nog steeds niet echt Follow Sets maken).

Omdat ik een opdracht kreeg een LL(1) checker te maken, ging de thread ineens een hele andere kant op:
- Het bouwen van een grammatica die een BNF grammatica representeerd (wat dus nu gelukt is),
- een interne representatie maken van de grammatica in Java (mee bezig, in de laatste paar posts),
- een scanner bouwen met behulp van JFlex (JFlex is software geschreven in Java dat een lexer, scanner en parser bevat)
- Een recursieve, descend parser bouwen voor de grammatica
- De LL(1) controle zelf

En tussendoor kwamen er ook nog veel vragen van mij over het vak zelf, aangezien ik er weinig van snapte.

[Sortjuh]

IvdSangen schreef op 28-10-2006 @ 12:33 :
Het enige probleem is dus nog dat iets als

A ::= x |

correct geparsed wordt: de lege string na een ``or''. Begrijp ik dat goed?

In de grammatica die ik hierboven gepost heb, zou dat niet mogen gebeuren. Dat zou mijn leerkracht niet eens goedkeuren.

[WelVrolijk]

IvdSangen schreef op 28-10-2006 @ 12:33 :
Het enige probleem is dus nog dat iets als

A ::= x |

correct geparsed wordt: de lege string na een ``or''. Begrijp ik dat goed?

Neen.

Als de grammatica dat toelaat, kun je dat altijd nog afvangen met een semantische regel.

---

Het probleem is dat de thread tot gisteren alleen ging over syntax en parsen.

Nu begint het deel over de datastructuur waarin we de ingelezen tekst opslaan, en over de implementatie van de beide algoritmes.


Het eerste is een technische keuze.
Die keuze moet gemaakt worden door de Technisch Ontwerper, of door de Programmeur. Hoewel de Opdrachtgever daar natuurlijk wel harde eisen aan kan stellen, en de Functioneel Ontwerper daar suggesties kan doen die er zeer dwingend uitzien.
Wij buitenstaanders kunnen daar alleen wat hits en tips geven.


Het tweede punt ligt anders.
Wij kunnen de vraagsteller helpen, de algoritmes beter te begrijpen.
Dat kan hem helpen bij het kiezen van een manier om de door hemgekozen datastructuur te doorlopen voor elke stap in het algoritme.
En dat kan uiteindelijk weer invloed hebben op de keuze die de vraagsteller uiteindelijk zal nemen bij het kiezen van de opslagstructuur.

[WelVrolijk]

Sortjuh schreef op 28-10-2006 @ 12:49 :
In de grammatica die ik hierboven gepost heb, zou dat niet mogen gebeuren. Dat zou mijn leerkracht niet eens goedkeuren.

Maar hij heeft het wel goedgekeurd...

Kijk nog maar eens goed naar de goedgekeurde grammatica (27-10-2006 @ 17:24) :

Achter een OR komt een <alternative>
Een <alternative> is een <production>
Een <production> kan bestaan uit een <term>
Een <term> blijft bestaan uit een <factor>
Een <factor> kan bestaan uit een lege string

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

Bedenk echter, dat deze grammatica al goedgekeurd is.

Als je de grammatica verandert, moet je ---strikt gesproken--- eerst toestemming vragen aan je opdrachtgever, voordat je verder mag.
En het is vandaag zaterdag. Waarschijnlijk heeft je opdrachtgever vandaag een vrije dag (dit is een heel realistische situatie. Komt in de praktijk ook voor, veelal als je vlak voor een deadline zit ).

Dus je moet even goed nadenken:
- Verdergaan met de goedgekeurde grammatica, en dit probleem later tackelen?
- De grammatica corrigeren, maandag goedkeuring krijgen, en ondertussen de ontwikkeling van de applicatie stil leggen?
- De grammatica corrigeren, maandag goedkeuring krijgen, en ondertussen stiekum doorwerken in de hoop dat maandag inderdaad goedkeuring wordt gegeven?

[Rob]

WelVrolijk schreef op 28-10-2006 @ 13:02 :
Maar hij heeft het wel goedgekeurd...

Kijk nog maar eens goed naar de goedgekeurde grammatica (27-10-2006 @ 17:24) :

Achter een OR komt een <alternative>
Een <alternative> is een <production>
Een <production> kan bestaan uit een <term>
Een <term> blijft bestaan uit een <factor>
Een <factor> kan bestaan uit een lege string

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

Bedenk echter, dat deze grammatica al goedgekeurd is.

Als je de grammatica verandert, moet je ---strikt gesproken--- eerst toestemming vragen aan je opdrachtgever, voordat je verder mag.
En het is vandaag zaterdag. Waarschijnlijk heeft je opdrachtgever vandaag een vrije dag (dit is een heel realistische situatie. Komt in de praktijk ook voor, veelal als je vlak voor een deadline zit ).

Dus je moet even goed nadenken:
- Verdergaan met de goedgekeurde grammatica, en dit probleem later tackelen?
- De grammatica corrigeren, maandag goedkeuring krijgen, en ondertussen de ontwikkeling van de applicatie stil leggen?
- De grammatica corrigeren, maandag goedkeuring krijgen, en ondertussen stiekum doorwerken in de hoop dat maandag inderdaad goedkeuring wordt gegeven?

...Nu je het zegt. Zo ver had ik nog niet gekeken.
De perfectionist in mij zegt dat ik het moet zeggen en een grammatica moet maken die dat dus niet toe laat. Maar anderzijds wil ik ook graag door met de opdracht.

...Toch maar emailen.

[Rob]

Nu pas ziet ie het. En nu pas zegt ie dat het eigenlijk toch niet goed is, maar dat wij maar wel door moeten gaan.

Okay, is het mogelijk zonder al te veel verbouwingen het <x> ::= <a> | deel weg te laten, of moet de hele grammatica dan herschreven worden? Als het teveel gerommel is, werk ik liever door, want anders komt het programma nooit af en dan telt mijn tentamencijfer niet eens mee...
Maar ik wil het wel goed hebben, want anders gaat het mij dwars zitten.

Een eenvoudig patch van de grammatica:

<term> ::= EPSILON
<term> ::= <factor> <restterm>
<restterm> ::= ε
<restterm> ::= <term>
<factor> ::= TERMINAL
<factor> ::= NONTERMINAL

(laagste niveau ---met name dat EPSILON-symbool--- natuurlijk nog wel even vertalen naar wat jullie gebruiken)

De grammatica wordt dan (in woorden):
- Een syntax bestaat uit een of meer rules.
- Een rule bestaat uit een NONTERMINAL, gevolgd door een DEFINEDAS-symbool, gevolgd door een production, gevolgd door een POINT-symbool.
- Een production bestaat uit een of meer termen, telkens gescheiden door een OR-symbool.
- Een term bestaat ofwel uit een EPSILON-symbool, ofwel uit een of meer factoren.
- Een factor bestaat uit een TERMINAL of NONTERMINAL.


Dit is wederom een realistische situatie.
Als je even vast zit op de werkvloer, kun je altijd assistentie vragen aan collega's of concullega's op de werkvloer of ver daarbuiten.
En veelal is er dan wel een of andere guru in India die snel een (meestal technisch correct) antwoord geeft.
(Veel van de Indiërs hier op de werkvloer zijn heel goed in het snel absorberen van kennis.
En ze zijn zeer ijverig: Op dit moment (18:15) tel ik hier op de vloer nog ruim 10 Indiërs, en nog maar 3 Nederlanders. Overdag is het half om half.)


Als je denkt, dat je dit (of een andere oplossing) snel goedgekeurd krijgt, kan het inderdaad handig zijn om met een kloppende grammatica verder te werken.

-----------------
De tijd die je besteedt om een ontwerp te verbeteren, win je in de praktijk altijd terug, zij het veelal pas op de lange duur (of op andere plaatsen in de organisatie).

Het is echter in de praktijk niet altijd mogelijk, je directe chefs of je opdrachtgever daarvan te overtuigen.
(Denk maar eens aan de millenniumbug, die ontstond doordat opdrachtgevers decennia lang onmogelijk maakten de software robuust te maken)

Dus aan jou de keus:
1. Nu oplossen, en dus de confrontatie met de opdrachtgever aangaan.
2. Doen wat de opdrachtgever zegt, en de problemen later oplossen.


Alternatief 1 levert in de regel een mooier eindresultaat.
Alternatief 2 levert in de regel eerder een tastbaar tussenresultaat.

Soms is alternatief 1 beter, soms is alternatief 2 beter...

[Rob]

Hartstikke bedankt. Dit is het antwoord:

Het lijkt me nu ok, ε is een metasymbool en zou ik gewoon empty noemen of zoiets.

Het deel "Het lijkt mij nu okay" komt zo raar op mij over. Ik krijg het idee dat hij er niet eens serieus naar kijkt.
Alleen snap ik zijn laatste zin niet helemaal. Wil ie EMPTY nu vervangen hebben door empty?

Nouja,het is in ieder geval goedgekeurd en die gegeven situatie komt in ieder geval niet meer voor.
Zoals je ziet heb ik dus maar voor optie 1 gekozen. Nu wordt het tijd om écht het programma te schrijven.

Alhoewel ik wel steeds lookahead unexpected errors krijg. Ik vind het zo jammer dat debug informatie meestal helemaal niets zegt over de echte error... Zie dit, bijvoorbeeld:

Tokenkind: 72, token: <x>
Tokenkind: 70, token: ::=
Tokenkind: 72, token: <a>
Tokenkind: 73, token: A
Tokenkind: 72, token: <b>
Tokenkind: -1, token:

parse error in <factor> : lookahead unexpected
lookahead '' (kind=-1) at 2/1
Exception in thread "main" java.lang.RuntimeException
   at Parser.parseError (Parser.java:52)
   at Parser.parseFactor (Parser.java:188)
   at Parser.parseTerm (Parser.java:163)
   at Parser.parseRestTerm (Parser.java:168)
   at Parser.parseTerm (Parser.java:164)
   at Parser.parseRestTerm (Parser.java:168)
   at Parser.parseTerm (Parser.java:164)
   at Parser.parseRestTerm (Parser.java:168)
   at Parser.parseTerm (Parser.java:164)
   at Parser.parseProduction (Parser.java:153)
   at Parser.parseRule (Parser.java:148)
   at Parser.parseSyntax (Parser.java:133)
   at Parser.parseRoot (Parser.java:98)
   at Main.main (Main.java:14)

Dit is gewoon een stukje tekst waarin de regel <x> ::= <a>A<b> staat. token -1 is het End Of File token. Deze parser is gebaseerd op de parser die in het JFlex pakket zat wat wij van school moesten downloaden. Hun tekstfiles gaven geen errors.
Ik krijg steeds lookahead unexpected errors. Voornamelijk wanneer ik of naar de volgende regel wil, of als ie op 1 regel het EOF token tegenkomt.

Als ik het EOF token toevoeg aan de switch (dus dat er iets mee moet gebeuren), dan krijg ik een hele lijst met Tokenkind: -1 en dan een segmentation fault.


----


Ik hoor trouwens veel van die Indiërs. Ze schijnen zeer goed opgeleid te zijn en er echt geen moeite mee te hebben met dit soort dingen.
Mag ik vragen wat voor werk je doet? Je maakt me nieuwsgierig.

[WelVrolijk]

Rob schreef op 31-10-2006 @ 14:33 :
Het deel "Het lijkt mij nu okay" komt zo raar op mij over. Ik krijg het idee dat hij er niet eens serieus naar kijkt.

Alleen snap ik zijn laatste zin niet helemaal. Wil ie EMPTY nu vervangen hebben door empty?

Hij heeft reeds eerder gedacht dat het klopte, en toen zat hij fout. (Kan gebeuren, vergissen is menselijk. Gebeurt in de praktijk ook: Het is goedkoper af en toe een fout te moeten herstellen, dan door te gaan totdat je 100% zekerheid denkt te hebben.)


Ik denk dat het vooral belangrijk is dat je te allen tijde *zelf* het verschil blijft zien tussen beide epsilons.

De ene geeft aan, dat *jouw* grammatica op die plaats (eventueel) genoegen neemt met een lege string.
De andere geeft aan, dat *de grammatica die je inleest* op die plaats genoegen zal nemen met een lege string.

Alhoewel ik wel steeds lookahead unexpected errors krijg.

De debug-informatie zeg toch al een heleboel.
Maar dat is bedoelt voor jou, en niet voor de gebruiker van het programma. De gebruiker krijgt (als het goed is) alleen de foutboodschappen te zien die *jij* hebt geschreven.

Uit die debug-informatie zien we:

Het programma:
- probeert een <syntax> te lezen
- probeert een <rule> te lezen
(Op dit moment werden <x> en ::= verwerkt)
- probeert een <production> te lezen
- probeert een <term> te lezen
(Op dit moment werd <a> verwerkt)
- probeert een <restterm> te lezen
- probeert een <term> te lezen
(Op dit moment werd A verwerkt)
- probeert een <restterm> te lezen
- probeert een <term> te lezen
(Op dit moment werd <b> verwerkt)
- probeert een <restterm> te lezen
- probeert een <term> te lezen
- probeert een <factor> te lezen
En dat mislukt.


Op dat moment behoort Parser.parseFactor terug te melden dat het lezen van een <factor> is mislukt.
Vervolgens behoort Parser.parseTerm (nadat ook het inlezen van een EPSILON geen succes had) terug te melden dat het lezen van een <term> is mislukt.

En vervolgens behoort Parser.parseRestTerm de andere tak te proberen: <restterm> ::= ε

Dat lukt!
Vervolgens behoort Parser.parseRestTerm succes terug te melden.
Vervolgens behoort Parser.parseTerm succes terug te melden.
Vervolgens behoort Parser.parseProduction succes terug te melden.
Vervolgens behoort Parser.parseRule succes terug te melden.
Vervolgens behoort Parser.parseSyntax succes terug te melden.
Vervolgens behoort Parser.parseRoot succes terug te melden.

En daarmee hoort het Parsen succesvol te eindigen.

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

Kortom: het gaat mis, op het moment dat Parser.parseFactor er niet in slaagt, een <factor> in te lezen.

Default gedrag is dan (blijkbaar) dat ParseError wordt aangeroepen.
En dat mag (blijkbaar) dus niet!


Je probeert hier een <factor> in te lezen.
En dat lukt niet.

Op dat moment zijn er twee mogelijkheden:
1 - Dat mag wel.
2 - Dat mag niet.

Als het inlezen van die <factor> *wel* mag mislukken, moet jouw programma niet abenden, maar doorgaan met het volgende alternatief.

Als het inlezen van die <factor> *niet* mag mislukken, moet jouw programma niet abenden, maar een foutmelding genereren.
En wel een foutmelding waar de gebruiker iets aan heeft ...


In dit geval mag het inlezen van die <factor> *wel* mislukken;
Die <restterm> hoefde immers niet perse een <term> te zijn, maar mocht eventueel ook een lege string zijn!

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

Je zult (blijkbaar) iets met die EOF moeten doen.

Daarvoor zijn er (minstens) twee mogelijkheden:
1 - je geeft succes of falen van de parseMijnSymbool-functies aan door als resultaat (bijvoorbeeld) een boolean op te leveren.
2 - je geeft falen van de parseMijnSymbool-functies aan door middel van exceptions.

Indien je met functieresultaten wilt werken, zul je hetzij die exception moeten opvangen, hetzij iets met die EOF moeten doen.

Indien je zelf exceptions gaat gebruiken, ligt het voor de hand om die EOF-exception netjes op te vangen.

Ik hoor trouwens veel van die Indiërs. Ze schijnen zeer goed opgeleid te zijn en er echt geen moeite mee te hebben met dit soort dingen.

Ze zijn i.h.a. opgeleid op gespecialiseerde universiteiten, waar elk jaar misschien wel honderduizend studenten afstuderen.
En de besten sturen ze vervolgens uit over de wereld.

Die hebben er vaak best wel moeite mee, dat ze veelal samen moeten werken met mensen die ontslagen gaan worden omdat het werk naar India wordt uitbesteed.

Mag ik vragen wat voor werk je doet? Je maakt me nieuwsgierig.

In principe ben ik gewoon Programmeur en Functioneel Ontwerper. Vanuit die rollen kom je vaak ook terecht in test-functies en in helpdesk-achtige omgevingen (tweede of derdelijns).

Vanwege mijn wiskundige achtergrond zie ik snel zaken die in de toekomst wel eens problemen zouden kunnen opleveren.
Momenteel moet ik leren, er op te vertrouwen dat die problemen te zijner tijd wel opgelost kunnen worden, vooropgesteld dat we ze op tijd onderkennen en dat er op tijd actie wordt ondernomen.

Momenteel ben ik werkzaam als Data Warehouse specialist.

Het afgelopen jaar viel ik vooral op doordat ik (als developer) onze Acceptatie-testers opjoeg om *zoveel mogelijk* fouten te ontdekken.
Die houding begint zich de laatste maanden langzaam te verspreiden door de organisatie.
Immers: Als "onze" testers 10 fouten *meer* ontdekken, betekent dat dat de applicatie die wij opleveren 10 fouten *minder* zal bevatten.
Helaas zijn er elders (lees: hogerop) in de organisatie nog steeds mensen die proberen te "bezuinigen" op testen...

[Rob]

Alleen even dit quoten want dit zit mij het meeste dwars. De rest komt nog wel...

Je zult (blijkbaar) iets met die EOF moeten doen.

Daarvoor zijn er (minstens) twee mogelijkheden:
1 - je geeft succes of falen van de parseMijnSymbool-functies aan door als resultaat (bijvoorbeeld) een boolean op te leveren.
2 - je geeft falen van de parseMijnSymbool-functies aan door middel van exceptions.

Indien je met functieresultaten wilt werken, zul je hetzij die exception moeten opvangen, hetzij iets met die EOF moeten doen.

Indien je zelf exceptions gaat gebruiken, ligt het voor de hand om die EOF-exception netjes op te vangen.

Even vanaf het begin uitleggen:
Een tijdje geleden hadden wij een practicum opdracht: Het betrof het programma JFlex. Dit programma is een op Lex gebaseerde Lexer geschreven in Java. Er zit een Scanner.lex file bij waarin je de lexicale specificaties opgeeft. Met behulp van een shell scriptje kon je Scanner.lex file gebruiken om Scanner.java te genereren. Parser.java en TokenKinds.java waren allemaal al klaar voor gebruik en dit was dus slechts een oefening om te oefenen met het opgeven van lexicale specificaties.

Het was de bedoeling de lexicale specificatie zo uit te breiden dat het programma integers (decimaal, octaal en hexidecimaal), doubles, longs en commentaar kon herkennen en parsen. Dat ging prima.

Het eindresultaat ziet er dan ook zo uit (let op het EOF token, -1):

Tokenkind: 61, token: 1
Tokenkind: 22, token: -
Tokenkind: 61, token: 2
Tokenkind: 23, token: *
Tokenkind: 61, token: 3
Tokenkind: 21, token: +
Tokenkind: 61, token: 4
Tokenkind: -1, token:
Tokenkind: -1, token:
((1-(2*3))+4)

Hij liet dus netjes het EOF token zien en genereerde verder geen errors.

En dan is hier mijn opdracht...

[...]

3. Bouw een scanner voor de tokens van de grammatica uit stap 1 met behulp van JFlex.

4. Bouw een recursive descent parser voor de grammatica uit stap 1. De parser moet de interne representatie van de ingelezen grammatica opbouwen en vervolgens deze representatie controleren (stap 3).
[...]

Met die scanner ben ik dus bezig. Toen dacht ik dus: Als ik toch een Scanner moet bouwen mbv JFlex, dan kan ik de Parser die erin zit ook wel gebruiken als basis.
Ik heb dus de code voor de Parser gekopieërd en aangepast, zonder dingen aan het EOF token te veranderen en de Scanner file alleen maar uitgebreid.

Desondanks blijf ik toch de EOF fouten krijgen, terwijl ik die met de originele invoer bestanden niet heb.

Mijn punt: Hoe kan het originele pakketje geen errors terugkeert en mijn gewijzigde code wel ondanks dat ik de code die een EOF afhandelt niet heb gewijzigd?




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


Ohja, over het weergeven van de data in een boom: Is het ook mogelijk een correcte boom te genereren voor onze grammatica (dus niet over een te parsen grammatica)?

[WelVrolijk]

Rob schreef op 01-11-2006 @ 00:55 :
Mijn punt: Hoe kan het originele pakketje geen errors terugkeert en mijn gewijzigde code wel ondanks dat ik de code die een EOF afhandelt niet heb gewijzigd?

De parser uit de vorige opdracht werkt waarschijnlijk op een grammatica die er ongeveer zo uit ziet:

<root> ::= <expression>
<expression> ::= <term> PLUS <expression_rest>
<expression> ::= <term> MINUS <expression_rest>
<expression_rest> ::= <expression>
<term> ::= <factor> TIMES <term_rest>
<term> ::= <factor> DIVIDED_BY <term_rest>
<term_rest> ::= <term>
<factor> ::= NUMBER
<factor> ::= <closed_expression>
<closed_expression> ::= OPEN <expression> CLOSE


De truc zit hem hier in het parsen van die <factor>:

Op die plaats lees je *ofwel* een getal, *ofwel* een "(".
Als een van beide niet lukt, dan probeer je de andere.

------

Bij "onze" grammatica zit de truc in de restterm.
(Dat hadden we gisteren trouwens ook al afgeleid uit de foutmelding)

Op die plaats lees je *ofwel* een factor, *ofwel* niets.
Dus je weet niet van te voren of hier een factor staat, er kan ook iets anders staan. In principe kan hier alles staan wat in FOLLOWERS (<restterm>) voorkomt (voor zover de <restterm> weet).

=====

Kon de parser uit de vorige opdracht ook meer dan een expressie aan?

Zo ja, dan zag de grammatica er wellicht als volgt uit:

<root> ::= <expression_list>
<expression_list> ::= <expression> <expression_rest>
<expression_rest> ::= <expression>
<expression_rest> ::= ε
enzovoorts...

Dan speelt daar hetzelfde bij de <expression_rest> wat hier bij de <restterm> speelt.

Probeer de parser uit de vorige opdracht eens uit met de volgende invoer:

1 - 2 * 3 + 4
1 - 2 * 3 + 4


Als dat geen abend oplevert, zou je eens goed moeten kijken naar de code voor Parser.parseExpressionRest().

===================

Ohja, over het weergeven van de data in een boom: Is het ook mogelijk een correcte boom te genereren voor onze grammatica (dus niet over een te parsen grammatica)?

Natuurlijk.

Daavoor hoef je alleen maar onze grammatica los te laten op onze grammatica.

---

Kun je de uiteindelijke vorm van onze grammatica even quoten?
Dat voorkomt misverstanden.

[Rob]

De grammatica voor die parser zag er zo uit:

 <expression> ::= <term> <expression-tail>
 <expression-tail> ::= ε | <plus-expression> | <minus-term>
 <plus-expression> ::= PLUS <expression>
 <minus-term> ::= MINUS <term> <expression-tail>
 <term> ::= <factor> <term-tail>
 <term-tail> ::= ε | <times-term>
 <times-term> ::= TIMES <term>
 <factor> ::= PARENT_LEFT <expression> PARENT_RIGHT
 <factor> ::= ID | INT | LONG | FLOAT | DOUBLE

Als je wilt, kan ik de Parser ook nog copy pasten (in het allerergste geval). Hier is in ieder geval een deel van de code zodat je ziet waar ik 't over heb (nee, het is geen PHP code, maar de PHP tags geven tenminste highlight).

PHP-code:

[...]
  /**
   * Een fout is opgetreden bij het parsen van de nonterminal.
   * @param nonterminal naam van nonterminal
   * @param message foutmelding
   */
  private void parseError(String nonterminal,String message) {
    System.err.println();
    System.err.println("parse error in <"+nonterminal+"> : "+message);
    System.err.print("lookahead '"+lookahead.getText()+"' ");
    System.err.print("(kind="+lookahead.getKind()+") ");
    System.err.print("at "+lookahead.getLine()+"/"+lookahead.getColumn());
    System.err.println();
    throw new RuntimeException();
  }

  /**
   * Accepteer huidige token van scanner.
   */
  private void acceptIt() {
    try {
      lookahead=scanner.nextToken();
    } catch (IOException exception) {
      exception.printStackTrace();
      throw new RuntimeException();
    }
  }

  /**
   * Accepteer huidige token van scanner, mits deze van een bepaald soort is.
   * @param nonterminal naam van nonterminal
   * @param kind identifatie van token soort
   */
  private void accept(String nonterminal,int kind) {
    if ( lookahead.getKind()!=kind ) {
      parseError(nonterminal,"kind="+kind+" expected");
    } else {
      acceptIt();
    }
    
  }

[...]

  /**
   * Parse het root symbool van de grammatica.
   * @return het resultaat van parsing (in dit geval een string)
   */
  public Object parseRoot() {
    parseExpression();
    //Na parsen van root symbol moet EOF token gescanned worden
    accept("root",EOF);
    //Geef de root van de opgebouwde expressie stack terug
    return pop();
  }

[...]

  /**
   * Push (tekst van) current token op de interne stack.
   */
  private void pushIt() {
    push(lookahead.getText());
  }

  /**
   * Push een object op de interne stack.
   * @param object object dat bovenop de stapel wordt geplaatst
   */
  private void push(Object object) {
    expressionStack.addFirst(object);
  }

  /**
   * Haal bovenste object van de interne stack.
   * @return bovenste verwijderde element
   */
  private Object pop() {
    return expressionStack.removeFirst();
  }

[...]

  /**
   * Parsen van
   *  <factor> ::= PARENT_LEFT <expression> PARENT_RIGHT
   *  <factor> ::= ID | INT | LONG | FLOAT | DOUBLE
   */
  private void parseFactor() {
    switch (lookahead.getKind()) {
      case PARENT_LEFT:
        acceptIt();
        parseExpression();
        accept("factor",PARENT_RIGHT);
        break;
      case ID:
      case INT:
      case LONG:
      case FLOAT:
      case DOUBLE:
        pushIt();
        acceptIt();
        break;
      default:
        parseError("factor","lookahead unexpected");
    }
  } 


Het zou zo ongeveer duidelijk moeten zijn wat de rest van het programma inhoud (namelijk het initialiseren van een LinkedList en een Scanner en methodes voor het parsen van nonterminals).

Ik heb dus ditzelfde idee overggenomen, en dus ook de code. Het enige wat anders is, zijn de methodes voor het parsen van de grammatica (maar dat lijkt mij logisch. ).

Probeer de parser uit de vorige opdracht eens uit met de volgende invoer:

1 - 2 * 3 + 4
1 - 2 * 3 + 4


Als dat geen abend oplevert, zou je eens goed moeten kijken naar de code voor Parser.parseExpressionRest().

Wat is trouwens abend?

Anyway, als ik 1 - 2 * 3 + 4 doe, krijg ik de volgende output:

Tokenkind: 61, token: 1
Tokenkind: 22, token: -
Tokenkind: 61, token: 2
Tokenkind: 23, token: *
Tokenkind: 61, token: 3
Tokenkind: 21, token: +
Tokenkind: 61, token: 4
Tokenkind: -1, token:
Tokenkind: -1, token:
((1-(2*3))+4)

Gaat prima, dus. De grammatica komt wel overeen met jouw assumptie.

<expression> ::= <term> <expression-tail>
 <expression-tail> ::= ε | <plus-expression> | <minus-term>

Ik zou dus naar de code voor parseExpressionTail() moeten kijken.

PHP-code:

  /**
   * Parsen van<br>
   *  <expression-tail> ::= e | <plus-expression> | <minus-term>
   */
  private void parseExpressionTail() {
    switch (lookahead.getKind() ) {
      case PLUS:
        parsePlusExpression();
        break;
      case MINUS:
        parseMinusTerm();
        break;
    }
  } 


En wanneer ik terug ben van school, ga ik verder.
----------------

Hier is onze grammatica:

<syntax> ::= <rule> <followrules>
<followrules> ::= <syntax>
<followrules> ::= ε
<rule> ::= NONTERMINAL DEFINEDAS <production> POINT
<production> ::= <term> OR <alternative>
<production> ::= <term>
<alternative> ::= <production>
<term> ::= <factor> <restterm>
<term> ::= EMPTY
<restterm> ::= <term>
<restterm> ::= ε
<factor> ::= TERMINAL | NONTERMINAL

OK, dat maakt het een stuk duidelijker.


De foutmelding en de abend (= Abnormal End = Abort) genereer je zelf,
doordat je in de 'default'-tak van parseFactor() een aanroep doet van
parseError("factor","lookahead unexpected");

In Parse.parseExpressionTail()
kun je zien hoe de epsilon wordt toegestaan door *geen* exception te forceren in het default-deel.

------

De truc zit hem zo te zien in die lookahead.
Dit kan alleen werken indien je met een enkele lookahead kunt bepalen in welke tak je verder moet (tenzij je voorlopig-ingelezen symbolen kunt terugpushen op de lees-stack.

Ik zal later op de dag nog even kijken hoe dat in onze grammatica ligt

[Rob]

Ohohoh! Hij doet 't nu een beetje!
Ik kan nu <x> ::= <a> parsen met het volgende resultaat:

Tokenkind: 72, token: <x>
Tokenkind: 70, token: ::=
Tokenkind: 72, token: <a>
Tokenkind: -1, token:
Tokenkind: -1, token:

Het parsen van <x> ::= <b> | <c> werkt ook:

)Tokenkind: 72, token: <x>
Tokenkind: 70, token: ::=
Tokenkind: 72, token: <b>
Tokenkind: 71, token: |
Tokenkind: 72, token: <c>
Tokenkind: -1, token:
Tokenkind: -1, token:

Hij gaat wel onderuit met meerdere nonterminals achter elkaar (bijvoorbeeld <x> ::= <a><b>), maar het is een begin.
En een punt aan het einde vindt ie ook niet zo prettig.

Die eerste genereert de volgende fouten:

Tokenkind: 72, token: <x>
Tokenkind: 70, token: ::=
Tokenkind: 72, token: <b>
Tokenkind: 72, token: <a>
Tokenkind: -1, token:

parse error in <rule> : kind=70 expected
lookahead '' (kind=-1) at 2/1
Exception in thread "main" java.lang.RuntimeException
at Parser.parseError (Parser.java:52)
at Parser.accept (Parser.java:74)
at Parser.parseRule (Parser.java:158)
at Parser.parseFollowRules (Parser.java:147)
at Parser.parseSyntax (Parser.java:137)
at Parser.parseRoot (Parser.java:98)
at Main.main (Main.java:14)

Alleen de EOF gaat hier de mist in.

En de laatste genereert het volgende:

Tokenkind: 72, token: <x>
Tokenkind: 70, token: ::=
Tokenkind: 72, token: <b>
Tokenkind: 74, token: .

parse error in <root> : kind=-1 expected
lookahead '.' (kind=74) at 1/12

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

Ik heb het ondertussen al wel met mijn teamgenoot over gehad dat we de grammatica waarschijnlijk het beste in een syntax tree kunnen weergeven.

Rob,


Ik denk dat je eerst de kwestie met de punt moet oplossen.

Dan kun je namelijk zowel
<x> ::= <a> .
als
<x> ::= <a> .
<y> ::= <b> .
parsen.

Dus echt een *willekeurig* aantal rules.

---

Volgend probleem bestaat uit de <term>.
Die bestaat in wezen uit ofwel een epsilon-symbool, ofwel uit 1 of meer <factor>en achter elkaar.


<term> ::= <factor> <restterm>
<term> ::= EMPTY
<restterm> ::= <term>
<restterm> ::= ε

Dus als jouw Parser.parseRestTerm() een lookahead doet, moet hij gewoon checken of dat ingelezen teken in FIRST(<term> zit of in FOLLOWERS(<restterm>).
- In het eerste geval zit je in <restterm> ::= <term>
- In het tweede geval zit je in <restterm> ::= ε

In dat tweede geval voltooi je dus parseRestTerm en parseTerm, zodat je terugkeert in parseProduction().
Als het een OR was ga je verder met het vervolg van parseProduction.
Als het een POINT was voltooi je de parseProduction, verwerk je die POINT, en voltooi je de parseRule.

Vervolgens kom je terug in parseFollowRules().
Daar doe je wederom een lookahead:
- Is het een EOF, dan voltooi je parseFollowRules() en parseSyntax().
- Zo niet, dan roep je de volgende parseSyntax() aan, en van daaruit de volgende parseRule().

---

Bedenk overigens dat met deze grammatica *elke* productieregel moet eindigen met een punt.

Voordeel hiervan is overigens dat je nu zonder problemen een productieregel over meer dan 1 regel moet kunnen inlezen.

Anders krijg je (na de eerste factor) telkens het probleem of de volgende nonterminal
- een volgende <factor> van dezelfde <term> is
- of de NONTERMINAL van de volgende <rule>.

[WelVrolijk]

Tokenkind: 72, token: <x>
Tokenkind: 70, token: ::=
Tokenkind: 72, token: <b>
Tokenkind: 72, token: <a>
Tokenkind: -1, token:

parse error in <rule> : kind=70 expected
lookahead '' (kind=-1) at 2/1
Exception in thread "main" java.lang.RuntimeException

Bij nader inzien is eigenlijk vrij duidelijk wat er hier gebeurt.

De Parser leest:
<x> ::= <b> <a> EOF
En op het moment dat hij EOF leest, verwacht hij Tokenkind 70, oftewel "::=".

De Parser denkt dus, dat <a> het begin is van een <rule>.

---

Bij parseRestTerm() zul je dus *eerst* moeten proberen of het volgende symbool in FIRST(<term>) zit. Pas als dat *niet* het geval blijkt te zijn, mag je aannemen dat je in de andere tak ( <restterm> ::= ε ) zit.

[WelVrolijk]

Tokenkind: 72, token: <x>
Tokenkind: 70, token: ::=
Tokenkind: 72, token: <b>
Tokenkind: 74, token: .

parse error in <root> : kind=-1 expected
lookahead '.' (kind=74) at 1/12

Wellicht ben je aan het eind van je parseRule() een accept(POINT) vergeten.

[Rob]

Eerst die punt kwestie, ja.

WelVrolijk schreef op 01-11-2006 @ 19:24 :
Wellicht ben je aan het eind van je parseRule() een accept(POINT) vergeten.

Ja, maar als ik die toevoeg, lukt 't nog niet echt... Ik heb daar:

PHP-code:

private void parseRule() {
  switch(lookahead.getKind()) {
    case NONTERMINAL:
      acceptIt();
      accept("rule", DEFINEDAS);
      parseProduction();
      accept("point", POINT);
      break;
  }
} 


Dat lookahead gebeuren vind ik eigenlijk maar verwarrend om goed uit te voeren. Gebeurt het ongeveer zo?

Scanner leest <x> ::= <b> . in.

Dan begint de applicatie met Parser.parseRoot().
  Deze roept Parser.parseSyntax() aan.
    Parser.parseSyntax roept Parser.parseRule() aan
      Parser.parseRule() voert een lookahead uit. Het volgende symbool is <x>, 
      een NONTERMINAL. Als er een nonterminal inzit, accept ie deze, dan accept 
      ie het DEFINEDAS symbool, en dan roept ie Parser.parseProduction() aan
        Parser.parseProduction roept Parser.parseTerm() aan.
          Parser.parseTerm() voert een lookahead uit. Het volgende symbool is 
          <b>, een NONTERMINAL. In dit geval, roept ie Parser.parseFactor() aan
            Parser.parseFactor() voert een lookahead uit. Hij ziet <b>, een 
            NONTERMINAL. Hij roept pushIt() en acceptIt() aan, en is klaar.
          Parser.parseTerm() hoeft nu niets meer te doen.
        Parser.parseProduction voert een lookahead uit, ziet dat hij niets te
        doen heeft en is dus klaar
      Parser.parseRule ziet een ., de POINT. hij deot accept("point", POINT), en
      is klaar
    Parser.parseSyntax roept Parser.parseFollowRules() aan
      Parser.parseFollowRules() doet een lookahead, ziet dat ie niets kan doen
      en is klaar
    Parser.parseSyntax is klaar
  Parser.parseRoot doet accept("root", EOF) en is klaar
Applicatie klaar

Zo gaat het geloof ik, maar ik weet het niet zeker. Het is in ieder geval niet goed, want ik heb de volgende error bij het proberen van <x> ::= <b> . :

parse error in <root> : kind=-1 expected
lookahead '.' (kind=74) at 1/12
Exception in thread "main" java.lang.RuntimeException
  at Parser.parseError (Parser.java:52)
  at Parser.accept (Parser.java:74)
  at Parser.parseRoot (Parser.java:100)
  at Main.main (Main.java:14)

[WelVrolijk]

Klopt niet helemaal, maar het zit wel in de buurt.

Ik heb hier niet zoveel ervaring mee, want onze tool werkte (destijds) iets geavanceerder.
(Lees: destijds was het niet mogelijk, ons eerst met het door jullie gebruikte concept (een symbool lookahead) te oefenen, en later met een concept dat "oneindig ver" vooruit kon lezen. Daarom leerden wij dit alleen maar als abstracte theorie, en maakten wij onze oefeningen meteen in CDL2).

Die lookahead hoef je alleen maar te gebruiken als je moet kiezen tussen twee (of meer) alternatieven.

Parser.parseRule() hoeft dus geen lookahead uit te voeren; er zijn namelijk geen alternatieven.

Ik zie in feite 5 keuze-momenten in de grammatica:
1 - in <followrules>
2 - in <production> (maar het lijkt alsof dit niet helemaal volgens de regels is uitgewerkt)
3 - in <term>
4 - in <restterm>
5 - in <factor>

- In geval 5 is het vrij duidelijk wat er moet gebeuren. Als we vooruit lezen, zien we hetzij een terminal, hetzij een nonterminal.
- In geval 3 is het ook duidelijk: Het volgende symbool is ofwel een epsilon-symbool, ofwel iets anders.

In de overige gevallen ligt het iets lastiger.

In geval 1:
- Als het volgende symbool een nonterminal is, moeten we er van uitgaan dat het het begin van een <rule> is.
- Als het volgende symbool een EOF is, zijn we klaar met het parsen van de <followrules>, en dus zijn we klaar met het lezen van de syntax.
- In alle andere gevallen zit er een fout in de invoer.

In geval 4:
- Als het volgende symbool een terminal of een nonterminal is, dan is dat een factor (die het begin is van een term). In dat geval roepen we dus parseFactor aan. Merk echter op, dat we die factor reeds ingelezen hebben met die lookahead!
- Anders sluiten we restterm en term af.

In geval 3 (huidige vorm):
Nadat we met succes een <term> hebben gelezen, doen we een lookahead.
- Als het volgende symbool een OR is, verwerken we die etc.
- Anders sluiten we de productie af; het volgende teken dat (in parseRule() ) verwerkt moet worden, is een POINT. Merk echter op, dat we die reeds ingelezen hebben met die lookahead!

[Rob]

...Hij parsed 'em al. Weet je waarom ie het niet deed? Ik had een accolade teveel in die switch.
1 accolade!

Wat mij opviel, was dat ie niet compile fouten gaf, maar netjes (nouja, netjes...) doorging.

Anyway, na het wegwerken van de switch in parseRule(), voldeed ik al aan het feit dat switches alleen bij die andere vijf methodes aanwezig moesten zijn.

- In geval 5 is het vrij duidelijk wat er moet gebeuren. Als we vooruit lezen, zien we hetzij een terminal, hetzij een nonterminal.

Yup, dat had ik al. De code die ik heb is:

PHP-code:

private void parseFactor() {
  switch(lookahead.getKind()) {
    case NONTERMINAL:
    case TERMINAL:
      pushIt();
      acceptIt();
      break;
    default:
      parseError("factor", "lookahead unexpected");
      break;
  }
} 


In geval 1:
- Als het volgende symbool een nonterminal is, moeten we er van uitgaan dat het het begin van een <rule> is.
- Als het volgende symbool een EOF is, zijn we klaar met het parsen van de <followrules>, en dus zijn we klaar met het lezen van de syntax.
- In alle andere gevallen zit er een fout in de invoer.

Aye, dat had ik ook al. Code:

PHP-code:

private void parseFollowRules() {
  switch(lookahead.getKind()) {
    case NONTERMINAL:
      parseRule();
      break;
  }
} 


In geval 4:
- Als het volgende symbool een terminal of een nonterminal is, dan is dat een factor (die het begin is van een term). In dat geval roepen we dus parseFactor aan. Merk echter op, dat we die factor reeds ingelezen hebben met die lookahead!
- Anders sluiten we restterm en term af.

Had ik ook.

PHP-code:

private void parseRestTerm() {
  switch(lookahead.getKind()) {
    case TERMINAL:
    case NONTERMINAL:
      parseFactor();
      break;
  }
} 


In geval 3 (huidige vorm):
Nadat we met succes een <term> hebben gelezen, doen we een lookahead.
- Als het volgende symbool een OR is, verwerken we die etc.
- Anders sluiten we de productie af; het volgende teken dat (in parseRule() ) verwerkt moet worden, is een POINT. Merk echter op, dat we die reeds ingelezen hebben met die lookahead!

Werkt nu ook, gok ik? Hij kan in ieder geval iets als <x> ::= <a> | <b>. en <x> ::= ε | <b>. netjes parsen zonder errors. Alhoewel ie niet precies doet wat ie hoort te doen (hij ziet ε als een terminal en geeft het het terminal token, terwijl ie een EMPTY token moet geven? Of klopt dat niet en is ε gewoon een terminal?)

PHP-code:

private void parseTerm() {
  switch(lookahead.getKind()) {
    case EMPTY:
      acceptIt();
      pushIt();
      parseProduction();
      break;
    default:
      parseFactor();
      break;
  }
} 


Ik heb Parser.parseProduction als volgt gedaan: Hij parsed sowieso als eerste een term mbv parseTerm(); (immers: <production> ::= <term> | <term> OR <alternative>).
Daarna volgt er of niets (dus gewoon geen input) of een OR symbool. Ik heb op basis daarvan mijn (voor zover ik weet incorrecte) switch gemaakt:

PHP-code:

private void parseProduction() {
  parseTerm();
  switch(lookahead.getKind()) {
    case OR:
      acceptIt();
      parseAlternative();
      break;
    case EMPTY:
      acceptIt();
      parseFactor();
      break;
  }
} 


Hij kan dus nu in ieder geval die punt netjes parsen, en de OR terminal, en ε. Volgende doel is het parsen van iets als <x> ::= <a><b>.

Daar krijg ik nu de melding dat ie een punt (kind=74) verwacht na de nonterminal en dat ie een nonterminal (kind=72) krijgt.

TokenKind: 72. token: <x>
TokenKind: 70. token: ::=
TokenKind: 72. token: <a>
TokenKind: 72. token: <b>

parse error in <rule> : kind=74 expected
lookahead '<b>' (kind=72) at 1/12
Exception in thread "main" java.lang.RuntimeException
  at Parser.parseError (Parser.java:52)
  at Parser.accept (Parser.java:74)
  at Parser.parseRule (Parser.java:158)
  at Parser.parseSyntax (Parser.java:136)
  at Parser.parseRoot (Parser.java:98)
  at Main.main (Main.java:14)

Van wat ik hier kan zien, is parseRule() nog niet goed, correct?

En ik ga nu bed in. Morgen twee tentamens, waaronder dit vak...

[WelVrolijk]

Die parseTerm() is niet correct.

Je schrijft:

PHP-code:

private void parseTerm() { 
  switch(lookahead.getKind()) { 
    case EMPTY: 
      acceptIt(); 
      pushIt(); 
      parseProduction(); 
      break; 
    default: 
      parseFactor(); 
      break; 
  } 
} 


Maar dat komt overeen met:
<term> ::= EMPTY <production>
<term> ::= <factor>

We moeten echter hebben:
<term> ::= <factor> <restterm>
<term> ::= EMPTY

Dus in beide takken is iets mis.

---

Vanwege <term> ::= <factor> denkt de parser na <x> ::= <a> dat de <term> compleet is ingelezen.
Hij returnt naar parseProduction, ziet geen OR, dus <production> is blijkbaar compleet ingelezen.
Hij returnt naar parseRule, en verwacht dus een POINT.
En dat is precies de foutmelding die je krijgt.

Je programma *denkt* dat de fout in parseRule() zit.
Met andere woorden: jouw programma denkt, dat <x> ::= <a><b> in strijd is met de productieregels voor <rule>
De fout zit echter in parseTerm().

[Rob]

Krijg nou wat. Ja, ik dacht een beetje scheef daar... Ik dacht dat na een EMPTY een <production> kwam (wtf?), maar eigenlijk komt er na een EMPTY of een OR (immers: <term> ::= EMPTY, <production> ::= <term> OR <alternative> wat EMPTY OR <alternative> geeft) of een POINT.

Dus ik hoef eigenlijk helemaal niets te doen als ie een EMPTY tegenkomt (behalve accepten, eigenlijk).

Hij parsed 'm nu dan ook. Maar als ik iets als <x> ::= <b><c><d><e>. doe, dan verwacht ie na <d> een punt. Hij's toch nog niet helemaal lekker. Volgens het programma zou de error in parseRule() moeten zitten... Maar na je voorbeeld van daarnet, weet ik dat niet zeker.

Maar het komt er op neer da hij maar 4 nonterminals achter elkaar aankan voor die ermee stopt (dan verwacht ie dus een .).