[linux-l] Grammar Design

[Volker Grabsch]

On Sat, Sep 17, 2005 at 01:19:38PM +0200, Axel Weiß wrote:
> > Gerade wegen dem vielen Ausprobieren und Redesign sind mir lex/yacc
> > einfach zu aufwändig.
> 
> Huh?? Wenn man in der Klasse der LR1-Grammatiken bleibt, sind lex/yacc 
> (ala flex/bison) doch eine *erhebliche* Erleichterung! Was ist daran zu 
> aufwändig?! Wenn man allerdings diese Klasse verlässt, sind andere 
> Werkzeuge/Programmiersprachen generell geeigneter. (Wie man am Beispiel 
> des GCC sieht, kann man mit flex/bison auch Nicht-LR1-Grammatiken 
> implementieren. Das Ganze wird aber recht krampfig, und die Grammatik 
> ist in den yacc-Dateien nicht mehr wiederzufinden. Schaut mal in die 
> GCC-Quellen...).

Dieser gesamte Absatz geht nicht im Geringsten auf mein Geschriebenes ein.
Natürlich ist lex+yacc eine wesentliche Erleichterung im Vergleich
zum Schreiben des Parsers per Hand, das habe ich nirgends bestritten!

Es geht darum, dass es aber /noch/ besser geht. Schau dir einfach
mal pyparser an. Auch dort geht es um LR1-Grammatiken. Aber für viele
typische Sprachen, vorallem für Programmiersprachen (darum ging es dem OP),
ist pyparser besser geeignet, d.h. man kommt schneller zum Ziel. Der
entstehende Parser wird sicher nicht so schnell sein wie ein lex/yacc-
Konstrukt, aber die Entwicklungszeit ist kürzer. Und genau darauf kommt
es an, wenn es um "viel Ausprobieren und Redesign" geht.


> > Doch selbst wenn feststeht, dass du es in C machen willst, rate ich
> > dennoch an, gerade diese Ausprobieren/Verwerfen - Phase mit besseren,
> > einfacheren Tools zu beschreiten (z.B. mit pyparser). Danach die Sache
> > nach lex/yacc zu bringen (besser gesagt: flex/bison), ist mehr oder
> > weniger trivial, also IMHO das kleinere Übel.
> 
[...]
> Für LR1-Grammatiken gibt es derzeit nichts effizienteres als 
> flex/bison,

Bezogen auf die Laufzeit: Ja.
Habe ich nie bestritten!

Bezogen auf die Entwicklungszeit: Nein.
Pyparser hat z.B. direkte Konstrukte für
	- "eins oder viele von ..."
	- "liste gleichartiger Elemente,
           durch gewisse Separator-Elemente getrennt".
	- [...]
Solche Sachen muss man in yacc erstmal umschreiben. Das sind aber nicht
die einzigen Vorzüge von pyparser.


Ich rate zu stärkeren Werkzeugen, wie z.B. pyparser, weil dort dieser
"ändern, ausprobieren, ändern, ..."-Zyklus (inkrementelle Programmierung)
eben kürzer ist. Wenn man erstmal seine Grammatik gefunden hat, also
genug "rumprobiert" hat, kann man sich immer noch überlegen,
ob man bei Python+pyparser bleibt, oder man diese Grammatik nun nach
lex+yacc+C übersetzt. Dieser Weg ist IMHO mit viel weniger Aufwandt
verbunden, als wenn man gleich zu Anfang alles in lex+yacc machen würde.

Ich persönlich würde sogar empfehlen, auch die Codegenerierung bzw.
den Interpreter erstmal in einer "high-level"-Programmiersprache
wie Python zu implementieren, und dieses Python-Programm dann als
"Bauplan" für ein lex+yacc+C Programm zu nutzen, weil das insgesamt
schneller geht, und weil man dann schonmal einen sauber und
übersichtlich programmierten Prototyp hat, der sogar lauffähig ist
und den man schon gründlich ausgetestet hat. Design-Fehler in einem
Python-Programm auszumärzen ist nämlich sehr viel angenehmer, als ein
C-Programm zu restrukturieren.

Außerdem stehen die Chancen nicht schlecht, dass die Performance von
Python+pyparser für die Zwecke des OP schon völlig ausreichen. Dann
kann er sich sogar die Reimplementierung in lex+yacc+C komplett sparen.
Um das besser einzuschätzen, wäre es gut, wenn er uns erklären könnte,
was genau er eigentlich vor hat.


Viele Grüße,

	Volker

-- 
Volker Grabsch
---<<(())>>---
Administrator
NotJustHosting GbR