Scanners & Parsers (SEP)

[Scare360]

Momenteel ben ik begonnen aan een vak Scanners & Parsers (SEP), hogere informatica. Nu is de lesstof van dat moduul wel zo gigantisch bagger dat ik op zoek ben naar wat alternatieven. Op internet is nagenoeg niets bruikbaars te vinden.

Als studie-materiaal gebruik ik nu Compilers, their design and construction using pascal van Robin Hunter, maar das wel zo'n rukboek dat wil je gewoon niet eens inzien.

Op internet heb ik dit gevonden http://www.cs.wisc.edu/~bodik/cs536.html maar das ook niet bepaald helder en gestructureerd.

Mijn probleem. Het scan-pars idee is geen probleem. De kennis op het gebied van state-machines, determinisme, reguliere expressies is aanwezig. Ik loop eigenlijk direct vast bij het begrip productieregels bv

code:

G2=({a},{S,N,Q,R},P,S)

?

S->QNQ
QN->QR
RN->NNR
RQ->NNQ
N->a
Q->E

Zou iemand me op weg willen helpen?

bvd: ps ik heb dus alles al afgezocht dus een search is voor mij geen oplossing meer

[TheDancer]

Hmm, wil je nu dat we je uitleggen wat productieregels zijn, of wil je een link naar een boek??

Uitleggen kan ik nu wel een (simpel) begin mee maken, maar voor een goed boek moet ik thuis even kijken. Ik heb een engelstalig boek wat ze op TU/e gebruik(t)en liggen... Titel moet ik dus even opzoeken...

offtopic:
Waar zit je op het HBO?? Fontys Eindhoven?

[Nappa]

Op woensdag 19 juni 2002 14:50 schreef paulgielens het volgende:

code:

G2=({a},{S,N,Q,R},P,S)



?



S->QNQ

QN->QR

RN->NNR

RQ->NNQ

N->a

Q->E

Even een snelle introductie:
G2 is de naam an de grammatica, waarin {a} de terminals zijn (dit zijn de eind symbolen waaaruit een grammatica bestaat); S,N,Q,R zijn de nonterminals; dit zijn de tussensymbolen, die je gebruikt om uiteindelijk je woorden te maken. P geeft de productieregels aan, die je daaronder hebt staan, en S is het startsymbool daar begin je mee als je een woord uit deze grammatica wilt maken.
In dit geval kun je dus bijvoorbeeld krijgen:

code:

S = (productieregel S->QNQ)
=
QNQ
= ( QN->QR)
QRQ
= ( RQ -> NNQ )
QNNQ
= (etcetera)

[Alarmnummer]

volgens mbravenboer is deze erg goed. Ik heb er zelf nog niet naar gekeken.

de namen type en variable_declaration voor het '=' teken zijn productie regels. IDENT en SEMI_COLON zijn terminals (tokens die van je lexer komen) en type in variable_declaration is een non terminal (omdat het een verwijzing is naar de productie regel: type).

code:

type
    = IDENT
    ;

variable_declaration
    = IDENT type SEMI_COLON
    ;

Ik heb zelf intussen al redelijk ervarig met parsers, maar ik heb net een paar week 'Modern Compiler Implementations in Java' binnen, en ik vind het echt een aanrader. Hier staan LL en LR grammatica`s in uitgelegd en nog veel meer. Dit is zeker geen miskoop.

[Nappa]

Trouwens, aangezien E niet in de lijst voorkomt neem ik aan dat die E staat voor epsilon, oftewel een 'lege string'. Als je mn vorige uitwerken voortzet zou je dus door Q->E en N->a te gebruiken bij QNNQ uitkomen op het woord 'aa'.

[Alarmnummer]

Maar gebruik je een parser generator of ben je een die hard, en ga je zelf een lexer en een parser schrijven?

[mbravenboer]

Alarmnummer: volgens mbravenboer is deze erg goed. Ik heb er zelf nog niet naar gekeken.

Die wilde ik net gaan posten .

Dit docje geeft inderdaad in de eerste paar hoofstukken een goede introductie in talen, zinnen, grammatica's, context-vrije grammatica's, productie-regels, non-terminals en terminals. Ik denk dat je hier wel wat aan hebt.

Overigens zijn er ook nog meer dan genoeg goede boeken:

Aho, Sethi en Ullman: Compilers, Principles, Techniques and Tools gaat voor een aardig deel over parsing technieken en context-vrije grammatica's. Dit is zo'n beetje 'het' klassieke werk op het gebied van compilerbouw, dus ik denk dat je daar sowieso altijd nog wat aan hebt.

Verder zijn er ook wel hele boeken geschreven over deze parsing en dergelijke, maar die heb ik niet op m'n plank staan en dus kan ik ze ook niet goed beoordelen.

ik heb net een paar week 'Modern Compiler Implementations in Java' binnen, en ik vind het echt een aanrader. Hier staan LL en LR grammatica`s in uitgelegd en nog veel meer. Dit is zeker geen miskoop.

