Berechnung von First- und Followmengen in erweiterten kontextfreien Grammatiken und Generierung eines ELL(1)-Parsers

Reinhold Heckmann


English version of this page


Erweiterte Grammatiken, das sind solche, bei denen die rechten Seiten der Produktionen aus regulären Ausdrücken bestehen, ermöglichen elegantere und kürzere Syntaxdefinitionen mit weniger direkten Rekursionen als herkömmliche Grammatiken. In diesem Vortrag werden zunächst die erweiterten Grammatiken eingeführt, mit Hilfe der üblichen regulären Linksableitung First1-Mengen definiert und ihre Haupteigenschaften festgestellt. Dann wird sich zeigen, daß es bei der Definition der Follow1-Mengen Schwierigkeiten gibt, die durch eine neue Art von Ableitung gelöst werden können. Anschließend wird ein Algorithmus zur Berechnung der First- und Followmengen vorgestellt, dessen Laufzeit linear ist in der Größe der Grammatik und der Zeit, die für die Vereinigung zweier Mengen von Terminalzeichen benötigt wird. Mit Hilfe dieser Mengen kann man dann überprüfen, ob die Grammatik die ELL(1)-Eigenschaft besitzt, und wenn ja, einen ELL(1)-Parser in Tabellenform dafür generieren.

Reinhold Heckmann / heckmann@absint.com