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