In diesem Beitrag geht es (i) um die Verallgemeinerung eines Text-Parsers zum Parsen beliebiger Objektfolgen mit Hilfe zweier Stacks und (ii) um Parser, die ich RewriteParser nenne, und deren Kombination mit einem ganz speziellen RewriteParser-Kombinator, RPC*. Ich habe auf eine konkrete Programmiersprache verzichtet, damit das Prinzip klarer zutage tritt.
Um die Idee der Parser-Kombinatoren nicht auf das Parsen von Zeichenketten zu beschränken, verallgemeinern wir die Idee, parsen beliebige Objekte von einem Stack und legen die Ergebnisse auf einem anderen Stack ab. Ein Parser (und somit auch ein Parser-Kombinator) nimmt zwei Stacks entgegen, ich nenne sie inStack und outStack, und liefert neben einem Flag für erfolgreiches Parsen zwei Stacks zurück, inStack' und outStack'. Zur Info: meine Stacks sind funktional, sprich immutabel.
Was macht ein Parser generell? (1) Er prüft, ob ein bestimmtes Muster auf dem inStack zu finden ist -- dafür gibt es eine Funktion Crit(erion):Stack->Bool. (2) Er konsumiert kein oder mehr Elemente vom inStack -- die konsumierende Funktion heiße Consume:Stack->Stack. (3) Er produziert kein oder mehr Elemente für den Ausgabe-Stack -- der produzierte Stackanteil werde über Produce:Stack->Stack erzeugt.
Wir können das etwas formaler beschreiben mit P(arser), Consume und Produce als Funktionen und SUCCESS = True, FAILURE = False. Der '+'-Operator produziert einen neuen Stack aus dem Aneinanderhängen zweier gegebener Stacks.
P(Crit,Consume,Produce)(inStack,outStack) --> success,inStack',outStack'
if !Crit(inStack): return FAILURE, inStack, outStack
return SUCCESS, inStack', outStack'
with inStack' + Consume(inStack) == inStack
and outStack' == outStack + Produce(inStack)
Die "with"-Schreibweise ist vielleicht etwas ungewöhnlich, aber sie besagt nur, dass der inStack' ein um Consume(inStack) reduzierter inStack ist. Und dass der outStack immer nur um Produce(inStack) anwachsen kann zu outStack'. Ich nutze für die Stackreduktion weiter unten kurzfristig auch das "-":
inStack' == inStack - Consume(inStack)
Ein Parser-Kombinator, der ein oder mehr Parser in irgendeiner Weise verknüft (bisweilen ist die Verknüpfung konfigurierbar), muss sich an dieselben Spielregeln halten: er ist auch wieder ein Parser, der möglicherweise Teile vom inStack oder den ganzen inStack konsumiert und möglicherweise etwas zum outStack beiträgt. Beachten Sie nochmal, dass Konsum und Produktion ausschließlich eine Funktion vom inStack sind! Der outStack kann z.B. als Gedächtnis nicht genutzt werden!
Nachfolgend beschreibe ich einen Parser-Kombinator der zwei Parser komponiert: PC kombiniert zwei Parser
P1 = P(Crit1,Consume1,Produce1) und P2 = P(Crit2,Consume2,Produce2):
PC(P1,P2)(inStack, outStack) --> success, _inStack, _outStack
success', inStack', outStack' = P1(inStack, outStack)
if !success': return FAILURE, inStack, outStack
success'', inStack'', outStack'' = P2(inStack', outStack')
if !success'': return FAILURE, inStack, outStack
return SUCCESS, inStack'', outStack''
Man könnte auch für den Erfolgsfall zusammenfassen:
inStack'' == inStack' - Consume2(inStack') <==>
inStack'' == inStack - Consume1(inStack) - Consume2(inStack - Consume1(inStack))
und
outStack'' == outStack + Produce1(inStack) + Produce2(inStack)
Die Komposition zweier Parser tut genau das, was man erwartet: erst konsumiert der erste Parser etwas vom inStack und legt sein Ergebnis auf dem outStack ab, dann folgt der zweite Parser, der weiteres vom inStack konsumiert und zusätzlich etwas auf dem outStack ablegt.
Nachfolgende möchte ich eine Parser-Klasse vorstellen, die ich RewriteParser nenne. Sie verallgemeinern das Parser-Prinzip; sie sind aus meinen Spielereien und der Suche nach immer wieder neuen, verbesserten, generischeren Parser-Kombinatoren hervorgegangen. Allerdings hat es eine Weile gedauert, bis ich ihre neue Eigenschaft destilliert hatte.
Der Unterschied zum Parser ist: Der Rewrite-Parser (RP) kann den inStack modifizieren! Der outStack kann nachwievor nicht gelesen, sondern nur produzierend (d.h. mit der Ablage neuer Elemente) bedient werden.
RP(Crit,Rewrite,Produce)(inStack,outStack) --> success,inStack',outStack'
if !Crit(inStack): return FAILURE, inStack, outStack
return SUCCESS, inStack', outStack'
with inStack' == Rewrite(inStack)
and outStack' == outStack + Produce(inStack)
Die Modifikation ist gering. Rewrite ist ebenso wie Consume eine Funktion,
Rewrite:stack->stack. Sie konsumiert jedoch nicht nur einen Teil des inStack, sondern kann ihn vollständig umschreiben und beispielsweise neue Elemente auf dem inStack ablegen (z.B. als Gedächtnis etwa in Form von Annotationen). Der nachfolgende RewriteParser arbeitet dann mit diesem modifizierten inStack.Schauen wir uns jetzt einmal einen RewriteParser-Kombinator an, der zwei Parser in eine Kompositionsbeziehung miteinander bringt. Wir berücksichtigen nun wieder den outStack. Es gilt
RP1 = RP(Crit1,Rewrite1,Produce1), RP2 = RP(Crit2,Rewrite2,Produce2).
RPC(RP1,RP2)(inStack,outStack) --> success, _inStack, _outStack
success', inStack', outStack' = RP1(inStack,outStack)
if !success': return FAILURE, inStack, outStack
success'', inStack'', outStack'' = RP2(inStack',outStack')
if !success'': return FAILURE, inStack, outStack
return SUCCESS, inStack'', outStack''
Um das Kompositionsverhalten im Erfolgsfall verstehbar zu machen, auch hier wieder die Auflösung:
inStack'' == Rewrite2(inStack') <==> (mit inStack' == Rewrite1(inStack))
inStack'' == Rewrite2(Rewrite1(inStack))
Voila! Die Komposition zweier RewriteParser ist die Komposition ihrer Rewrite-Funktionen angewendet auf den inStack!
outStack'' == outStack' + Produce2(inStack')
outStack' == outStack + Produce1(inStack)
mit
inStack' == Rewrite1(inStack)
ergibt sich
outStack'' == outStack + Produce1(inStack) + Produce2(Rewrite1(inStack))
Das Ergebnis für den OutStack überrascht nicht. Hier legen RP1 und RP2 ihre Ergebnise der Verarbeitung von inStack bzw. inStack' ab
Wir können schon einmal festhalten: Die Kombination von RewriteParsern entspricht der Funktionskomposition plus Seiteneffekte!
Es gibt einen kleinen Kniff, der die Sache nun vollends interessant macht. Berücksichtigen wir bei der Komposition doch den Output von RP1, outStack', beim Input von RP2. Damit ist es nicht mehr nötig, RP2 als Ausgabe-Stack outStack' zu geben, da er den prinzipiell bei Produce berücksichtigen kann, sondern outStack. Ebenso benötigt RP1 nun nur einen EMPTYSTACK.
Diesen modifizierten RPC bezeichne ich RPC*.
RPC*(RP1,RP2)(inStack,outStack) --> success, _inStack, _outStack
success', inStack', outStack' = RP1(inStack,EMPTYSTACK)
if !success': return FAILURE, inStack, outStack
success'', inStack'', outStack'' = RP2(inStack'+outStack',outStack)
if !success'': return FAILURE, inStack, outStack
return SUCCESS, inStack'', outStack''
Es ergibt sich nun für inStack'':
inStack'' == Rewrite2(inStack'+outStack')
inStack' == Rewrite1(inStack)
outStack' == EMPTYSTACK + Produce1(inStack)
---
inStack'' == Rewrite2(Rewrite1(inStack)+Produce1(inStack))
Und für outStack'' ergibt sich:
outStack'' == outStack + Produce2(inStack'+outStack')
outStack'' == outStack + Produce2(Rewrite1(inStack)+Produce1(inStack))
Das Ergebnis hat zwei bemerkenswerte Eigenschaften. Zum einen: Darin ist vollständig der Parser-Kombinator RPC nachbildbar über geeignete Rewrite- und Produce-Funktionen. RPC* ist also erheblich mächtiger. Zum anderen: Es kommt wunderbar aus, dass das Argument zu Rewrite2 in inStack'' und zu Produce2 in outStack'' das gleiche ist! Das Ergebnis inStack'' kann entweder auf "normale" Funktionskomposition reduziert werden oder es bekommt ein Ergebnis einer Vorverarbeitung durch Produce1(inStack) dazu! Mit diesem Input arbeitet auch Produce2 und kann das Gedächtnis beim Hinzufügen eines Ergebnisses zu outStack berücksichtigen.
Für diejenigen, die sich mit konkatenativer Programmierung schon einmal befasst haben (siehe z.B. Factor, Joy oder Cat), sei verraten, dass sich das konkatenative Paradigma mit RewriteParsern und RPC* vollständig umsetzen lässt. Oder anders herum: Konkatenative Programmierung kann man verstehen als die Programmierung mit RewriteParsern, die durch PRC* komponiert werden.
Ich weiß, das war viel. Aber vielleicht werden Sie den Nutzen der RewriteParser erkennen, wenn Sie selber einmal mit Parser-Kombinatoren arbeiten und programmieren.
Posts
