LL(1) Parser

[Scare360]

Stel gegeven:

De grammatica G=({a,b,c,d},{A,B,S},P,S) met
P = {S->ABd|bSa, A->cA|E, B->aBb|E}

Is dit een LL(1)-grammatica?


Omdat A, B beide E kunnen produceren moet ik zien te achterhalen vanuit welk symbool A vervangen kan worden door een E.

Nu geeft men: FOLLOW(A) = {a,d}, FOLLOW(B ) = {b,d}

Vanuit hier kan men weer Director Symbols afleiden...

Probleem:
Ik snap de methodiek voor het vinden van de FOLLOW niet, de defenitie luidt als volgt:

FOLLOW(A)={x|xET ^ S =>*wAy ^ xE FIRST(y)}

Wie o wie, kan mij in plain nederlands uitleggen hoe die FOLLOW defenitie te gebruiken om de FOLLOW(productieregel) te vinden?

[Parcye]

TSP mooi vak!

Jij zegt : omdat A en B beide E kunnen produceren...
maar is het niet zo dat E de lege string is en je dus moet kijken naar wat de opvolgers zijn van een A en B?

Opvolgers van A
B

Dus waar kan een B mee beginnen?
a
En wat kan de B opvolgens in dien leeg?
d
b

Opvolgers van B
b
d

Dus een E bij A levert of een a,b,d
En een E bij B levert een b,d

Of ben ik er al weer te ver uit?

[Zoijar]

Ik kan het wel uitleggen, maar als je even op google "parsing follow set" intyped, dan krijg je meteen al een match die het uitlegt met code algoritme.
In feite ga je alle alternative tails na, en wanneer gevolgd wordt door 'leeg' kan het gevolgd worden door alles wat de regel zelf volgt (recursief). Zal een closure algoritme moeten schrijven.

[Scare360]

In mijn antwoorden wordt voor FOLLOW(A)={a,d} gegeven.

Die b vonnik ook al vreemd dat die niet meegenomen is in het antwoord...vaag, misschien dat wat meer voorbeelden bekijken daar duidelijkheid in kan brengen.

[Parcye]

Welke school? en als het Eindhoven is, welke leraar?

[Scare360]

HIO, cat

[drm]

Parcye:
Welke school? en als het Eindhoven is, welke leraar?

paulgielens:
HIO, cat

ontopic blijven, ajb

[Parcye]

Theo Cats zou dat haar fijn kunnen uitlegen

Heb je de proeftentamens? En zo ja, wist jij dat er op t Fontys Eindhoven 2 versies van het dictaat rond gaan en daarom je antwoorden misschien niet kloppen.

[Scare360]

Gebruik versie 1, ja oefententames heb ik ook... pruts nog wel een beetje verder.

[drm]

mja, op deze manier leidt dit dus nergens toe. We gaan hier niet een beetje dictaten en oefententamens van school bespreken.