Inderdaad, dat is ook een goed boek, waar ook het een en ander over grammatica's, parser-generators en automaten ter sprake komt.

Wellicht helpt het nog het meest als je er gewoon eens mee gaat spelen zodat je een gevoel krijgt voor wat het nu eigenlijk allemaal is: pak gewoon eens een parser-generator en pruts er eens wat mee .

[Scare360]

tjezus wat een snelle reacties! bedankt!

TheDancer
Yep HIO aan de fontys in eindhoven, waar men het niet nodig vind studenten te motiveren met goede structurele colleges en lesmateriaal, maar gewoon voor de makkelijke weg kiezen en zomaar wat in een dictaat pleuren.

Nappa
Bedankt voor je uitleg, maar ik vat het concept niet denk ik wellicht dat de theorie beter valt

Alarmnummer & mbravenboer
bedankt voor dat document...eens kijken (wel bagger dat de laatste psghost niet backwards compatible is)

[Alarmnummer]

Ik kan hem je wel in pdf formaat toesturen.

[Scare360]

Op woensdag 19 juni 2002 15:52 schreef Alarmnummer het volgende:
Ik kan hem je wel in pdf formaat toesturen.

heb ff een oude versie geinstalleerd, zodat ik deze alsnog kan bekijken en converteren etc. Toch bedankt voor de aanbieding!

[Alarmnummer]

Op woensdag 19 juni 2002 15:57 schreef paulgielens het volgende:

[..]

heb ff een oude versie geinstalleerd, zodat ik deze alsnog kan bekijken en converteren etc. Toch bedankt voor de aanbieding!

Heb je net een url gestuurt waar je hem kan downen

[Scare360]

Op woensdag 19 juni 2002 15:58 schreef Alarmnummer het volgende:

[..]

Heb je net een url gestuurt waar je hem kan downen

waar dan?

niet op [e-mail] iig, want daar is ie nog niet binnen.

[TheDancer]

Op woensdag 19 juni 2002 15:49 schreef paulgielens het volgende:

TheDancer
Yep HIO aan de fontys in eindhoven, waar men het niet nodig vind studenten te motiveren met goede structurele colleges en lesmateriaal, maar gewoon voor de makkelijke weg kiezen en zomaar wat in een dictaat pleuren.

Yep, I know it all.... Zit er ook. 25 juni moet ik mijn praatje houden...

Wie is je docent?? v/d Hooven?
Die heb ik mijn boek laten zien waarmee ik op de TU/e een (slechts gedeeltelijk gelijk) vak heb gehaald, omdat ik ook vond dat het studiemateriaal crap was... Ik stelde toen voor om dat boek dan maar te gebruiken want hij was zo onder de indruk van het boek dat hij spontaan vrijstelling gaf

Maar als ik het goed begrijp hebben ze er dus niets van geleerd.

edit:

Hmm, misschien een beetje Offtopic, maar toch...

[mbravenboer]

Waarom post je hier trouwens zo'n vaag voorbeeld met Qs, Ns en dergelijke? Staan er in je literatuur geen praktische voorbeelden voor bijvoorbeeld expressies? Ik kan me eigenlijk niet voorstellen dat het idee niet overkomt bij jou als je een voorbeeldje ziet met optelling, vermenigvulidingen, integer literals en dergelijke.... Dat het idee niet overkomt met deze vage voorbeelden kan ik goed begrijpen .

[Scare360]

Op woensdag 19 juni 2002 16:11 schreef TheDancer het volgende:

[..]

Yep, I know it all.... Zit er ook. 25 juni moet ik mijn praatje houden...

