Parserbau

[Danny]

Hi,

ich versuche gerade experimentell, selbst eine kleine Template-Engine zu entwickeln. Als Feature möchte ich auch verschachtelbare Elemente implementieren:

<!--( BLOCK 1 -->
  <!--( INCLUDE header.html test )-->
  <h1>Foo</h1>
  <p>Das ist ein Dummy-Text.</p>
  <!--( BLOCK 1.1 -->
    <p>Fusszeile</p>
  <!--)-->
<!--)-->

Das große Problem dabei ist der Algorithmus, der die Positionen der Token <!--( und )--> ermitteln soll. Allein mit regulären Ausdrücken komme ich wg. dem "nesting" nicht weit, da schon beim ersten Block das Ende der Include-Zeile markiert wird und nicht das eigentliche Ende des Blocks in der letzen Zeile.

Um die passenden Token zu finden, habe ich jetzt alle Positionen (Byte-Offset ab Stringanfang) der Tokens in einem Array gesammelt und will versuchen, durch Vergleich in mehreren Schleifen die korrekten Paare zu finden. Dabei fehlt mir aber irgendwie der Ansatz, ich komme einfach nicht auf die Lösung.

Vielleicht hat jemand von Euch schon mal sowas gemacht und kann mir einen Tipp geben...

Wäre echt nett!

freundlichen Gruß
Danny

[Darkboy]

Als Feature möchte ich auch verschachtelbare Elemente implementieren:

Waere es dann nicht sinnvoller fuer dich, die Bloecke im XML-Stil zu gestalten, d.h. mit einem oeffnenden und einem schliessenden Tag? Das vereinfacht sicher auch die Paarfindung.

[Danny]

Ja, wäre es. Daran hatte ich auch schon gedacht, weil ich dann auf einen XML-Parser zurückgreifen könnte.

Die Templates sollen jedoch nur HTML enthalten und mit jedem HTML-Editor gepflegt werden können. Deshalb die Kommentare, damit es auch trotz Template-Befehlen noch standardmäßiges HTML ist. Die Templates werden später auch von Anfängern mit Daten gefüllt, daher möchte/kann ich nicht valides XML oder XHTML voraussetzen.

MfG
Danny

[Daniel Thoma]

Hallo Danny,

<!--( BLOCK 1 -->
  <!--( INCLUDE header.html test )-->
  <h1>Foo</h1>
  <p>Das ist ein Dummy-Text.</p>
  <!--( BLOCK 1.1 -->
    <p>Fusszeile</p>
  <!--)-->
<!--)-->

Um solche verschachtelten Strukturen zu parsen musst Du mit einem Stack arbeiten. (Ein Stack ist eine Liste, bei der Du nur ein Element hinten anhängen oder entfernen kannst)
Wenn Du auf ein Startelement triffst legst Du es oben auf den Stack, wenn Du auf ein Endelement triffst, muss das entsprechende Startelement auf dem Stack liegen, so dass Du die Struktur überprüfen kannst.
Da Du immer das Startelement auf dem Stack liegen hast, wenn Du auf die entsprechenden Unterelemente stößt, kannst Du so auch recht einfach einen Syntaxbaum erzeugen. (wobei Du beim Verarbeiten von Templates natürlich direkt die Ersetzungen vornehmen solltest, da Du dann nicht die ganze Datei im Speicher halten musst)

Es gibt auch Parsergeneratoren, die aus einer formalen Beschreibung der Grammatik einen Parser erzeugen.
Wenn Du die Programmiersprache nennst, die Du verwenden willst, kann Dir vielleicht jemand einen nennen, der Parser in dieser Sprache erzeugt.
Das muss bei dieser Sprache aber nicht einfacher sein, zumindest, wenn man noch nie einen Parsergenerator benutzt hat.

Grüße

Daniel

[Danny]

Hi,

