Parser schrijven

[Slagroom]

Hallo,

Hoe kun je een parser schrijven die een scipt iutvoert. Ik heb bijvoorbeeld dit:

code:

$bericht = "Hallo";
print $bericht;

Ik heb echt helemaal geen idee hoe dit werkt maar ik ben er wel nieuwsgierig naar...

En ook, hoe maakt men bijvoorbeeld een compiler als er nog geen compiler is, met assambly, ok, maar wat deden ze toen er nog geen assambler was, alles in nulletjes en eentjes programmeren?

[Verwijderd]

Staat allemaal uitgelegd in dit (enigsinds droge) standaard werkje over compilerbouw:

Aho, Sethi, and Ullman, "Compilers: Principles, Techniques, and Tools,"
Addison Wesley, 1986, ISBN 0-201-10088-6, the "dragon book".

[Slagroom]

Ha ha, da's analoog, is er ook iets in digitaal formaat?

Iets als 'Teach yourself making a compiler in 2 minutes'

[Verwijderd]

Je parsed eerst expressies in een boom. Simpele vormen hiervan zijn berekeningen: 2 + 3 * 5

code:

    +
   / \
  2   *
     / \
    3   5

Zodra je zo'n expressie in een boom geparsed hebt is het uitrekenen niet zo'n probleem. Maar eerst moet je een syntax definieren. Bijvoorbeeld:

code:

expressie ::= term addop term
addop     ::= '+' | '-'
term    ::= factor mulop factor
mulop     ::= '*' | '/'
factor    ::= '(' expressie ')' | getal

Op deze manier beschrijf je de syntax van een numerieke expressie. Met deze notatie geef je ook prioriteiten aan, immers 1 + 2 * 3 wil je als 1 + (2 * 3) parsen en niet als (1 + 2) * 3. Ik kan je wel een java voorbeeldje geven (ik ben er zelf ook mee bezig namelijk). Maar ik weet niet of je daar iets aan hebt. Het is typisch iets dat je tijdens de studie informatica krijgt.

[Verwijderd]

Op maandag 25 februari 2002 16:50 schreef Monstar.nl het volgende:
Ha ha, da's analoog, is er ook iets in digitaal formaat?

[vertaling]
Hahah dat moet ik betalen, kan ik niet ergens gratis een e-book downloaden?"
[/vertaling]

[Slagroom]

Op maandag 25 februari 2002 16:50 schreef Zef het volgende:
[...]

Hee cool, je mag het me wel mailen als je wilt, [e-mail]

[Slagroom]

Op maandag 25 februari 2002 16:51 schreef Yarvieh het volgende:

[..]

[vertaling]
Hahah dat moet ik betalen, kan ik niet ergens gratis een e-book downloaden?"
[/vertaling]

Ha ha ha! Zit een stukje waarheid in... eigelijk, ja, je hebt gelijk!

[Verwijderd]

Op maandag 25 februari 2002 16:53 schreef Monstar.nl het volgende:
Ha ha ha! Zit een stukje waarheid in... eigelijk, ja, je hebt gelijk!

Cheap bastard!

Het dragon book staat nergens dat ik weet gratis online maar hier wat andere online references

http://dynodonalies.com/tutorials/compiler/frame_index.htm
http://www.google.com/search?sourceid=navclient&q=writing+a+compiler

[Verwijderd]

Met Haskell kan je tamelijk eenvoudig je eigen compiler schrijven die een zin in natuurlijke taal parsed naar een bepaald datastructuur. Ik heb dit net op de Universiteit moeten mogen doen, en met Haskell viel het reuze mee . Mooi taaltje hiervoor .

[Alarmnummer]

EBNF is ook uitstekend geschikt om parsers in te schrijven. Ik gebruik ANTLR als parser generator. Ik schrijf mijn taal in ebnf met wat inline java, parser generator erover en voila een parser.

[Verwijderd]

Of YaCC (Yet another Compiler Compiler) natuurlijk

[Alarmnummer]

Op maandag 25 februari 2002 16:50 schreef Zef het volgende:
Je parsed eerst expressies in een boom. Simpele vormen hiervan zijn berekeningen: 2 + 3 * 5

code:

    +
   / \
  2   *
     / \
    3   5

Zodra je zo'n expressie in een boom geparsed hebt is het uitrekenen niet zo'n probleem. Maar eerst moet je een syntax definieren. Bijvoorbeeld:

code:

expressie ::= term addop term
addop     ::= '+' | '-'
term    ::= factor mulop factor
mulop     ::= '*' | '/'
factor    ::= '(' expressie ')' | getal

Op deze manier beschrijf je de syntax van een numerieke expressie. Met deze notatie geef je ook prioriteiten aan, immers 1 + 2 * 3 wil je als 1 + (2 * 3) parsen en niet als (1 + 2) * 3. Ik kan je wel een java voorbeeldje geven (ik ben er zelf ook mee bezig namelijk). Maar ik weet niet of je daar iets aan hebt. Het is typisch iets dat je tijdens de studie informatica krijgt.

expressie
: term (addop term)*

addop
: '+'
| '-'

