Parser & Lexer in C++

[Andreas Tscharner]

Hallo Welt,

In meinem kleinen OpenSource Projekt[1] parse ich eine Datei
zeilenweise. Im Moment geschieht dies mittels fgets und strtok (ugh).
Nun moechte ich das ganze in Zukunft etwas flexibler machen und frage
mich, was heute denn zum Parsen so verwendet wird. Ist das immer noch
Lex und Yacc? Oder gibt's da etwas anderes, bzw. etwas C++ - spezifischeres?

Anforderungen:
* GPL oder kompatibel (um mit GPL verwendet werden zu koennen)
* Entweder auf einem typischen (C++)Entwicklersystem vorhanden oder
klein genug, um allenfalls mit dem Source-Code ausgeliefert werden zu
koennen.

Danke im Voraus
Andreas

[1] https://bitbucket.org/StarFire/lrc/overview
--
Andreas Tscharner an...@vis.ethz.ch
--------------------------------------------------------------------
Gordon's Law:
If you think you have the solution, the question was poorly phrased.

[Edzard Egberts]

> In meinem kleinen OpenSource Projekt[1] parse ich eine Datei
> zeilenweise. Im Moment geschieht dies mittels fgets und strtok (ugh).

*g*

> Nun moechte ich das ganze in Zukunft etwas flexibler machen und frage
> mich, was heute denn zum Parsen so verwendet wird. Ist das immer noch
> Lex und Yacc? Oder gibt's da etwas anderes, bzw. etwas C++ -
> spezifischeres?

Ich habe mal geguckt, was Du überhaupt willst und so etwas wie Lex kann
man mit C++ eigentlich recht einfach selber realisieren. Mal so einen
Ansatz mit kleinen Fehlern, weil nicht compiliert, aber die Idee sollte
klar sein:

using namespace std;

typedef int token;
typedef vector< string > td_vector_string;
typedef map< string, token, less< string> > td_map_string_token;
typedef vector< token > td_vector_token;

td_map_string_token TMap; // Mit Map parsen!
TMap["print"]= 1;
TMap["load"]= 2;
TMap["goto"]= 3;

string Zeile; // Zum Einlesen
std::getline(In, Zeile); // Zeile einlesen und zerlegen:
td_vector_string Worte; // die Bestandteile der Zeile
string Wort; // Zum Einlesen
for (unsigned i= 0; i< Zeile.size(); ++i)
if (!whitespace()) Wort.push_back(Zeile[i]);
else {
Worte.push_back(Wort);
Wort.clear();
}
// Mit Map Worte parsen:
td_vector_token VT;
for (unsigned i= 0; i< Worte.size(); ++i)
VT.push_back(TMap[Worte[i]]);

// end

An der Stelle hätte man in VT für jedes Wort entweder das entsprechende
Token, oder für unbekannte Worte die Null. Na ja, und alle Worte in der
Map, das kann verbessert werden und auch gleich noch die Nummern
auswerten (da braucht man dann ein VT[ struct{ token, double }]).

Also wenn Du auf C-String-Level arbeitest, ist der Schritt auf C++
vielleicht schon ausreichend, so dass Du gar keine Bibliothek brauchst
und trotzdem mit einem Bruchteil des C-Codes hinkommst. Hat eben den
Vorteil, dass man sich die genau passende Lösung schneidern kann...
Die Funktion whitespace() wäre dann natürlich auch ToDo. ;o)

[Tim Landscheidt]

Andreas Tscharner <an...@vis.ethz.ch> wrote:

> In meinem kleinen OpenSource Projekt[1] parse ich eine Datei
> zeilenweise. Im Moment geschieht dies mittels fgets und
> strtok (ugh). Nun moechte ich das ganze in Zukunft etwas
> flexibler machen und frage mich, was heute denn zum Parsen
> so verwendet wird. Ist das immer noch Lex und Yacc? Oder
> gibt's da etwas anderes, bzw. etwas C++ - spezifischeres?

> Anforderungen:
> * GPL oder kompatibel (um mit GPL verwendet werden zu koennen)
> * Entweder auf einem typischen (C++)Entwicklersystem
> vorhanden oder klein genug, um allenfalls mit dem
> Source-Code ausgeliefert werden zu koennen.

> [...]