ich möchte PHP nutzen und den Aufwand so gernig wie irgend möglich halten. Wie bereits erwähnt, es soll eine relativ minimale und schnelle Engine werden, die aus wenigen Zeilen Code besteht. Das ist meine Hauptanforderung, sonst könnte ich ja auch einfach auf Smarty, etc.. zurückgreifen.

Notfalls werde ich aus ( vielleicht etwas wie n( machen, wobei n für die Verschachtelungstiefe steht. Bsp.:

<!--0( BLOCK A -->
  <!--(1 INCLUDE header.html test 1)-->
  <h1>Foo</h1>
  <p>Das ist ein Dummy-Text.</p>
  <!--1( BLOCK B -->
    <p>Fusszeile</p>
    <!--2( INCLUDE footer.html foo 2)-->
  <!--1)-->
<!--0)-->

Mit diesem Trick ist es zwar etwas umständlich zu schreiben, weil man die Tiefe manuell angeben muß aber dafür sehr simpel und effizient zu parsen.

MfG
Danny

[Henryk Plötz]

Moin,

Das große Problem dabei ist der Algorithmus, der die Positionen der Token <!--( und )--> ermitteln soll. Allein mit regulären Ausdrücken komme ich wg. dem "nesting" nicht weit, da schon beim ersten Block das Ende der Include-Zeile markiert wird und nicht das eigentliche Ende des Blocks in der letzen Zeile.

Ja, mit regulären Ausdrücken kannst du bei Sprachen wie HTML keinen Blumentopf gewinnen. Allerdings ist es auch so, dass Parser- bzw. Compilerbau an der Uni im Informatik-Grundstudium ein ganzes Semester belegt, also nicht in Eins,Fix,Drei zu erklären ist.

Ein einfacher Ansatz vielleicht: Zunächst mal baut man sich fast immer einen Scanner. Der tut nichts weiter als den einkommenden Bytestrom anzusehen und in Token zu zerlegen, wobei die Token zum Beispiel durch reguläre Ausdrücke beschrieben sind. Ein Token hat dann immer einen Typ und manchmal auch noch einen Wert. Praktische Token in deinem Fall scheinen mir KOMMENTARAUF (also '<--'), KOMMENTARZU ('-->'), KLAMMERAUF ('('), KLAMMERZU (')'), T_BLOCK ('BLOCK'), T_INCLUDE ('INCLUDE'), ZAHL (regulärer Ausdruck /[0-9]+/), STRING (regulärer Audruck /\S+/) und HTMLLITERAL (alles zwischen Dateianfang und dem ersten <!--, zwischen --> und dem nächsten <!--, sowie zwischen dem letzten --> und Dateiende) zu sein. (So nebenbei wirft der Scanner auch noch alle Leerräume zwischen den Token weg.)

Der Scanner stellt dann nur zwei Funktionen zur Verfügung: 'Zeige das nächste (oder die nächsten n, mehr dazu gleich) Token', und 'Konsummiere ein Token' (also bewege die Position im Zeichenstrom hinter das Token, um zu markieren dass es schon verarbeitet wurde). (Und aus Bequemlichkeit vielleicht noch ein 'Wenn das nächste Token vom Typ x ist, dann konsummiere es, sonst breche unter lautem Gezeter das Parsen ab'.)

Jetzt wäre der passende Moment, um eine Grammatik für deine Aufgabe zu basteln. Ich schlage mal einen einfachen, aber unvollständigen Teil vor, um dann gleich was zum Demonstrieren zu haben:

Start := (HTMLLITERAL | Block)*
Block := KOMMENTARAUF KLAMMERAUF T_BLOCK ZAHL KOMMENTARZU Anweisung* KOMMENTARAUF KLAMMERZU KOMMENTARZU
Anweisung := (HTMLLITERAL | Block)

Die vollständig großgeschriebenen Wörter sind dabei Terminale, die genau so aus dem Scanner fallen; die anderen sind Nichtterminale die von deinem Parser behandelt werden müssen. Als Parsertyp würde ich Recursive Descent vorschlagen, also rekursiven Abstieg. Der ist recht leicht zu bauen und auch zu verstehen (wenn man Funktionen und Rekursion verstanden hat). Dabei baut man einfach für jedes Nichtterminal eine Funktion, die die Terminale in der passenden Reihenfolge einsammelt, und ggbf. die Funktion eines anderen Nichtterminals aufruft.

Jetzt mal zu ein bisschen Code (aus Bequemlichkeit werde ich C-artigen Pseudocode nehmen). Dabei kommt es noch zu einer klitzekleinen Komplikation: Wenn du dir die Grammatik ansiehst, wirst du feststellen dass man nur mit Kenntnis des nächsten Tokens in der Block-Funktion nicht entscheiden kann, ob als nächstes eine Anweisung (die ja ein Block sein könnte, der mit KOMMENTARAUF beginnt) oder das Ende des Blockes kommt (welches ja auch mit KOMMENTARAUF beginnt). Deswegen brauchen wir einen vorrausschauenden Scanner (oder müssen die Grammatik umbauen). Ich übergebe der Einfachheit halber einfach an nexttoken eine Zahl die angibt das wievieltnächste Token (beginnend bei 0) ich haben möchte. Die Scannerfunktionen heissen dann in der oben beschriebenen Reihenfolge nexttoken(n), consumetoken() und asserttoken(x).

void Start(void)
{
 Token t;

while(t = nexttoken(0)) {
  switch(t.type) {
   case HTMLLITERAL:
    consumetoken();
    break;
   case KOMMENTARAUF:
    Block();
    break;
  }
 }
}

void Block(void)
{
 Token t;

asserttoken(KOMMENTARAUF);
 asserttoken(KLAMMERAUF);
 asserttoken(T_BLOCK);
 asserttoken(ZAHL);
 asserttoken(KOMMENTARZU);
 while(t = nexttoken(0)) {
  if(t.type == HTMLLITERAL)
   anweisung();
  if(t.type == KOMMENTARAUF) {
   Token u = nexttoken(1);
   if(u.type == KLAMMERZU)
    break;
   else
    anweisung();
  }
 }
 asserttoken(KOMMENTARAUF);
 asserttoken(KLAMMERZU);
 asserttoken(KOMMENTARZU);
}

void Anweisung(void)
{
 Token t = nexttoken(0);
 if(t.type == HTMLLITERAL) {
  consumetoken();
 } else {
  Block();
 }
}

Puh, das war's schon. Damit müsste man jetzt im Prinzip einfache verschachtelte Blöcke parsen können. (Abzüglicher aller Fehler natürlich, die ich eingebaut habe. Absichtlich und aus didaktischen Gründen, versteht sich ;-)

Das ganze kann man natürlich auch einfacher (naja) haben, indem man Parsergeneratoren benutzt. flex/lex und Bison/yacc zum Beispiel. Die ersten beiden sind dabei dafür da, Scanner zu bauen; die letzten beiden um damit Parser und Compiler zu basteln. (Zuerst genannt jeweils das freie GNU-Tool, das andere ist dann die Vorlage dafür gewesen.) Denen wirft man im Prinzip 'nur' die Regeln für die Token, bzw. die Grammatik vor und sie bauen dann daraus ein Programm welches Eingaben mit dieser Grammatik parsen kann.

[Danny]

Hey!

Vielen, vielen Dank, Mann - Du hast es echt drauf !!!
Ich weiß schon, warum ich kein Informatik studiert habe... ;)

Vieles wußte ich trotzdem schon, das Thema ist mir also nicht neu. Aber um einen klassischen Parser, bzw. Lexial-Scanner möchte ich hier am Liebsten herumkommen.
Okay, so ein Automat kann dann straight und exakt den String durchlaufen, scheint aber für meine Zwecke doch zu viel Aufwand zu bedeuten, da ich den Code gerne minimal halten möchte. Ich weiß nicht so recht, es muß doch auch irgendwie einfacher gehen...

Trotzdem nochmal vielen lieben Dank für Deine Erläuterungen, das ist nicht selbstverständlich!

mit freundlichem Gruß
Danny