Unsere Aufgabe besteht darin einen Parsergenerator zu erstellen, der einen LL(1)-Parser generiert. Der Prozess ist dabei in zwei Teile aufgeteilt. Der erste Teil ist das dynamische Erstellen einer Parsetabelle aus der gegebenen Grammatik. Im zweiten Teil wird diese Parsetabelle verwendet um einen Tokenstream zu parsen.

Zum Erstellen der Parsertabelle werden folgende Schritte durchlaufen:

• Einlesen der Grammatik
• LL(1)-Umwandlung der Grammatik (wenn nötig)
• Aufstellen der Firstmengen
• Aufstellen der Followmengen
• Aufstellen der Parsetabelle

Die gegebene Grammatik sollte in BNF sein. Terminale werden dabei als "symbol" und Nichtterminale als <symbol>. Alle Produktionen zu einem Nichtterminal müssen in eine Zeile geschrieben werden. Die einzelnen Produktionen werden durch das Zeichen | getrennt. Der Pfad zur Grammatik wird dem Parser übergeben. Die Grammatik wird zeilenweise und innerhalb der Zeile zeichenweise eingelesen alles, was zwischen den Zeichen "" beziehungsweise < > steht wird als Symbol interprätiert. Beispielzeile: := "+" "-" "."

Damit eine Grammatik geparsed werden kann muss die angegebene Grammatik zunächst in eine LL(1)-parsebare Grammatik umgewandelt werden. Dazu werden Linksfaktorisierungen zusammengefasst, sowie direkte und indirekte Linksrekursionen entfernt, falls diesnötig ist um die Grammatik LL(1)-parsebar zu machen.

Der erste Schritt bei der LL(1)-Umwandlung ist die Linksfaktorisierung. Dabei werden gemeinsame Präfixe der unterschiedlichen Produktionen zusammengefasst, falls es gemeinsame Präfixe gibt.

Der nach dem Erstellen der Parsetabelle entstandene Parser ist ein tabellengesteuerter LL(1)-Parser.

1. in createGrammar, die Max. Anzahl der Iterationen (NItr) wird definiert um unendliche linkrekursion zu beschranken. wir definieren NItr=5. falls Anzahl der Iterationen > NItr, wird es ausgedrueckt und throw RuntimeException dann wird programm stoppt.

2. Nach Aufstellung der Parsetabelle, wird die eingelesen Grammatik ueberprueft.falls Anzahl der ParseTableEntry >1 ist, dann diese grammar ist fuer LL(1) nicht parsebar, and TokenParser wird aufhoeren.

3. ReadFile wir checken zuerst das Format der eingelesen file, ob es BNF ist. wenn jeder Zeile kein "::=" vorkommt, diese Production aus diese Zeilen ist falsch Format, throw RuntimeException,und Diese invalid Grammar in welchem Zeilen werden als Tip gegeben.

4. Productionen aus jeder Zeile werden in 2 Teil getrennt, auf Linker Seite muss es ein NonTerminal sein, und auf rechte seite muss es aus nonterminals , terminals , und "|" entstehen. wir benutzen Regulaeren Ausdruck um die Formaten zu checkeen. die lineNo von der invaild Grammar werden auch gegeben, wenn check scheitert.

5. auf rechter Seite der productionen haben wir auch Regulaeren Ausdruck benutzt. Als Nontermials, z.b.<A> diese ganze Gruppe wird addiert ins ProductionVector. Als Terminals z.b."String", die beide " " werden ins ProductionVector nicht hinzugefuegt, deshalb haben wir substring von Position 1 bist Position (size-1) genommen. <\w+> : Nonterminal Formate definieren. "\S+" : Terminal Formate ist "String", aber "" ist nicht erlaubt. d.h kein Leerzeichen zwischen " und " erlaubt. nur wenn die Productionen passen diese Formate an, erst werden sie akzeptiert.

6. In Tokenparser, parseTokenSTream, wenn wir kein "EOF" sehen, throw RuntimeException (es gibt zu viel Symbols).

7. parserToken, wenn es keine passende Productionen gefunden werden koennte, throw RuntimeException (Token passt die gegeben Grammar nicht an).

• Patrick Schlott (Ansprechpartner)
• Christoph Schröder
• Ying Wei
• Fateh Kishi