[c++] Simpele parser bouwen.

[writser]

Ik zit al een tijdje te pielen met het volgende probleem. Ik probeer een simpele parser te maken (voor de botwar, maar dat is verder niet erg relevant) die strings omzet in objecten. Ik krijg bijvoorbeeld de string "USER foo bar" binnen, die wil ik parsen naar een klasse 'UserMessage' met members 'user' en 'password'. Omgekeerd wil ik ook objecten kunnen terugzetten in een string. Een soort serialization dus, maar met simpele ascii strings. Ik heb hiervoor een abstracte klasse voor berichten gemaakt:

C++:

class Message {
public:
    virtual QString toString() const = 0;
    static Message * parse(const QString & line);
};

Voor elk mogelijk bericht definieer ik een subklasse van message met een bijbehorende toString(), zoals de volgende klasse:

C++:

class UserEnterMessage : public Message {
public:
    QString toString() const;
    // getters en setters even weggelaten
    int turnID;
    QString user;
};

Ik kan nu op makkelijke wijze een UserMessage maken en deze converteren naar een string. Ik kan ook gemakkelijk het protocol aanpassen door nieuwe klasses te maken. Alleen twijfel ik nu hoe ik het parsen van strings moet aanpakken. Ik heb een mooie tokenizer en het parsen opzich is niet zo moeilijk. Maar wat is de beste manier om het te integreren in mijn project?

Op dit moment heb ik een statische functie voor het parsen. Op het eerste gezicht handig, ik doe Message::parse("USER foo bar") en er wordt een UserMessage object geretourneerd. Maar ik zit met het volgende probleem: als ik een nieuw type message toevoeg, moet ik een functie in de abstracte klasse gaan veranderen. Dat is niet erg OO dunkt me, bovendien maakt het het uitbreiden van het protocol lastig.

Ik heb geprobeerd om voor elke subklasse een aparte parse-functie te maken. Maar nog steeds moet ik de abstracte klasse aanpassen, want die moet nu voor elke afgeleide klasse de parse-functie aanroepen. Bovendien zorgt dit voor erg slechte performance, omdat voor elke afgeleide klasse wordt geprobeerd om de gehele string te parsen. In het ideale geval zou dit parallel gebeuren, zodat het parsen meteen stopt bij een ongeldige string.

Een andere oplossing zou zijn om voor elke Message klasse een MessageParser te maken en deze te registreren bij de abstracte klasse. Maar dit lijkt me overkill, bovendien is het slecht voor de performance, want nog steeds moeten alle parse-functies geprobeerd worden. Bovendien komt iets simpels als het parsen van een double steeds terug, dat zou eigenlijk in een centrale functie gedefinieerd moeten worden.

Op dit moment hou ik het maar bij de statische parse-functie. Het is lelijk, maar het werkt! Maar er is vast een betere methode, ik heb het gevoel dat ik in de verkeerde richting zoek. Elke message heeft een uniek keyword, zoals 'USER' in "USER foo bar". Misschien kan ik hier iets mee? Heb je een geheel ander idee, prima, alle hulp is welkom. Maar kom a.u.b. niet met "het is overkill voor die botwars contest, gebruik gewoon wat simpele hacks" (hoewel je misschien gelijk hebt ). Het gaat me meer om het achterliggende idee, hoe pak je zoiets handig aan?

[ Voor 25% gewijzigd door writser op 14-11-2005 17:49 ]

[.oisyn]

Ik heb geprobeerd om voor elke subklasse een aparte parse-functie te maken. Maar nog steeds moet ik de abstracte klasse aanpassen, want die moet nu voor elke afgeleide klasse de parse-functie aanroepen

Waarom? Je override toch de parsefunctie, dan hoef je toch niets in de abstracte klasse te veranderen? Ik zou zelf gewoon alle parsers registreren, en dan bij een binnenkomende message elke parser uitproberen om te kijken of hij er wat mee kan. Als dat niet het geval is ga je door met de volgende, en anders heb je een geldige Message.

Als je het wat efficienter wil laten lopen zul je wat meer aannames moeten doen over wat er precies geparsed wordt. Elke parser moet dan opgeven wat hij verwacht (bijvoorbeeld string "USER" gevolgd door twee strings), en als je alle parsers hebt dan genereer je een lookup tree. Dan kun je vervolgens zelf de binnenkomende string opdelen in hapklare blokken (tokenizen) en vervolgens door de lookup tree heen lopen en kom je uiteindelijk bij de goede parser uit.

[Daos]

