11.1.2 Syntaktische Analyse (Parser)

Die syntaktische Analyse faßt mehrere Terminalsymbole zu grammatikalischen Phrasen zusammen [155][8][3]. Die grammatikalischen Phrasen werden durch die (Ableitungs-) Regeln der Grammatik definiert. Anschaulich können die grammatikalischen Phrasen durch einen Ableitungsbaum dargestellt werden. Die Blätter dieses Baumes sind die Terminalsymbole. Wenn man die Blätter dieses Baumes von links nach rechts liest, so erhält man die Eingabe.

Bei der syntaktischen Analyse unterscheidet man zwei Hauptmethoden [3]:

LL(n):

Bei einer LL(n)-Grammatik wird die syntaktische Analyse von links nach rechts durchgeführt, wobei Linksableitungen verwendet werden. Dies ist ein Top-Down Verfahren.

LR(n):

Bei einer LR(n)-Grammatik wird die syntaktische Analyse von links nach rechts durchgeführt, wobei Rechtsableitungen verwendet werden. Dies ist eine Bottom-Up Methode.

• Mit LR-Parsern können praktisch alle Konstruktionen in Programmiersprachen analysiert werden, sofern sie kontext-frei sind.
• Die LR-Methode ist die universellste non-backtracking Parser-Methode, die bekannt ist. Eine effiziente Implementierung ist möglich.
• Die Grammatiken, die mit LR-Parsern analysiert werden können, sind ein Superset der Grammatiken, die mit prediktiven Parsern (LL(n)) analysiert werden können.
• Ein LR-Parser kann Syntaxfehler in der Eingabe so früh wie möglich erkennen.

Zur Erstellung der Parser-Tabellen wurde das an der Unversität von Wisconsin entwickelte Programm ECP (Error Correcting Parser) [105] verwendet. Dieses Programm erstellt nicht nur die Parser-Tabellen, sondern erzeugt auch Tabellen für eine Error-Corrector (siehe nächster Abschnitt).

Die Definition der Sprache JANAP für ECP ist im Anhang B.2 enthalten. Der Parser erwartet als Eingabe die Terminal-Symbole, die der Scanner erkannt hat. Danach wird der Syntax-Baum aufgebaut. Sobald ein Teilbaum fertig ist, kann eine Semantik-Routine aufgerufen werden (siehe 11.2), die die notwendige Verarbeitung zur Erstellung der Netzwerkgleichungen durchführt.

Bei der syntaktischen Analyse mußten folgende Spezialitäten von JANAP eigens berücksichtigt werden:

• Die Anweisungen zur Definition der Topologie des Netzwerkes (Bauelementanweisungen) sind nicht durch ein eigenes Anweisungsschlüsselwort gekennzeichnet. Statt dessen gibt das erste Zeichen des Bauelementnamens den Typ des Bauelements und damit die konkrete Syntax der Anweisung an. Dadurch mußte im Scanner die Definition des Namens auf verschiedene Terminalsymbole aufgeteilt werden. Die Aufgabe der Syntaxanalyse ist nun die Zusammenfassung dieser verschiedenen Namen zu einem einzigen Symbol - sofern es sich nicht um den Beginn einer Bauelementanweisung handelt.
• In JANAP können Knotennamen mit einer Ziffer beginnen. Dadurch ist der Scanner nicht mehr in der Lage die Unterscheidung zwischen Zahlen und Knotennamen zu treffen. Diese Entscheidung muß daher der Parser anhand des Kontext treffen. Eine weitere Komplikation ist, daß die Knoten in einer Bauelementanweisung durch ein - getrennt werden. Dies führt nun auch zur Kollision mit dem Vorzeichen einer Zahl. Dadurch werden die Grammatik-Regeln für Ausdrücke relativ kompliziert.
• Nach der letzten Bauelementanweisung muß das Gesamtnetzwerk aufgebaut werden, da sich in den folgenden Anweisungen alle Referenzen auf das Gesamtnetzwerk beziehen - im Gegensatz zum Topologieteil, wo sich Referenzen auf die jeweilige Teilschaltung beziehen. Zu diesem Zweck wurde eine Epsilon-Produktion eingeführt, die als Semantik-Aktion das Gesamtnetzwerk aufbaut.
• Zeilen der Eingabe, die bereits gelesen worden sind, können solange nicht ausgegeben werden, bis sichergestellt ist, daß diese Zeilen syntaktisch richtig sind. Wenn das nicht der Fall wäre, würde der Error-Corrector Terminalsymbole einfügen oder löschen (und dies entsprechend kennzeichnen). Dies bedeutet, daß die Eingabezeilen zwischengespeichert werden müssen. Dadurch ergibt sich auch eine Einschränkung der Anzahl der Kommentarzeilen.
• Beim Aufruf von Funktionen und der Verwendung von Tabellen kann in der Syntax noch nicht festgelegt werden, wieviele Parameter die Funktion bzw. Tabelle hat und welchen Typ (Zahl, Knotenname oder Zweigname) die Parameter haben. Dies ist eine kontextabhängige Entscheidung, die nach einer Suche der Definition der Funktion bzw. Tabelle in der entsprechenden Symboltabelle erfordert. Um diese Situation doch vom Parser und insbesondere vom Error-Corrector behandeln zu lassen, wurde folgender Trick implementiert.

  Sobald der Funktions- oder Tabellenname erkannt wurde (der Parser in der gewählten LALR(1) Grammatik erkennt, daß es sich um eine Funktion oder Tabelle nach dem Lesen der öffnenden Klammer der Parameterliste - also noch vor dem Lesen der Parameterliste - handeln muß) wird die Definition der Funktion bzw. Tabelle gesucht. Anhand der Definition wird festgestellt welchen Typ die Parameter haben müssen. Je nach Art der vorgeschriebenen Parameterliste wird nun ein zusätzliches Terminalsymbol ($E, $R oder $V) nach der öffnenden Klammer eingefügt, sodaß der Parser die richtige Form der Parameterliste (die richtige Grammatikregel) auswählen kann. Diese Einfügung scheint natürlich nicht im Protokoll der Eingabe auf.