Wenn ich das richtig sehe, parst Du ausschlie�lich Zeilen.
Da kann man nat�rlich mit (f)lex sch�ne Automaten bauen, ich
w�rde aber wahrscheinlich einfach einen regul�ren Ausdruck
nehmen und dann zu regexec()/PCRE greifen.

Was nat�rlich auch immer eine �berlegung wert ist: Nach be-
stehenden Parsern f�r Konfigurationsdateien umsehen - Du
verwendest an anderer Stelle beispielsweise ja schon XML -
und das Format der Datei anpassen.

Tim

[Christoph Moench-Tegeder]

## Andreas Tscharner <an...@vis.ethz.ch>:

> In meinem kleinen OpenSource Projekt[1] parse ich eine Datei
> zeilenweise. Im Moment geschieht dies mittels fgets und strtok (ugh).
> Nun moechte ich das ganze in Zukunft etwas flexibler machen und frage
> mich, was heute denn zum Parsen so verwendet wird. Ist das immer noch
> Lex und Yacc? Oder gibt's da etwas anderes, bzw. etwas C++ - spezifischeres?

Lex/Yacc ist immernoch gut. C++-spezifisch wäre z.b. Boost.Spirit (in
boost enthalten, kann also vermutlich voraussetzen?) FSF/Gnu hält die
Boost Software License auch für GPL-kompatibel.

Gruß,
Christoph

--
Spare Space

[Achim Peters]

Am 16.01.2013 18:56, schrieb Andreas Tscharner:
> In meinem kleinen OpenSource Projekt[1] parse ich eine Datei
> zeilenweise. Im Moment geschieht dies mittels fgets und strtok (ugh).
> Nun moechte ich das ganze in Zukunft etwas flexibler machen und frage
> mich, was heute denn zum Parsen so verwendet wird. Ist das immer noch
> Lex und Yacc?

Falls noch nicht bekannt: Alternativ GNUs flex und bison (der Name ist
kein Zufall).

Oder fï¿œr Hardliner und "Trau keinem Programm, das Du nicht selbst
geschrieben hast"-Fans: Das Dragon-Book (wahlweise green, red oder
purple) von Aho, Seti, Ullman et al.

Bye
Achim

[Volker Birk]

Andreas Tscharner <an...@vis.ethz.ch> wrote:
> zeilenweise. Im Moment geschieht dies mittels fgets und strtok (ugh).
> Nun moechte ich das ganze in Zukunft etwas flexibler machen und frage
> mich, was heute denn zum Parsen so verwendet wird. Ist das immer noch
> Lex und Yacc? Oder gibt's da etwas anderes, bzw. etwas C++ - spezifischeres?
> Anforderungen:
> * GPL oder kompatibel (um mit GPL verwendet werden zu koennen)
> * Entweder auf einem typischen (C++)Entwicklersystem vorhanden oder
> klein genug, um allenfalls mit dem Source-Code ausgeliefert werden zu
> koennen.

http://www.boost.org/doc/libs/1_52_0/libs/spirit/doc/html/index.html

Viele Grüsse,
VB.
--
Wenn Steinbrück „Urwahl“ hört, ruft der „Rolex!“

(Friedrich Küppersbusch)

[Jan Andres]

On 2013-01-16, Tim Landscheidt <t...@tim-landscheidt.de> wrote:
> Andreas Tscharner <an...@vis.ethz.ch> wrote:
>
>> In meinem kleinen OpenSource Projekt[1] parse ich eine Datei
>> zeilenweise. Im Moment geschieht dies mittels fgets und
>> strtok (ugh). Nun moechte ich das ganze in Zukunft etwas
>> flexibler machen und frage mich, was heute denn zum Parsen
>> so verwendet wird. Ist das immer noch Lex und Yacc? Oder
>> gibt's da etwas anderes, bzw. etwas C++ - spezifischeres?
>
>> Anforderungen:
>> * GPL oder kompatibel (um mit GPL verwendet werden zu koennen)
>> * Entweder auf einem typischen (C++)Entwicklersystem
>> vorhanden oder klein genug, um allenfalls mit dem
>> Source-Code ausgeliefert werden zu koennen.
>
>> [...]
>

> Wenn ich das richtig sehe, parst Du ausschließlich Zeilen.
> Da kann man natürlich mit (f)lex schöne Automaten bauen, ich
> würde aber wahrscheinlich einfach einen regulären Ausdruck

> nehmen und dann zu regexec()/PCRE greifen.