Parsers zijn lastig om te maken en daarom zijn er parser-generators. De tokens komen van een lexer en daar heb je weer een lexer-generator voor. Een bekende combinatie is lex met yacc (GNU: flex en bison). Deze gevallen genereren respectievelijk een lexer en parser in C. C is niet zo moeilijk om te zetten naar C++.

[.oisyn]

Ik zou dan overigens gaan voor flex++ en bison++, die genereren C++ classes die (uiteraard zoals je van een klasse kunt verwachten) reentrant zijn

[ Voor 3% gewijzigd door .oisyn op 14-11-2005 18:17 ]

[writser]

Waarom? Je override toch de parsefunctie, dan hoef je toch niets in de abstracte klasse te veranderen? Ik zou zelf gewoon alle parsers registreren, en dan bij een binnenkomende message elke parser uitproberen om te kijken of hij er wat mee kan. Als dat niet het geval is ga je door met de volgende, en anders heb je een geldige Message.

Hoe pak je zoiets precies aan? Elke afgeleide klasse heeft dan een functie static Message * parse(Qstring line). Op welke manier kun je die registreren in de abstracte klasse? Ik ben nog niet zo'n held met functie-pointers.

C++:

static bool registerParser((Message *) parseFunction (const QString & line))
};

Zoiets, en dan alle functies in een vector gooien? Ik zal zo even wat uitproberen. Het lijkt me een prima oplossing, kan ik ook mooi wat basisfuncties als parseNumber<type> in de abstracte klasse gooien. Vraag me alleen wel af in hoeverre deze functionaliteit 'hoort' in de Message klasse. Deze representeert toch alleen een bericht, niet een parser!

Ik ken flex en bison, maar het gebruik daarvan lijkt me wat overdreven. Ik heb geen grammatica, alleen enkele commando's waarvan de vorm al vast staat.

[ Voor 38% gewijzigd door writser op 14-11-2005 19:05 ]

[MisterData]

Wat ook een optie is is Spirit. Die gebruikt wat leuke taaltrucjes zodat je je grammatica eigenlijk gewoon in C++ beschrijft. Werkt erg handig, geen gezeur met losse tooltjes, alleen even de library en wat headers toevoegen

[writser]

Ik heb nu de volgende oplossing bedacht:

C++:

// Message.h

class Message {
public:
    virtual QString toString() const = 0;
    static Message * parse(const QString & line);
    static bool registerParser(Message * (*parseFunction) (const QString &));

private:
    static QList<Message * (*) (const QString &)> parserList;
};

C++:

// Message.cpp

// initialiseer de static member parserList
QList<Message * (*) (const QString &)> Message::parserList;

bool Message::registerParser(Message * (*parseFunction) (const QString &)) {
    // voeg de meegegeven parse-functie toe aan de lijst van parse-functies.
    Message::parserList << parseFunction;
    return true;    
}

Later kan ik de QList nog vervangen door een QMap, zodat een parser kan worden opgezocht aan de hand van een string. Bijvoorbeeld, begint een string met 'USER', dan kan ik de goede parser vinden met parserMap["USER"]. Maar eerst vind ik dit wel goed genoeg. Kan iemand mij vertellen of dit goede code is? Er zijn geen compileerfouten, maar als ik haken om 'Message *' zet krijg ik wel errors. Raar ..

Tijdens het googlen was ik Spirit inderdaad tegengekomen. Erg knap hoe ze dat geimplementeerd hebben, zal er eens wat mee knutselen. Maar ik ben begonnen aan mijn eigen parser, en die moet nu af ook!

[andrew]

Ik los zoiets meestal op met een map.

Je maakt voor alle commando's die je binnenkrijgt een parse-klasse aan en deze stop je in een map onder de string waar het commando bijhoort. Vervolgens roep je de de parse functie aan op dat object.

Een voorbeeld (lijkt me handig ):

C++:

abstract class MessageParser
{
  virtual void parse(const QString &line) = 0;
};

class UserParser : public MessageParser
{
  virtual void parse(const QString &line);
};

Vervolgens maak je ergens een map aan.

C++:

  map<QString, MessageParser> parsers;

In die map gooi je dan een instantie van alle parsers. Daarna lees je het eerste woord uit de string die je binnenkrijgt, dan kijk je of hij in de map bestaat en vervolgens roep je de parse functie aan van dat object met de rest van de string. Zo heb je voor alle commando's een aparte functie, alleen gewrapt in een klasse.

_{deze code zal wel niet werken, maar het gaat om het idee..}

[H!GHGuY]

writser zoekt wel degelijk wat .oisyn en co aangeven.

