Fachrat Informatik - Forum

Guten Abend zu so später Stunde, liebe Mit-Compilerbauer.
Vielleicht interessiert euch das ja auch.

Weil ich gerade dabei war, den Parser für unsere (would-be-) LL(1)-Grammatik zu schreiben, und dafür gerne die beiden einschlägig bekannten LL(1)-Bedingungen überprüfen wollte, hätte ich die First- und Followmengen aller nonterminaler Symbole bestimmen müssen. Aus meiner Erinnerung an PSUE weiß ich noch, dass dies selbst bei relativ winzigen Grammatiken recht aufwändig und für Leute ohne den berühmten "scharfen Blick" ein fehleranfälliges und langwieriges Unterfangen werden kann. Dies war dann auch der Grund dafür, dass ich mich zunächst daran gemacht habe, unsere Produktionen von einem Miniparser zur weiteren Analyse in einen Transitionsgraphen umwandeln zu lassen. Jedoch habe ich dann bald schon, nach 14 Stunden (programmieren | lesen)*, feststellen müssen, das dauert wohl noch länger - zu lang. Also habe ich ein Tool für diese Aufgabe gesucht und HIER gefunden - siehe da, entwickelt von einem ehemaligen Studenten dieser Universität. Falls jener Mensch dies jemals lesen sollte, möchte ich mich an dieser Stelle herzlich bei ihm für dieses grandiose Programm bedanken!

Es handelt sich um einen 2004 während einer Studienarbeit beim IfIs entwickelten LL(1)-Parsergenerator "parll2", jedoch kann er auch die von mir so sehnlich herbeigewünschten First und Follows bestimmen (mit deren Kenntnis die Parsingfunktionen des Recursive Descent Parsers problemlos erstellt werden können) und ist zugleich in der Lage, die LL-Eigenschaft der Grammatik zu überprüfen. Den Parser selbst möchte ich natürlich zu Lernzwecken selbst schreiben, deshalb nimmt man ja auch an der Veranstaltung überhaupt teil. Jedoch, auf die eklige Bestimmung dieser Mengen möchte ich nach Möglichkeit liebend gerne verzichten, zumal dies ja auch eine in einer großzügiger bemessenen Zeit automatisierbare Aufgabe wäre. Deshalb sehe ich den Verweis auf dieses Tool hier auch nicht als "Schummeln" an, im Gegenteil, ich möchte euch anderen Gruppen nichts für sie eventuell ebenfalls so wichtiges vorenthalten.

Falls die möglicherweise mitlesenden Mitarbeiter des Fachgebiets für Programmiersprachen und Übersetzer dies jedoch anders sehen sollten, möchte ich mich hierfür entschuldigen (und in dem Fall wurde natürlich alles handberechnet ) - ich hätte eventuell um Erlaubnis für dieses Thema gefragt, aber jetzt ist Wochenende, und bis Mittwoch sollte der Parser ja bereits so weit fertig sein.

Nachtrag: Das Ding ist so super, dass ich mich frage, wie man es bei so vielen Produktionen ohne schaffen kann. Ich musste mindestens noch sechs davon provisiorisch verändern, damit die Sprache LL(1) parsbar ist...die Änderungen werd ich wohl mit meiner Gruppe besprechen müssen: If <something> ELSE <something> ENDIF mag keiner.
Jemand machte den Vorschlag, dann eben eine LL(k) - Grammatik daraus zu machen, aber das lässt das Interface IScanner nicht zu, und zwar aus dem Grund, dass man nach dem Abholen des nächsten Token nicht mehr zu den vorherigen zurückspringen kann, habe ich recht? Man müsste dann schon im Parser die nächsten k Token puffern, und in den Parsingmethoden irgendwie damit rumhantieren...aber so richtig schönes Recursive Descent ist das dann nicht mehr...?