Da der OP etwas C++-spezifisches sucht, würde sich hier natürlich auch
boost::regex anbieten bzw. später mit C++11 dann std::regex. Letzteres
ist vom API her weitgehend mit boost::regex identisch (man kann einfach
den Namespace austauschen). Im Moment ist std::regex allerdings
zumindest in der STL vom gcc noch nicht vollständig implementiert.

Außerdem fällt mir spontan noch ANTLR ein, das wurde wohl bislang nicht
erwähnt. Funktioniert ähnlich wie flex und bison (welche man den
"originalen" lex und yacc definitiv vorziehen sollte), fühlt sich für
mich dabei aber etwas "moderner" an und integriert Lexer- und
Parsergenerator in einem Tool. Die Version, die C++ generieren kann, ist
aber etwas obskur und schwer zu finden, daher evtl. für ein Open-Source-
Projekt nicht optimal. Die im Netz verfügbare Doku zu ANTLR ist auch
eher "so mäßig", man sollte wohl das entpr. Buch vom Autor der Software
kaufen, wenn man ernsthaft damit arbeiten will. Solange die Grammatik
nicht allzu komplex wird, ist das wahrscheinlich Overkill.

[Ulrich....@gmx.de]

In <qRBJs.29418$kp4....@newsfe09.iad> Andreas Tscharner <an...@vis.ethz.ch> writes:

>Hallo Welt,

>In meinem kleinen OpenSource Projekt[1] parse ich eine Datei
>zeilenweise. Im Moment geschieht dies mittels fgets und strtok (ugh).
>Nun moechte ich das ganze in Zukunft etwas flexibler machen und frage
>mich, was heute denn zum Parsen so verwendet wird. Ist das immer noch
>Lex und Yacc? Oder gibt's da etwas anderes, bzw. etwas C++ - spezifischeres?

Also die Klassiker sind ja genannt worden, aber wenn Du etwas
interessanteres haben m�chtest kann ich Dir ANTLR http://www.antlr.org/
empfehlen:

>Anforderungen:
>* GPL oder kompatibel (um mit GPL verwendet werden zu koennen)

Abgehakt

>* Entweder auf einem typischen (C++)Entwicklersystem vorhanden oder
>klein genug, um allenfalls mit dem Source-Code ausgeliefert werden zu
>koennen.

Es gibt .deb-Pakete (zumindestens f�r Debian), klein ist's im Vergleich zu
FLEX und BISON nicht zu nennen. Der gr��te Nachteil (IMHO) ist das es unter
Java l�uft, aber daf�r kannst Du ein Tool benutzen um den Scanner, den Parser
und einen Tree-Walker zu erzeugen. Ausserdem kommt da echtes C++ raus, was
man auch debuggen kann, wenn's denn sein mu� (das ist f�r mich ein
wesentlicher Punkt).

[del]

>[1] https://bitbucket.org/StarFire/lrc/overview

Ein Resource Compiler? IMHO v�llig unn�tig, tar oder cpio tun's auch. Aber
jeder wie er mag,

CU,
Uli
--
Dipl. Inf. Ulrich Teichert|e-mail: Ulrich....@gmx.de | Listening to:
Stormweg 24 |Pale Bride (The Von Bondies), Slip Away (Sedatives)
24539 Neumuenster, Germany|Sacred Decay (The Estranged), She's Lost Control

[Jan Andres]

On 2013-01-17, Ulrich....@gmx.de <Ulrich....@gmx.de> wrote:
> [ANTLR]
>
> Es gibt .deb-Pakete (zumindestens für Debian), klein ist's im Vergleich zu
> FLEX und BISON nicht zu nennen. Der größte Nachteil (IMHO) ist das es unter
> Java läuft, aber dafür kannst Du ein Tool benutzen um den Scanner, den Parser

> und einen Tree-Walker zu erzeugen. Ausserdem kommt da echtes C++ raus, was

> man auch debuggen kann, wenn's denn sein muß (das ist für mich ein
> wesentlicher Punkt).

Diese Syntax-Tree-Geschichten werden aber doch nicht unterstützt, wenn
man ihn C++ generieren lässt, oder? Steht zumindest so im Wiki [1] und
deckt sich auch mit meinen Erfahrungen beim Ausprobieren. Oder habe ich
irgendwas übersehen?

[1] http://www.antlr.org/wiki/pages/viewpage.action?pageId=29130834

[Ulrich....@gmx.de]