Wie is je docent?? v/d Hooven?
Die heb ik mijn boek laten zien waarmee ik op de TU/e een (slechts gedeeltelijk gelijk) vak heb gehaald, omdat ik ook vond dat het studiemateriaal crap was... Ik stelde toen voor om dat boek dan maar te gebruiken want hij was zo onder de indruk van het boek dat hij spontaan vrijstelling gaf

Maar als ik het goed begrijp hebben ze er dus niets van geleerd.

edit:

Hmm, misschien een beetje Offtopic, maar toch...

Om het ff concreet uit te leggen... onze docent is de heer cats (waarschijnlijk omdat ze DW5 en SEP samen willen voegen en de vakdocenten op het nieuw materiaal zetten). Tijdens mijn colleges is hij na 2 colleges maar voor de rest afwezig gebleven. Nu zitten wij dus met de problemen! Wij hebben zon gele reader waarin ze dus "Compilers and there design and construction using pacal, by Robin Hunter" gecopieerd hebben.

Dat boek is dus toetaal niet te volgen omdat de schrijver enorm veel onnodige intermezzo's toevoegd over de goede oude tijd terwijl het naar mijn inziens noodzaak is de essentie boven tafel te krijgen ipv de lezer continue te laten afdwalen. Tis toch al pittige stof als je het mij vraagt.

Nu heb ik dus vrijdag tentame dag wat ik hoogstwaarschijnlijk toch oversla, maar toch zal ik dat vak eens moeten halen, vandaar mijn post

[Alarmnummer]

Ik denk dat jullie veel HBO instellingen niet goed begrijpen. Het gaat erom dat je van veel dingen niet veel opsteekt, ipv een paar dingen goed leert te beheersen. HBO zuigt IMHO. Er zijn bij ons op school een aantal docenten die naar mijn mening streng genoeg zijn en de vereiste kennis eisen en gewoon niet genoegen nemen met minder. Helaas is mijn favoriet (Theo Sinema) vorig jaar op pensioen gegaan Gelukkig zijn er nog een aantal andere die niet zo slap lesgeven.

[Scare360]

Op woensdag 19 juni 2002 16:15 schreef mbravenboer het volgende:
Waarom post je hier trouwens zo'n vaag voorbeeld met Qs, Ns en dergelijke? Staan er in je literatuur geen praktische voorbeelden voor bijvoorbeeld expressies? Ik kan me eigenlijk niet voorstellen dat het idee niet overkomt bij jou als je een voorbeeldje ziet met optelling, vermenigvulidingen, integer literals en dergelijke.... Dat het idee niet overkomt met deze vage voorbeelden kan ik goed begrijpen .

Nou dit is dus echt "de stof" op deze wiskundige wijze wordt ook van de student verwacht deze uit te werken in opgaves. Tentame opgaves worden dus in dermate abstracte vorm gepresenteerd dat de leraar de enige is die weet waar het over gaat School tell me about it.

[Alarmnummer]

Je moet even een wat duidelijker voorbeeld gaan maken en je kan altijd nog overstappen op abstracter. Maar als je een concreet voorbeeld hebt kan jeje er iets bij voorstellen en dat kan het in het begin een stuk makkelijker maken. Kijk maar eens naar mijn vb grammatica waar ik een Variable declaratie doe. Dat is toch duidelijk?

[Scare360]

Op woensdag 19 juni 2002 16:20 schreef Alarmnummer het volgende:
Ik denk dat jullie veel HBO instellingen niet goed begrijpen. Het gaat erom dat je van veel dingen niet veel opsteekt, ipv een paar dingen goed leert te beheersen. HBO zuigt IMHO. Er zijn bij ons op school een aantal docenten die naar mijn mening streng genoeg zijn en de vereiste kennis eisen en gewoon niet genoegen nemen met minder. Helaas is mijn favoriet (Theo Sinema) vorig jaar op pensioen gegaan Gelukkig zijn er nog een aantal andere die niet zo slap lesgeven.

Naja ik ben niet iemand die snel een leraar de schuld ergens van geeft, zodra je gaat werken heb je ook de kantjeslopers die je het leven zuur maken.

Tja op deze manier wordt je ook wel weer gestimuleerd om een beetje innovatief met het materiaal om te gaan. En ikke maar typen terwijl de printer rammelt

