Formula parser en control structures

[DexterDee]

Voor een data mapping component heb ik een formuletaal parser geschreven om zeer flexibele transformaties mogelijk te maken. Aangezien ik weinig ervaring heb met het zelf schrijven van language parsers, ben ik eerst op zoek gegaan naar een stukje theorie. Uiteindelijk heb ik een stack based bottom-up parser gekozen en het operator precedence parser algoritme geimplementeerd.

Mijn parser hanteert de volgende stappen:
1. parse formule naar individuele string tokens
2. classificeer elk string token in een token object en zet type, precedence, arity en associativity
3. converteer token object array naar reverse polish notation middels het shunting yard algoritme
4. voer de postfix token object array uit en retourneer de output

Ik heb de parser uitgebreid om met functies te kunnen omgaan die een niet vaststaand aantal parameters hebben, omdat het originele algoritme hierin niet voorzag. Ook heb ik de ; operator toegevoegd om meerdere commando's te kunnen opgeven na elkaar.

De engine werkt prima en ik kan formules als deze keurig correct uitvoeren:

code:

a=@REPLACE('Fok', 'GoT', 'Fok is mijn favoriete forum!'); a+'!!'

@SUBSTRING('groenblauwwit',5,5)+' is mijn favoriete kleur'

3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

a=1; b=2; @IF(a==b, 'gelijk', 'anders')

(9*11)+' luchtballonnen'

So far so good... Nu zit ik echter te denken aan een aantal nice-to-haves in de vorm van control structures. Deze manier van parsen herleidt keurig alle geneste haakjes en de correcte operator volgorde. Een side-effect van deze manier van parsen is dat álle delen van de formule geparsed worden.

Als ik deze formule neem:

code:

@IF(1==2, a='piet', b='kees')

dan zal na het uitvoeren zowel variabele a als b gezet zijn. Ergens ook wel logisch, want de 'if' en 'else' parameters van @IF worden eerder geëvalueerd dan de @IF functie.

Dit werkt wel:

code:

a=@IF(1==2, 'piet', 'kees')

dus het is niet een hele grote ramp, men kan er altijd wel omheen werken.

Nu ben ik benieuwd of ik nog wat kan tweaken aan de parser om dit soort constructies toch mogelijk te maken. Misschien ook zoiets als dit:

code:

@WHILE(a<10, 'loop nummer '+a, a=a+1)

Aangezien de parameters eerst (en eenmalig) worden geëvalueerd, gaat die vlieger niet zomaar op.

Ik zou graag willen weten of het mogelijk is om het huidige algoritme te tweaken, zodat zaken als conditionals correct werken. Het omschrijven naar een recursive descent of LL / LALR parser vind ik teveel werk voor deze nice-to-haves, maar ik kan zo een-twee-drie geen oplossing of hack bedenken om de huidige code zover te krijgen.

Wie weet raad?

[kasper_vk]

Het lijkt erop dat je het parsen en evalueren dus in één moeite door doet, en da's dus niet wat je wilt.
Je zou als resultaat van het parsen een (boom-achtige) datastructuur moeten opbouwen, waarop je dan een evalueer() methode o.i.d. aanroept, welke de eigenlijke evaluatie doet.

Het opbouwen van boomrepresentaties van de code is vrij gebruikelijk bij het oplossen van dit probleem, je bent de termen AST, CST en intermediate representation vast wel tegengekomen in je zoektocht naar de achterliggende theorien.
De boomstructuur waar ik op doel is er dan één die het meest lijkt op de intermediate representation.

[ Voor 3% gewijzigd door kasper_vk op 25-03-2010 13:30 ]