In <kd928t$6eq$1...@dont-email.me> Jan Andres <J...@nAndr.es> writes:

>On 2013-01-17, Ulrich....@gmx.de <Ulrich....@gmx.de> wrote:
>> [ANTLR]
>>

>> Es gibt .deb-Pakete (zumindestens f�r Debian), klein ist's im Vergleich zu
>> FLEX und BISON nicht zu nennen. Der gr��te Nachteil (IMHO) ist das es unter

>> Java l�uft, aber daf�r kannst Du ein Tool benutzen um den Scanner, den Parser

>> und einen Tree-Walker zu erzeugen. Ausserdem kommt da echtes C++ raus, was

>> man auch debuggen kann, wenn's denn sein mu� (das ist f�r mich ein
>> wesentlicher Punkt).

>Diese Syntax-Tree-Geschichten werden aber doch nicht unterst�tzt, wenn
>man ihn C++ generieren l�sst, oder? Steht zumindest so im Wiki [1] und

>deckt sich auch mit meinen Erfahrungen beim Ausprobieren. Oder habe ich

>irgendwas �bersehen?

ANTLR ist ziemlich im Fluss. TreeWalker gab's in Version 2 f�r alle Targets,
das ist auch etwas anders als die ParseTrees der Version 3, die Du meinst.
Immerhin hei�en die Klassen tats�chlich anders ;-)

Ich mu� auch zugeben das ich keine 3er-Versionen je benutzt habe, es gab
f�r mich keinen zwingenenden Grund ;-)

[Andreas Tscharner]

On 16.01.2013 18:56, Andreas Tscharner wrote:

> mich, was heute denn zum Parsen so verwendet wird. Ist das immer noch
> Lex und Yacc? Oder gibt's da etwas anderes, bzw. etwas C++ -
> spezifischeres?

Danke fuer Eure Vorschlaege. Ich werde mal abwarten, ob gcc 4.8 die
RegEx implementiert, oder andernfalls auf Flex/bison ausweichen.

Gruss
Andreas

[Rainer Weikusat]

Andreas Tscharner <an...@vis.ethz.ch> writes:
> On 16.01.2013 18:56, Andreas Tscharner wrote:
>
>> mich, was heute denn zum Parsen so verwendet wird. Ist das immer noch
>> Lex und Yacc? Oder gibt's da etwas anderes, bzw. etwas C++ -
>> spezifischeres?
>
> Danke fuer Eure Vorschlaege. Ich werde mal abwarten, ob gcc 4.8 die
> RegEx implementiert, oder andernfalls auf Flex/bison ausweichen.

Es gibt alle moeglichen Parser-Generatoren und die sind auch nicht
wirklich kompliziert zu finden. Die Wikipedia-YACC-Seite hat zB einen
Link auf einen laengliche Vergleichstabelle solcher Programme/
Bibliotheken. Persoenlich wuerde ich Dir den Vorschlag machen,
entweder auf eine Konfigurationsdatei zu verzichten (zB lassen sich
NAME=WERT-Paare wunderbar auf Shell-'Skriptlets' abbilden, die von der
Shell mit Hilfe eines 'startup'-Skripts geparst werden, welches dann
das eigentliche Programm mit entsprechenden Kommandozeilenparametern
oder Umgebungsvariablen aufruft) oder sowohl auf strtok als auch auf
einen Parser-Generator zu verzichten. Das waere aber wohl kaum die
Antwort, die Du hoeren wolltest.

NB: Ich arbeite seit laengerer Zeit unter anderem an dem
Flex/Bison-basierten racoon.conf-Parser, den ich um verschiedene
Features erweitern musste (ua Quoting von " in "-begrenzten Strings)
und ausserdem im letzten November in eine dynamische Bibliothek
verwandelt habe, weil ich dieses Konfigurationsdateien auch noch aus
einem Perl-Programm parsen muss, das 'irgendwann in der Zukunft'
dynamische racoon-Rekonfiguration zur Verfuegung stellen soll damit
'Kunden' ihre VPN-Endpoints als DNS-Namen definieren koennen, deren
Zuordnung zu tatsaechlichen Addressen sich 'bedarfsweise' (disaster
recovery) aendert. Wenn es diesen strukturlosen Texthaufen, der in
nahzeu unverstaendlichen Code uebersetzt wird, nicht bereits gaebe,
wuerde ich ihn weder mir noch anderen antun wollen.