Parserbau

[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.