term
: factor (mulop factor)*

mulop
: '*'
| '/'

factor
: '(' expressie ')'
| getal

Je bent de herhalingen vergeten anders zou je bv geen
1+1+1+.... kunnen krijgen. En het is wat je op je studie hoort te krijgen, maar denk niet dat er veel HTS`ers zijn die een parser kunnen schrijven.

[Verwijderd]

Ja klopt, was ik vergeten. Nee op de HTS misschien niet, maar op de universiteit (mijn universiteit) iig wel.

[Alarmnummer]

En kan YACC ook LLK grammatica`s aan?

bv

mooie_regel
: A B
| A
;

De parser kan niet bepalen welke regel hij in moet (ambiguiteit). Bij antlr kan je syntactische predicaten opgeven:

mooie_regel
: ( A B )=>A B
| A
;

Dit is superpraktisch in wat lastigere grammatica`s.

Je kan zelfs semantische predicaten opgeven.

mooie_regel_2
: {isHetMooiWeer()}=> A B
| A
;

[Verwijderd]

Op maandag 25 februari 2002 17:08 schreef Alarmnummer het volgende:
EBNF is ook uitstekend geschikt om parsers in te schrijven.

EBNF is toch gewoon de standaard om grammatica's voor gewone mensen in op te schrijven

[Alarmnummer]

Op maandag 25 februari 2002 17:15 schreef Zef het volgende:
Ja klopt, was ik vergeten. Nee op de HTS misschien niet, maar op de universiteit (mijn universiteit) iig wel.

Ik zit over een dikke jaar ook weer op jouw universiteit

[Alarmnummer]

Op maandag 25 februari 2002 17:20 schreef KoenM het volgende:

[..]

EBNF is toch gewoon de standaard om grammatica's voor gewone mensen in op te schrijven

Yep.. Je kunt in EBNF elke taal uitdrukken.. ook voor computers.en aan de hand van EBNF net zo goed een parser genereren. Want eigelijk is een parser maken op basis van EBNF ongelovelijk simpel. (Je hebt namelijk vertaal tabellen). En dit doen dus de meeste parser generators ook.

[Verwijderd]

Op maandag 25 februari 2002 17:21 schreef Alarmnummer het volgende:

[..]

Ik zit over een dikke jaar ook weer op jouw universiteit

jeej

[Verwijderd]

Op maandag 25 februari 2002 17:21 schreef Alarmnummer het volgende:
Ik zit over een dikke jaar ook weer op jouw universiteit

Aan jullie profilen te zien gaat het hier om de Uni van Groningen Op de UU heb je anders ook meer dan genoeg parsers... Volgende periode moet ik zelf compiler(tje)s gaan schrijven...

[Verwijderd]

Op maandag 25 februari 2002 17:34 schreef KoenM het volgende:

[..]

Aan jullie profilen te zien gaat het hier om de Uni van Groningen Op de UU heb je anders ook meer dan genoeg parsers... Volgende periode moet ik zelf compiler(tje)s gaan schrijven...

Ik beweer ook niet dat de RUG de enige goede universiteit is

[JapJap]

Op maandag 25 februari 2002 17:13 schreef Alarmnummer het volgende:

Je bent de herhalingen vergeten anders zou je bv geen
1+1+1+.... kunnen krijgen.

Nee hoor, want factor kan weer een expressie zijn:

expressie: term addop term

term: factor mulop factor

factor: '(' expressie ')' | getal

[edit]
aleen (addop term) en (mulop factor) zouden optioneel moeten zijn, denk ik...

[Alarmnummer]

is wel een erg late reply maar ik ben ff opzoek naar ander topic. Ik kon dit alleen niet onbeantwoord laten

Op maandag 25 februari 2002 18:56 schreef JapJap het volgende:

[..]

Nee hoor, want factor kan weer een expressie zijn:

In jouw geval zou je dan alleen expressies kunnen schrijven waarbij alles tussen haken staat en dat is denk ik niet de bedoeling

10+(10+(10+(10+20)))

ipv

10+10+10+10+20

aleen (addop term) en (mulop factor) zouden optioneel moeten zijn, denk ik...

Daarom staan er bij mij ook '*' omheen. Dit betekend dat je een herhaling van 0 tot n hebt en dus optioneel is.

[Janoz]

offtopic:
[quote]
Op maandag 25 februari 2002 17:39 schreef Zef het volgende:

[..]

Ik beweer ook niet dat de RUG de enige goede universiteit is
[/quote]

Ikke wel :P[quote]
Op maandag 25 februari 2002 17:21 schreef Alarmnummer het volgende:

[..]

Ik zit over een dikke jaar ook weer op jouw universiteit
[/quote]

Wat nou, ga je in de herkansing?

[Alarmnummer]

Op dinsdag 26 maart 2002 19:29 schreef Janoz het volgende:
Wat nou, ga je in de herkansing?

Yep, ik ga het duaal doen. Ze zijn erg tevreden over me waar ik nu werk en het was geen enkel probleem als ik wat extra tijd vrij moet nemen. De financieen zijn er dus en de interesse is eigelijk nooit verdwenen