[edit]
Ja het concept is duidelijk, ook heb ik al een simpele scanner parser geschreven mbv een deterministische (logisch) state machine. Een hele eenvoudige grammatica beschreven etc. De clau van school is sommetjes maken en daar breekt het bij mij op dit moment.

[Alarmnummer]

Het principe is hetzelfde, maar ik vind die voorbeelden in sommige boeken ook vervelend om te lezen omdat je iedere keer vergeet wat een bepaalde productie regel inhoud (Wat zegt Q me nou) en daardoor heb je ook minder snel een totaal beeld wat er gebeurd. En wat ik ook vaak rond uitslecht/achterhaald vind is dat je niet kan zien of je een terminal of een non terminal te pakken hebt. In mijn voorbeeld heb ik de terminals met hoofdletters geschreven (doen ze bij ANTLR ook) en dat werkt erugh fijn. Ik gebruik nu SableCC als parser generator en daar heb je dat onderscheid niet. Ik vind dit wel een beetje jammer en het je verliest daardoor toch een stukje duidelijkheid.

Ik zou zeggen: ga eens met een 'echte' grammatica wat rommelen en dan kan je ook snel genoeg met een abstracte aan de slag omdat je dan alle/veel kreten al beheerst.

[TheDancer]

Op woensdag 19 juni 2002 16:17 schreef paulgielens het volgende:

Om het ff concreet uit te leggen... onze docent is de heer cats (waarschijnlijk omdat ze DW5 en SEP samen willen voegen en de vakdocenten op het nieuw materiaal zetten). Tijdens mijn colleges is hij na 2 colleges maar voor de rest afwezig gebleven. Nu zitten wij dus met de problemen! Wij hebben zon gele reader waarin ze dus "Compilers and there design and construction using pacal, by Robin Hunter" gecopieerd hebben.

Hmm, da's jammer dat je daar nu pas mee komt.... Dit moet je onder de aandacht brengen van Paul Guit ofzo... Die had er iets aan kunnen doen...
(Misschien alsnog voor de volgende keer??)

Op woensdag 19 juni 2002 16:17 schreef paulgielens het volgende:

Nu heb ik dus vrijdag tentame dag wat ik hoogstwaarschijnlijk toch oversla, maar toch zal ik dat vak eens moeten halen, vandaar mijn post

Een tip: Ga wel naar het tentamen! Om twee redenen:

1) Een 4 of 5 kan voldoende zijn (ivm minpunten die je mag hebben)
2) Tentamens zijn vaak hetzelfde van opzet. Dan heb je de volgende keer een goed voorbeeld....

[Scare360]

Op woensdag 19 juni 2002 16:31 schreef TheDancer het volgende:

[..]

Hmm, da's jammer dat je daar nu pas mee komt.... Dit moet je onder de aandacht brengen van Paul Guit ofzo... Die had er iets aan kunnen doen...
(Misschien alsnog voor de volgende keer??)
[..]

Een tip: Ga wel naar het tentamen! Om twee redenen:

1) Een 4 of 5 kan voldoende zijn (ivm minpunten die je mag hebben)
2) Tentamens zijn vaak hetzelfde van opzet. Dan heb je de volgende keer een goed voorbeeld....

cats kwam in week 7 opdagen en zij dat we het vak makkelijk eigen hadden kunnen maken middels zelfstudie. Hij vond het vreemd dat we de stof van week 3 niet hadden bestudeerd... ja duh mr de rand* mzzl zoek het maar uit zeggen we dan.

Tentame ophalen kan ik wel eens doen. Kan ik lekker op Tenerife eens wat nuttigs doen. Op het strand liggen maffen is gewoon geen doen voor een IT'er.

[Scare360]

ok concreet opg 2.6

X={a}

S->E
S->aS

een string zou E, a, aa, aaa, aaaa, a^n

maar

X={a,b}

S->E
S->XS
X->a|b

na deze opgave ben ik hem kwijt...

S->E
S->aAb
A->b

zou denken... S produceert terminal a tjes, waarop A ternimal b'tjes produceerd dus,

L= E, ab, abab, abab, ababab, ab^n

Ik wordt gek, kan iemand dit eens wat simpeler uitleggen? Grammatica wil er nog niet zo in denk ik

[Alarmnummer]

S->E //is een lege string
S->XS //is dus een a of een b met daarachter S
X->a|b //a of een b.

