linux-l: Wie schreibt man Parser?

Wolfgang Metze metze at trionet.de
Sa Nov 22 09:41:14 CET 1997


Oliver Bandel schrieb:

> Hallöchen!
>
> On Thu, 20 Nov 1997, Wolfgang Metze wrote:
>
> > Oliver Bandel schrieb:
> >
> > > Hi!
> > >
> > > Steht eigentlich schon alles im Betreff.
> > >
> >
> > Parser schreibt man: P A R S E R
> >
> > Aber das war wohl doch nicht Deine Frage oder?
>
> Hahaha, ich habe selten so ... versucht zu ... lachen.



> Habe ich "Parser" im Betreff in Anführungszeichen gesetzt?
>
> Nein!
>
> Also fragte ich nach was anderem.
>
> Aber Du hast es glücklicherweise noch mitbekommen:
>

Ja, bin doch nicht so blöd, wie ich aussehe :-)

> >
> > Spaß beiseite.
>
> Ja, bitte!     ... also wirklich!
>

Kein Problem.

> >
> > Parser schreibt man am Besten mit der Hand.
>
> Mit Füler, oder Kugelschreiber?
> Oder meintest Du mit Fingermalfarben?
>

Nein, direkt kodiert.

> [...]
> > Aus diesem Grund werden diese Teile meist
> >
> > von Hand implementiert, weil Generatoren keinen so effizienten Code
> > erzeugen.
>
> Das habe ich vermutet; aber für den Anfang (Versuchsstadium)
> vielleicht
> doch geeignet?
>

Ich glaube nicht. Die Zeit, die Du zur Konfiguration von Generatoren
benötigst, istgrößer, als die zur Implementierung eines Parsers.


> Oder sollte man Lisp nutzen (wegen rekursiven Problemen)?
>

Großer Gott, bloß nicht.

> Ich wollte das eigentlich gerne in C implementieren.
>

Gute Idee!

> [...]
> > Liegt dem Ganzen eine Grammatik zugrunde?
>
> Ja.
> Gibt es auch Parser, die in keiner Grammati etwas parsen sollen?
> Wie soll das gehen?
> Oder meinst Du, es wäre eine NICHT BEKANNTE Grammatik?
>
> (Wie wäre es mit einem Semantik-Parser?! (!!!)  (KI) )
>

Macht eigentlich jeder Compiler. Dafür sollte man aber eine
attributierte Grammatik haben.

> > Wenn ja, ist
> > es eine LL(1)-Grammatik?
>
> Kann ich nicht beurteilen, denn ich weiß nicht, was eine
> LL(1)-Grammatik
> ist. Wüßte ich das, wäre ich vermutlich der Lösung des Parser-Problems
>
> so nahe, daß ich hier nicht mehr  fragen müßte...
>
> Was also ist eine LL(1)-Grammatik?
>

Ein effizientes parsieren des Quelltextes bedeutet, daß Du wie beim
normalen Lesen von links nach rechtsden Text durchquerst. Dafür steht
das erste L (Left to right). Das Zweite L steht für Look-ahead. Damit
ist das bzw. die Symbole
gemeint, die vorrausschauend eingelesen wurden. Im obigen Beispiel 1
Symbol. Eine LL(1)-Grammatik ist also meiner Meinung
nach notwendig, um eine Sprache effizient verarbeiten zu können. Ist
eine Grammatik nicht LL(1), sondern vielleicht LALR(1)
oder sonst was, so kann es passieren, daß Du die Hälfte der Zeile
eingelesen hast, aber dann noch einmal x Zeichen nach links wandern muß,

weil aufgrund der Symbole in der Grammatik nicht entschieden werden
kann, welche Ableitungsregel verwendet werden soll.
Ein Symbol ist übrigens nicht mit Zeichen zu werwechels. Das
Wertzuweisungszeichen := in Pascal wäre ein Symbol, genauso wie der
Punkt
oder das Schlüsselwort BEGIN, das aus mehreren Zeichen besteht.



> > Wenn ja, ist alles ziemlich einfach, wenn nein,
> > solltest Du
> > daraus eine LL(1)-Grammatik machen.
>
> Tja. Angenommen, ich müßte das machen.... wie geht das?
>
> Geht es darum, daß man verschachtelte Parsing-Probleme auf
> nicht-verschachtelte reduziert?

Nein, das hat damit nichts zu tun. s.o.

> Wenn ja: Wie geht man da am besten vor?
>
> >
> >
> > > Irgendwelche schlauen Hinweise, oder Praxistips?
> > >
> >
> > Ja, ich habe schon einige Parser geschrieben. Aber wie gesagt, ein
> > bißchen konkreter solltest Duwerden.
>
> Erst mal - für den Anfang -  geht es darum, LaTeX-Grammatik zu
> erkennen. Welche Textabschnitte sind wie mit den Markups versehen
> worden?

Hm, ich kenne LaTex leider nicht. gibt es dafür eine Grammatik, wenn ja,
mail sie mir mal bitte.

>
>
> Welcher Buchstabe hat welchen Status (Layout-Status z.B.), usw.
>
> Später geht das ganze vielleicht mal in Richtung SGML.
>
> Ich will für ein Programm LaTeX-Code einerseits generieren, und
> andererseits auch analysieren.
>
> Tschüß,
>     Oliver
>
> P.S.: Und warum icht eines Tages wirklich mal ne semantische Analyse
>       versuchen? (...)


Kein Problem. Hängt alles nur davon ab, wie Du Deinen Ableitungsbaum
organisierst.

Ach ja, Literatur.

Niklaus Wirth hat ein sehr einfach zu lesendes Buch geschrieben:
"Compilerbau". Ist sehr dünn und
wirklich leicht verständlich.
Sollte das nicht reichen, gibt es ein größeres und weitergehendes von
Wilhelm/Maurer: Übersetzerbau,
erschienen im Springer-Verlag ISBN 3-540-55704-0.
Solltest Du aber ein Mathe-Guru sein, so wär das folgende Buch genau
richtig:
Hans zima: Compilerbau I/II, Wissenschaftsverlag
Gruß

Wolfgang

--
Wolfgang Metze
TrioNet Datentechnik GmbH
Roonstr. 39
12203 Berlin
Phone: +49 30 84471603
Fax: +49 30 84471605
e-mail: metze at trionet.de






Mehr Informationen über die Mailingliste linux-l