[COMPILER] Van parse tree naar syntax tree

zaterdag 17 augustus 2002 17:41

Als parser gebruik ik goldparser om mijn source te parsen aangezien dit de enigste parser is die naar mijn weten ondersteuning bied voor .NET

cewl

die .NET module heb ik geschreven

Nu is mijn vraag: Hoe kan ik het beste dit aanpakken?

ik weet niet of het de beste manier is (zal wel niet), maar zelf doe ik het zo:

PHP:

while (!done && !fatal)
{                               
    ParseMessage result = m_parser.Parse();
                    
    switch (result)
    {
    case ParseMessage.Reduction:
        HandleReduction(m_parser.CurrentReduction);
        break;
    case ParseMessage.Accept:
        // program accepted
        done = true;
        break;
    // ... (foutafhandeling)
    }
    
    errors = (fatal ? errors + 1 : errors);
    fatal = fatal || (errors > 7);
}

private void HandleReduction(Reduction p_reduction)
{
    String str = "";
    Console.WriteLine(p_reduction);

    switch ((RuleConstants)p_reduction.RuleIndex)
    {
    /* function declaration */
    case RuleConstants.FunDecl:
        PushFunction();
        break;
    case RuleConstants.Param:
        PushVariable();
        break;
    /* statements */
    case RuleConstants.StmtListStart:
        PushCodeBlock(true);
        break;
    case RuleConstants.StmtList:
        PushCodeBlock(false);
        break;
    case RuleConstants.VarDecl:
        PushDeclaration();
        break;
    case RuleConstants.Assign:
        PushAssignment();
        break;
    case RuleConstants.IfStmt:
        PushIfStatement(false);
        break;
    case RuleConstants.ReturnStmt:
        PushReturnStatement();
        break;
    /* expressions */
    case RuleConstants.IntLiteral:
        str = (String)p_reduction.GetToken(0).Data;
        PushIntLiteral(str);
        break;
    case RuleConstants.Ident:
        str = (String)p_reduction.GetToken(0).Data;
        PushIdentifier(str);
        break;
    case RuleConstants.IdentList:
        PushIdentList(false);
        break;
    case RuleConstants.IdentListEnd:
        PushIdentList(true);
        break;
    /* types */
    case RuleConstants.TypeVoid:
        PushStandardType(StdType.Void);
        break;
    case RuleConstants.TypeInt:
        PushStandardType(StdType.Int);
        break;
//  ...
    }
}
        
private void PushFunction()
{
    CodeBlock code = (CodeBlock)m_stack.Pop();
    String name = ((Identifier)m_stack.Pop()).Name;
    IType type = (IType)m_stack.Pop();
    m_stack.Push(new Function(name, type, code));
}
        
private void PushVariable()
{
    Identifier id = (Identifier)m_stack.Pop();
    IType type = (IType)m_stack.Pop();
    m_stack.Push(new Variable(id.Name, type));
}

// etc

(vrij veel typwerk

)

Acties:

Verwijderd

Topicstarter