Je kan hier dus een willekeurig lange reeks met a`s en b`s maken. E,a,b,aa,ab,ba,bb,etc etc etc

S=(a|b)* //andere notatie.

'|' is dus een of, maar dat wist je al
'*' is 0..n keer
'+' is 1..n keer
'?' is optioneel

dit is trouwens EBNF.


[edit] ik zie nog een opgave staan:
S->E
S->aAb
A->b

oplossing:
E, abb
(volgens mij heb je het voorbeeld verkeerd overgeschreven, want deze was te makkelijk )

ps: ben ervan uitgegaan dat S de Start productie regel is, maar anders moet je die 2e oplossing ook nog ff 'b' toevoeren.

[Nappa]

Op woensdag 19 juni 2002 19:16 schreef paulgielens het volgende:
na deze opgave ben ik hem kwijt...

S->E
S->aAb
A->b

zou denken... S produceert terminal a tjes, waarop A ternimal b'tjes produceerd dus,

L= E, ab, abab, abab, ababab, ab^n

Ik wordt gek, kan iemand dit eens wat simpeler uitleggen? Grammatica wil er nog niet zo in denk ik

Het is niet zo moeilijk als je denkt hoor
Start symbool S produceert of E, of aAb.
In dat 2e geval is de enige productieregel voor A die je kunt kiezen A->b.
De taal die deze grammatica dan construeert bestaat dus ook alleen maar uit de woorden E en aab.
De taal L die jij dénkt dat ie beschrijft kan weer als volgt:
S -> E | abS
In dit geval kun je S namelijk weer vervangen voor abS, en elke keer dat je dat doet wordt er dus een substring 'ab' voor het tot dan ontstane woord geplakt. Of om dit even te illustreren:
S => abS => ababS => abababS
En als je genoeg 'ab'-tjes hebt dan kies je de epsilon productie.

[SiNisTrAD]

phew ik ben blij dat dit vorig jaar heb gehaald (ook van cats, jaja maandag het 8e en 9e uur !!!) helaas voor jou heb ik alle lesstof weer verdrongen. Maarja het HBO is nog heilig tov het MBO die ik ook heb gevolgd .. dat was pas triest.

Succes iig vrijdag!

[Parcye]

Ben blij dat ik dit NA de vakantie heb

Geeft Aarts dat vak niet, dat is tenminste een goede docent...

Heb morgen alleen nog CSA... effe mn 10 veilig stellen

Maar deze thread ga ik toch even opslaan

[Alarmnummer]

Op woensdag 19 juni 2002 22:23 schreef Nappa het volgende:

[..]

Het is niet zo moeilijk als je denkt hoor
Start symbool S produceert of E, of aAb.
In dat 2e geval is de enige productieregel voor A die je kunt kiezen A->b.
De taal die deze grammatica dan construeert bestaat dus ook alleen maar uit de woorden E en aab.

abb Je hebt per ongeluk een a op de 2e plaatst gezet terwijl dit een b moet zijn (namelijk van A) Wat een slechte namen zeg, geen wonder dat het zo lastig is.

De taal L die jij dénkt dat ie beschrijft kan weer als volgt:
S -> E | abS

Of je gebruikt EBNF:
S -> (ab)*

[Verwijderd]

beetje offtopic maar ik vraag me even af:

hoeveelstejaars ben je topicstarter? ff om te vergelijken met de TU/e

[Scare360]

ja tis wel duidelijk ondertussen...

X={a,b}

S->E
S->XS
X->a|b

bovenstaand is de X een hulp non-terminal die ik introduceer. Dit om een herhalingspatroon in de grammatica mogelijk te maken, dus S produceerd E, aaaaa'tjes, bbbbbb'tjes of een combinatie ababababbbaabbaaabbba whatever.

Sanners en Parsers is blok 10 volgens mij, dus dat deed ik in het eerste kwartaal van het 2'e schooljaar. Of zou moeten hebben

Parcye: volgend jaar...dit vak werd toch samegevoegd met DW5? SEP & DW5 als 1 vak...dus als dit vak volgend jaar nog gewoon in de oude stijl wordt gegeven hoor ik dat graag van je. Trouwens van mijn lichting is er bijna niemand die dit vak gehaald heeft.

Ik denk dat dat boek wat in dit draadje gepost is een waardige aanvulling is! Mochten hier studenten van de HIO ronddwalen, een aanrader dus!