die dingen zijn eigenlijk gewoon statenmachines die regexp'en parsen.
evt kun je zelf die statenmachine in elkaar stoppen maar telkens er een commando bijkomt...

wat ik gedaan heb bij die Contest is het volgende:
het protocol staat vast. Je weet op elke moment wat de volgende commando's kunnen zijn.
dus je kan enkel gaan testen op de commando's die je verwacht.
ik gebruik daar een simpele sscanf voor.

[writser]

.oisyn, wat bedoel je precies met een lookup-tree voor parsers? Googlen levert niet echt veel bruikbare informatie op. En wat vind je van de oplossing die ik met de QList heb geimplementeerd? Andrew, ik gebruik nu ongeveer dezelfde oplossing als jij, maar met een statische parse-functie. Bedankt voor alle reacties!

[farlane]

Jullie gooien het telkens op een parser probleem, maar ik krijg de indruk dat het om een ontwerp probleem gaat bij de TS. Of zie ik dat fout?

[writser]

Dat klopt. Het maken van een parser is niet zo moeilijk, maar ik vraag me af hoe ik dat het beste in mijn project kan integreren. Ik vind de oplossing van .oisyn er wel aardig uitzien. Hoe zou jij het aanpakken dan?

[farlane]

Wat je wil is als er een nieuw commando komt. je niet op heel veel verschillende plekken dingen moet wijzigen.

Om zo een commando object te maken, voldoet de methode van .oisyn goed: Een nieuw commando betekend een extra registratie bij je CommandoFactory object. Maar daarmee los je alleen het 'create' gedeelte van de lifetime van je commando object op.

Daarna zou je alle akties die bij een commando horen ook moeten isoleren zodat je 'protocol engine' kan blijven werken met de constante interface die een commando heeft, en de afwijkende delen bij het commando zelf, of in 'companion classes' worden afgehandeld.

[ Voor 4% gewijzigd door farlane op 15-11-2005 12:20 ]

[.oisyn]

writser schreef op maandag 14 november 2005 @ 18:53:
[...]

Hoe pak je zoiets precies aan? Elke afgeleide klasse heeft dan een functie static Message * parse(Qstring line). Op welke manier kun je die registreren in de abstracte klasse? Ik ben nog niet zo'n held met functie-pointers.

Waarom functie-pointers? Maak een mooie klasse met virtual functies

C++:

class Parser
{
    virtual Message * parse(const QString & message) = 0;
};

class UserEnterMessageParser : public Parser
{
    UserEnterMessage * parse(const QString & message);
};

En wat ik bedoelde met lookup-tree: de meeste echte parsers die werken volgens een grammatica zijn in feite een hele grote statemachine. Ze baseren hun volgende state op de volgende k tokens in de tokenstream (meestal k=1), en die statemachine is gegenereerd aan de hand van de grammatica.

Nu heb je hier niet echt iets ingewikkelds met geneste structuren e.d.. In feite heb je 2 soorten tokens: een string en een getal. Daarnaast wil je de string soms als algemeen matchen, maar soms ook expliciet ("USER" is bijvoorbeeld een string die je precies zo wilt matchen, bij de username die erna komt wil je gewoon elke string matchen en niet een specifieke username). Dus een rule voor een message is vrij simpel: een array waarbij elk element een van deze 3 mogelijkheden weergeeft.

Als je al deze rules verzameld hebt, kun je een boomstructuur maken. Een beetje vergelijkbaar met de T9 berichtinvoer van je telefoon: bij een toetsindruk ga je een niveau dieper in de boom om zo de woorden te vinden die voldoen aan de ingevoerde letters. Bij deze parser gaat het precies hetzelfde. Stel je zou een rule hebben voor {"USER" getal string} en een {"USER" string getal}, dan staat er in de rootnode van de boom een node die aangeeft dat "USER" gematched moet worden. Daaronder staan weer twee nodes, één die aangeeft dat je een getal moet matchen, en de ander een string. In de bladeren van de boom vind je vervolgens een referentie naar de parser die het hele bericht omzet naar een Message.

Maar in feite is dit nog steeds overkill: elk soort bericht heeft zijn eigen begincommando. In principe kun je dus voldoen aan een std::map<std::string, Parser*> oid, zodat je in één keer de juiste parser kunt ophalen aan de hand van het eerste woord in het bericht.

[writser]

De map is inderdaad een heel goed idee. Ik gebruik nu nog een list voor wat testwerk, maar later zal ik deze omzetten naar een map. Ook een multimap lijkt me redelijk efficient als er ooit strings komen die niet direct herkenbaar zijn aan het eerste token.

Nu de AI nog ..