Voor ANTLR heb je dus JAVA nodig. Hier heb ik echter nog geen ervaring mee.
Ik denk dat ik eerst zelf een oplossing ga proberen te vinden. Het stukje over treecc ziet er ook goed uit. Staan ook wel leuke opmerkingen over het visitor pattern in ('Design patterns aren't always what they are cracked up to be'). Hier gaan ze in op de nadelen van de visitor. Ik vroege ontwikkeling van de compiler ben je regelmatig bezig met het veranderen van de tree. In dit geval is een visitor een 'maintaince nightmare'

zaterdag 17 augustus 2002 17:58

Acties:

Verwijderd

Topicstarter

marcusk schreef op 17 augustus 2002 @ 17:34:
[...]

cewl die .NET module heb ik geschreven

Heb je deze vanuit Java geport? In ieder geval wel handig. Scheelt mij weer een boel typewerk

ik weet niet of het de beste manier is (zal wel niet), maar zelf doe ik het zo:

Stuk code

Dit lijkt wel wat op wat ik in gedachten had. Ik ga echter al die functies (PushFunction, PushCodeBlock, etc.) in een visitor onderbrengen. Zo hou je al je analyses van tree apart. Zo kan ik later bijv. een visitor schrijven die de tree doorloopt en code genereert. Volgens mij was hiervoor al een interface gecode (IGoldVisitor).
Waar de grote truuk in zit, wat doe je met die stack? Zet je deze weer om naar een AST?

edit:
Het is quote, niet qoute

zaterdag 17 augustus 2002 17:59

Acties:

zaterdag 17 augustus 2002 18:07

-= Tja =-

ANTLR gebruikt een LL(k) grammatica en SableCC gebruikt een LALR(1) grammatica. Het voordeel aan een LR grammatica is dat je veel minder last hebt van ambiguiteiten zoals je dat hebt wel hebt met LL grammatica. Daar zul je mbv een syntactisch of semantisch predikaat de juiste alternatief moeten kiezen en door die predicaten gaat je grammatica naar zijn grootje.

Ik heb met uitzonderlijk veel plezier ANTLR verwijderd uit het system en vervangen door SableCC. Zoals Zef al zegt genereerd SableCC dus wel een AST met ingebouwde visitor en een aantal guide`s en het werkt echt geweldig.

Ik zou dus niets doen met ANTLR en kijken of je een LR parser generator kan vinden voor C# en mbv semantische acties die zelf geschreven AST gaan vullen.

En misschien komt er in de toekomst nog wel een c# versie voor SableCC. Maar ik neem aan dat je niet zo lang wilt wachten.

Acties:

zaterdag 17 augustus 2002 18:08

-= Tja =-

Verder kan je trouwens heel aardig je object ontwerp laten volgen uit je grammatica. Als bv de volgende productie hebt:

code:

persoon_declr
     = timmerman_declr
     | slager_declr
     ;

Dan lijkt het me vrij duidelijk hoe je je object model kan maken. Je maakt bv een interface voor de productie naam, en voor ieder alternatief maak je dus een object die die interface implementeerd en referentie naar alle terminal en non terminals.
En verder heeft iedere non terminal aan de rhs weer een referentie in zich naar de productie die is uitgevoerd. En voor tokens kan je iets vergelijkbaars doen (vaak is het wel dezelfde grammatica als je een scannerless parser hebt).

Anders moet je even kijken naar SableCC en wat voor code die geneerd. Verder staat er op de site een uitstekende handleiding.

Acties:

zaterdag 17 augustus 2002 18:12

Verwijderd schreef op 17 augustus 2002 @ 17:58:
Heb je deze vanuit Java geport? In ieder geval wel handig. Scheelt mij weer een boel typewerk .

De Java versie was toen nog niet open-source, dus het is min of meer een port van de VB-versie (heb vrij veel aangepast

)

Dit lijkt wel wat op wat ik in gedachten had. Ik ga echter al die functies (PushFunction, PushCodeBlock, etc.) in een visitor onderbrengen. Zo hou je al je analyses van tree apart. Zo kan ik later bijv. een visitor schrijven die de tree doorloopt en code genereert. Volgens mij was hiervoor al een interface gecode (IGoldVisitor).

Die IGoldVisitor (die ik overigens heb bedacht) heeft achteraf gezien eigenlijk weinig nut omdat het alleen een visitor-methode voor het Reduction object hebt. Dan zul je dus alsnog een switch moeten gebruiken voor de verschillende RuleIndex-en.

Waar de grote truuk in zit, wat doe je met die stack? Zet je deze weer om naar een AST?

Na het parsen staan er alleen nog Function objecten op de stack. Daarvan wordt dan de methode aangeroepen om de IL code te genereren.

Acties:

Verwijderd

Topicstarter

Alarmnummer schreef op 17 augustus 2002 @ 17:59:
ANTLR gebruikt een LL(k) grammatica en SableCC gebruikt een LALR(1) grammatica. Het voordeel aan een LR grammatica is dat je veel minder last hebt van ambiguiteiten zoals je dat hebt wel hebt met LL grammatica. Daar zul je mbv een syntactisch of semantisch predikaat de juiste alternatief moeten kiezen en door die predicaten gaat je grammatica naar zijn grootje.

GoldParser gebruikt ook LALR(1). Het automatisch creeren van een AST ontbreekt echter. Ook wordt EBNF niet ondersteund waardoor je van die diep geneste trees krijgt.

Ik heb met uitzonderlijk veel plezier ANTLR verwijderd uit het system en vervangen door SableCC. Zoals Zef al zegt genereerd SableCC dus wel een AST met ingebouwde visitor en een aantal guide`s en het werkt echt geweldig.

Kun je misschien een voorbeeldje geven van een AST die sablecc produceert? Ik denk dat ik dan wel weer verder kan. Waar in echt tegenaan loop is het feit dat ik niet weet welke nodes ik nodig heb, en hoe deze nodes informatie over elkaar opslaan.

Ik zou dus niets doen met ANTLR en kijken of je een LR parser generator kan vinden voor C# en mbv semantische acties die zelf geschreven AST gaan vullen.

En misschien komt er in de toekomst nog wel een c# versie voor SableCC. Maar ik neem aan dat je niet zo lang wilt wachten.

De enige optie is volgens mij nu nog goldparser. Op zich vind ik het ook niet erg om zelf een AST te bouwen. Ik vind deze materie nl wel interessant.

offtopic:
Ik wacht nog steeds op 'Modern Compiler Design' van Dick Grune.

zaterdag 17 augustus 2002 18:18

Acties:

Verwijderd

Topicstarter

marcusk schreef op 17 augustus 2002 @ 18:08:

Die IGoldVisitor (die ik overigens heb bedacht) heeft achteraf gezien eigenlijk weinig nut omdat het alleen een visitor-methode voor het Reduction object hebt. Dan zul je dus alsnog een switch moeten gebruiken voor de verschillende RuleIndex-en.

[...]

Ik heb hem daarom ook uitgebreid met extra 'Visit' methoden.

Na het parsen staan er alleen nog Function objecten op de stack. Daarvan wordt dan de methode aangeroepen om de IL code te genereren.

Aha, wat jouw code doet is dus het genereren van CodeDOM objecten. Deze zet je dan om naar IL. Wat ik echter wil is een eigen taal maken (de compiler wordt dus in c# geschreven), compleet met semantics, codegeneratie etc.

[ Voor 0% gewijzigd door Verwijderd op 17-08-2002 18:25 . Reden: Typo's ]

zaterdag 17 augustus 2002 18:24

Acties:

Verwijderd

Topicstarter

Alarmnummer schreef op 17 augustus 2002 @ 18:07:
Verder kan je trouwens heel aardig je object ontwerp laten volgen uit je grammatica. Als bv de volgende productie hebt:
code:
1
2
3
4
persoon_declr
     = timmerman_declr
     | slager_declr
     ;
Dan lijkt het me vrij duidelijk hoe je je object model kan maken. Je maakt bv een interface voor de productie naam, en voor ieder alternatief maak je dus een object die die interface implementeerd en referentie naar alle terminal en non terminals.
En verder heeft iedere non terminal aan de rhs weer een referentie in zich naar de productie die is uitgevoerd. En voor tokens kan je iets vergelijkbaars doen (vaak is het wel dezelfde grammatica als je een scannerless parser hebt).

Dus in mijn geval krijg ik dus een ProgramNode, StatementNode, WriteStatementNode, etc.

Anders moet je even kijken naar SableCC en wat voor code die geneerd. Verder staat er op de site een uitstekende handleiding.

Hmm, hier heb ik dus ook Java voor nodig. Moet het toch maar eens downloaden dan (heb 56k dus ik ben wat conservatief

zaterdag 17 augustus 2002 18:26

Acties:

zaterdag 17 augustus 2002 18:30

Verwijderd schreef op 17 augustus 2002 @ 18:18:
Ik heb hem daarom ook uitgebreid met extra 'Visit' methoden.

Visit metoden voor welke objecten dan?

Aha, wat jou code doet is dus het genereren van CodeDOM objecten. Deze zet je dan om naar IL.

Zoiets is de bedoeling idd, maar daar ben ik nog niet erg ver mee (project staat even in de koelkast

)

Wat ik echter wil is een eigen taal maken (de compiler wordt dus in c# geschreven), compleet met semantics, codegeneratie etc.

Jep, ik maak ook een eigen (simpele) taal. Wat is (volgens jou) het verschil met hoe ik het doe dan?

Acties:

zaterdag 17 augustus 2002 18:34

-= Tja =-

marcusk schreef op 17 augustus 2002 @ 18:26:
Visit metoden voor welke objecten dan?

Als een visitor bij een visitable op bezoek wil zal bij de visitable wel een 'accepts visitor' methode geimplementeerd worden met als argument de visitor die op bezoek gaat.

Acties:

Verwijderd

Topicstarter

marcusk schreef op 17 augustus 2002 @ 18:26:
[...]
Visit metoden voor welke objecten dan?

[...]
Zoiets is de bedoeling idd, maar daar ben ik nog niet erg ver mee (project staat even in de koelkast )

[...]
Jep, ik maak ook een eigen (simpele) taal. Wat is (volgens jou) het verschil met hoe ik het doe dan?

Als ik het goed heb dan wordt jouw taal uiteindelijk omgezet in IL bytecode. Je genereert uit de source dus eerst C# code (in DOM vorm dan), en laat de c# compiler hier overheen gaan met als resultaat een .NET assembly. Ik wil dus een 'eigen DOM' maken + compiler (misschien wat te hoog gegrepen maar we zien wel waar het schip strandt

zaterdag 17 augustus 2002 19:00

Acties:

zaterdag 17 augustus 2002 19:13

Verwijderd schreef op 17 augustus 2002 @ 18:34:
Als ik het goed heb dan wordt jouw taal uiteindelijk omgezet in IL bytecode. Je genereert uit de source dus eerst C# code (in DOM vorm dan), en laat de c# compiler hier overheen gaan met als resultaat een .NET assembly. Ik wil dus een 'eigen DOM' maken + compiler.

Aha, ik begrijp het. Jij wilt dus Reflection.Emit gebruiken neem ik aan?

Overigens maak ik de compiler als voorbeeld voor GoldParser, vandaar dat ik de boel simpel houdt

Er waren namelijk nogal wat mensen die me mailden voor een beter voorbeeld voor het gebruik van GP.Net (een parse tree printen is niet bepaald een nuttige toepassing

(misschien wat te hoog gegrepen maar we zien wel waar het schip strandt )

Succes iig

Acties:

Verwijderd

Ik vind SableCC echt een heerlijke parser generator. Juist omdat hij AST genereerd en de daarbij horende tree walkers. Als je de tijd hebt en een beetje java kan lezen (lijkt erg op C#) dan zou je veel mensen blij maken met een C# emitter

maar misschien is dit wel te veel werk. Mocht je hier voor voelen kun je natuurlijk het deel dat ik al gedaan heb krijgen

zaterdag 17 augustus 2002 19:18

Acties:

Verwijderd

Topicstarter

marcusk schreef op 17 augustus 2002 @ 19:00:
[...]
Aha, ik begrijp het. Jij wilt dus Reflection.Emit gebruiken neem ik aan?

Nou, eigenlijk niet

. De enigste baseclasses die ik nodig heb zijn die in System en System.Collections. De taak die nu iig voor me ligt is het schrijven van alle klassen van de AST, en de procedures die de Reductions en Tokens omzet in de juiste klassen. Uiteindelijk krijg je dan een boomstructuur met bovenaan bijv. ProgramNode. Deze bevat dan weer een aantal StamentNode's, die op zijn beurt als child's bijv. een VariableDeclarationNode heeft.
Wanneer dit karwei af is komt er een visitor bij die deze boom doorloopt, en een Win32 EXE genereert (waarschijnlijk wordt het eerst interpreted) en later wil ik nog een VM er voor bouwen

Overigens maak ik de compiler als voorbeeld voor GoldParser, vandaar dat ik de boel simpel houdt Er waren namelijk nogal wat mensen die me mailden voor een beter voorbeeld voor het gebruik van GP.Net (een parse tree printen is niet bepaald een nuttige toepassing ).

Hmm, misschien dat ik je hierbij kan helpen. Wanneer ik iets concreets heb kun je het misschien wel gebruiken (ik heb nogal eens het probleem dat projecten vaak een tijdje in de koelkast gaan wanneer ik tegen frustrerende details aanloop

Succes iig

Thx! Ik zal eerst even de AST's die SableCC genereert bekijken (beter goed gejat dan slecht bedacht

zaterdag 17 augustus 2002 19:22

Acties:

Verwijderd

Topicstarter

Zef schreef op 17 augustus 2002 @ 19:13een stukje over SableCC:

Ik zal iig kijken wat ik allemaal met SableCC kan. Als ik de reply's zo lees dan lijkt het me dat dit de beste optie is wanneer ik ergens op stuk loop.

zaterdag 17 augustus 2002 21:03

Acties:

zondag 18 augustus 2002 02:09

Verwijderd schreef op 17 augustus 2002 @ 19:18:
Nou, eigenlijk niet . De enigste baseclasses die ik nodig heb zijn die in System en System.Collections. De taak die nu iig voor me ligt is het schrijven van alle klassen van de AST, en de procedures die de Reductions en Tokens omzet in de juiste klassen. Uiteindelijk krijg je dan een boomstructuur met bovenaan bijv. ProgramNode. Deze bevat dan weer een aantal StamentNode's, die op zijn beurt als child's bijv. een VariableDeclarationNode heeft.
Wanneer dit karwei af is komt er een visitor bij die deze boom doorloopt, en een Win32 EXE genereert (waarschijnlijk wordt het eerst interpreted) en later wil ik nog een VM er voor bouwen .

Oh hehe, op die manier

Dat gaat best veel werk worden schat ik

Hmm, misschien dat ik je hierbij kan helpen. Wanneer ik iets concreets heb kun je het misschien wel gebruiken (ik heb nogal eens het probleem dat projecten vaak een tijdje in de koelkast gaan wanneer ik tegen frustrerende details aanloop ).

Bedankt voor het aanbod, maar ik maak et liever zelf

(In dit geval was ik even gestopt omdat ik het nogal druk had met m'n studie (dat houdt me van nuttige dingen af

), niet omdat het niet wilde lukken.)

Acties:

Blog, Stratego/XT: Program Transformation, SDF: Syntax Definition, Nix: Software Deployment

Hum, het schrijven van deze transformatie is in principe nogal vervelend (en dom) werk. Dat roept dus om code-generatie

.

Waarom neem je niet even de extra moeite en schrijf je (waarschijnlijk als uitbreiding op de GoldParser) niet een stuk code die AST klassen genereert en een transformatie van de parse-tree naar deze AST klassen? Het lijkt misschien erg ingewikkeld (en het is ook niet helemaal triviaal), maar het kan wel een hele leuke oefening zijn en een hele nuttige bijdrage.

Als je je grammatica flink gaat uitbreiden verdien je je investering vrij snel terug: opnieuw code genereren kost een paar seconde, de transformatie handmatig aanpassen kan een grotere (en vervelende) klus worden...

zondag 18 augustus 2002 12:01

Acties:

Verwijderd

Topicstarter

Dit lijkt me idd wel een interessant plan. Ik heb even op de GoldParser site rondgekeken en het blijkt dat er ook al iets dergelijks in C++ is geschreven is waarvan de source beschikbaar is. Ik denk dat ik dit even ga bestuderen om te kijken of dit bruikbaar is voor een C# versie.

zondag 18 augustus 2002 12:31

Acties:

Zoijar

Because he doesn't row...

Verwijderd schreef op 17 augustus 2002 @ 17:41: ('Design patterns aren't always what they are cracked up to be'). Hier gaan ze in op de nadelen van de visitor. Ik vroege ontwikkeling van de compiler ben je regelmatig bezig met het veranderen van de tree. In dit geval is een visitor een 'maintaince nightmare' .

Niet als je de (templated) visitor gebruikt die Alexandrescu beschrijft in z'n boek. Sorry moest het even zeggen, ben nl. DP junk

zondag 18 augustus 2002 13:20

Acties:

Blog, Stratego/XT: Program Transformation, SDF: Syntax Definition, Nix: Software Deployment

Visitor interfaces kunnen sowieso ook gegenereerd worden door een parser-generator. Sommige parser-generators doen dit dus ook en genereren daarbij ook nog allemaal helpers zoals een Visitor implementatie voor generieke visits, een Visitor implementatie met lege visits (vergelijk met de adapters in de Java event API), verschillende traversal-orders enz enz. Als je al echt serieuze code hebt geschreven in de vorm van visitors, zal je die uiteraard moeten aanpassen.

Bij het Visitor pattern zijn methoden die samen een bepaalde operatie implementeren, gegroepeerd in 1 klasse en dus niet verspreid over de object-structuur. Hierdoor is het makkelijk om een nieuwe operatie toe te voegen (in de vorm van een visitor), maar het is minder makkelijk als de boom-structuur verandert.

Het Visitor pattern komt op dit punt sterk overeen met de aanpak in functioneel programmeren, waar het toevoegen van een nieuwe functie over een data-structuur ook erg eenvoudig is, maar een aanpassing van de data-structuur erg vervelend kan zijn....

zondag 18 augustus 2002 13:20

Acties:

zondag 18 augustus 2002 13:23

-= Tja =-

Verwijderd schreef op 17 augustus 2002 @ 17:41:
Staan ook wel leuke opmerkingen over het visitor pattern in ('Design patterns aren't always what they are cracked up to be'). Hier gaan ze in op de nadelen van de visitor. Ik vroege ontwikkeling van de compiler ben je regelmatig bezig met het veranderen van de tree. In dit geval is een visitor een 'maintaince nightmare' .

Daarom is code generatie ook zo handig, en eigelijk onmisbaar bij het het gebruik van een AST. Zie verder verhaal van mbravenboer. Hij zegt dat je beter even tijd kan steken in een tooltje dat een AST kan maken op basis van een grammatica ipv het iedere keer met de hand te doen. Vooral na verloop van tijd zul je hier een grote tijdswinst mee behalen.

Acties:

Verwijderd

Topicstarter

Zoijar schreef op 18 augustus 2002 @ 12:31 iets over een templated visitor:

Templated visitor? Kun je hier wat meer over vertellen?
Het stuk waar dit in stond was trouwens niet echt professioneel. In het voorbeeld waar ze uitlegden waarom een visitor nadelen had, lieten ze ong. het volgende voorbeeld zien:

code:

void Visit(Node node)
{
    switch(node.type)
    {
        case Negate:
            ...
            break;

        case UnaryPlus:
            ...
            break;
    }
}

Al die case's van het switch statement moeten natuurlijk afzonderlijke Visit methoden worden.
Maar ja, feit blijft natuurlijk dat bij elke nieuwe Node er een nieuwe Visit methode moet worden geschreven.
_{ydejager is nu wel heel benieuwd wat een templated visitor voor oplossing biedt}

zondag 18 augustus 2002 13:29

Acties:

zondag 18 augustus 2002 13:38

-= Tja =-

Anders moet je dit even doorkijken. Mbv de element adder (extensie op de visitor design pattern) is het wel eenvoudig om nieuwe classes toe te voegen aan de hierarchie.

Maar zo gauw je dus wel beschikking hebt over alle sourcecode (in jouw geval dus) hoef je dit dus niet te te passen. Ik zou dus echt gebruik blijven maken van de normale visitor. Verder zou ik me even gaan verdiepen in visitor guide`s zodat je traversals kan hergebruiken.

code:

class VariableCollector extends VisitorAdapter{
    List _varList = new LinkedList();
 
    void visit(Variable var){_varList.add(v);}
}

VariableCollector varCol = new VariableCollector();
expression.accepts(new DepthFirstGuide(varCol));

Acties:

Verwijderd

Topicstarter

mbravenboer schreef op 18 augustus 2002 @ 13:20 een leuk stuk over het Visitor pattern:

Nu je het zegt doet me dit idd denken aan tijd dat ik nog wel eens iets in C schreef. Een verandering van datastructuur had als gevolg dat alle functies aangepast moesten worden.

Alarmnummer schreef op 18 augustus 2002 @ 13:20:
Daarom is code generatie ook zo handig, en eigelijk onmisbaar bij het het gebruik van een AST. Zie verder verhaal van mbravenboer. Hij zegt dat je beter even tijd kan steken in een tooltje dat een AST kan maken op basis van een grammatica ipv het iedere keer met de hand te doen. Vooral na verloop van tijd zul je hier een grote tijdswinst mee behalen.

Ik heb al even nagedacht over de aanpak hiervan. Ik zie in principe 2 oplossingen:
1 Een algemeen framework schrijven waarbij de gebruiker een library schrijft met alle ASTNode's welke doormiddel van reflection wordt ingeladen. Hier moet dan nog een beschrijving bij die opgeeft welke node uit de parse tree moet worden omgezet in een bijbehorende AST node (bijv. een simpele XML file.
2 Een eigen parser schrijven die de grammatica van de betreffende taal inleest en voor elke rule een bijbehorende node genereert. Hier kan dan, zoals mbravenboer al opmerkte, een framework voor het Visitor pattern aan worden toegevoegd.
De laatste optie is natuurlijk het mooist, maar zou betekenen dat ik een grammatica in BNF voor BNF moet schrijven

. Ik denk dat ik eerst voor de eerste optie ga (in de goldparser c++ source wordt dit ook op deze manier opgelost).

zondag 18 augustus 2002 13:38

Acties:

Gerco

Professional Newbie

Is het bij dat visitor pattern niet vreselijk lastig om een nieuwe Visitor toe te voegen? Je moet dan toch in alle visited klassen een methode accepts(BlablaVisitor) maken? Dan moet je alsnog je hele hierarchie bijwerken als je een operatie wilt toevoegen.

- "Als ik zou willen dat je het begreep, legde ik het wel beter uit!" | All number systems are base 10!

zondag 18 augustus 2002 13:41

Acties:

Blog, Stratego/XT: Program Transformation, SDF: Syntax Definition, Nix: Software Deployment

Voor het doen van een traversal over zeer in beweging zijnde of zelfs (gedeeltelijk) onbekende data-structuren is er nog een andere oplossing: de Walkabout.

Dit staat omschreven in The Essence of the Visitor Pattern van Palsberg en ik heb later nog een logischere en snellere variant gepresenteerd in Guiding visitors: Separating navigation from computation.

zondag 18 augustus 2002 13:46

Acties:

Verwijderd

Topicstarter

Gerco schreef op 18 augustus 2002 @ 13:38:
Is het bij dat visitor pattern niet vreselijk lastig om een nieuwe Visitor toe te voegen? Je moet dan toch in alle visited klassen een methode accepts(BlablaVisitor) maken? Dan moet je alsnog je hele hierarchie bijwerken als je een operatie wilt toevoegen.

Nee, het visitor pattern is ervoor om juist dit te voorkomen. Alle visitors erven nl over van een abstracte visitor klasse. Alle elementen in je structuur accepten deze abstracte visitor. Alle operaties stop je dus in van de abstracte visitor afgeleide klassen.

zondag 18 augustus 2002 13:47

Acties:

Blog, Stratego/XT: Program Transformation, SDF: Syntax Definition, Nix: Software Deployment

Gerco: Is het bij dat visitor pattern niet vreselijk lastig om een nieuwe Visitor toe te voegen? Je moet dan toch in alle visited klassen een methode accepts(BlablaVisitor) maken?

Er is maar 1 interface voor een Visitor over een bepaalde data-structuur. Alle klassen in de structuur moeten een methode accept hebben die deze Visitor accepteert. Concrete Visitor implementaties (operaties over de data-structuur dus) implementeren deze interface dus.

Het grote voordeel van het Visitor pattern is juist dat je niet in alle klassen in de structuur methoden op hoeft te gaan nemen en je operatie zo helemaal verspreid geimplementeerd is. Zie voor meer en betere uitleg de papers die ik net linkte

(op Javahova is er trouwens ook een leuk topic over).

zondag 18 augustus 2002 13:49

Acties:

Verwijderd

Topicstarter

Er wordt hier nu met aardig wat documentatie gesmeten wat ik eerst eens zal doorploegen. Ik hou nl niet de actuele ontwikkelingen op het gebied van design patterns bij. Ik heb iig weer wat te lezen

zondag 18 augustus 2002 13:51

Acties:

Blog, Stratego/XT: Program Transformation, SDF: Syntax Definition, Nix: Software Deployment

ydejager: Een eigen parser schrijven die de grammatica van de betreffende taal inleest en voor elke rule een bijbehorende node genereert.

In principe hoef je niet zelf een parser te gaan schrijven voor een bepaalde grammatica (tenzij je dat natuurlijk erg leuk vindt

). Je zou gewoon de bestaande toolkits uit kunnen breiden (wat bij vele toolkits trouwens geeneens nodig is omdat daar deze functionaliteit al aanwezig is).

GoldParser zal vast een parser en een AST hebben voor de grammatica-taal die wordt gebruikt. Je kan misschien zelfs nog wat code-generatie componenten gebruiken...

zondag 18 augustus 2002 13:59

Acties:

Verwijderd

Topicstarter

mbravenboer schreef op 18 augustus 2002 @ 13:51:
[...]

In principe hoef je niet zelf een parser te gaan schrijven voor een bepaalde grammatica (tenzij je dat natuurlijk erg leuk vindt ). Je zou gewoon de bestaande toolkits uit kunnen breiden (wat bij vele toolkits trouwens geeneens nodig is omdat daar deze functionaliteit al aanwezig is).

Ik bedoelde natuurlijke een eigen grammatica schrijven

GoldParser zal vast een parser en een AST hebben voor de grammatica-taal die wordt gebruikt. Je kan misschien zelfs nog wat code-generatie componenten gebruiken...

Op zich moet het wel te doen zijn wanneer ik eenmaal de grammatica die goldparser hanteerd (BNF dus) kan uitlezen. Er moet dan denk ik nog iets door de gebruiker aangeboden worden wat aangeeft welke reductions worden omgezet in een AST. De code generatie kan dan mooi via de .NET CodeDOM.
Het stukje over 'The Essence of the Visitor pattern' lijkt op het eerste gezicht wel interessant maar (als ik het goed heb) vertrouwd er dus op dat er reflection mogelijkheden in de taal aanwezig zijn. Als ik tijd heb zal ik me hier eens in gaan verdiepen.

zondag 18 augustus 2002 14:07

Acties:

zondag 18 augustus 2002 14:10

-= Tja =-

mbravenboer schreef op 18 augustus 2002 @ 13:47:
(op Javahova is er trouwens ook een leuk topic over).

Die kan hij niet lezen

Maar als het klaar is zal ik het ook op GoT plaatsen ivm dalend nivo en om een start te maken met de nieuwe 'tutorial/artikel' gebeuren op GoT.

Acties: