LR-Syntaxanalyse mit expliziter Konfliktmarkierung

Für die Spezifikation von Programmiersprachen verwendete Grammatiken erfüllen häufig nicht die LR(k)-Eigenschaft. In dieser Arbeit wird daher eine Erweiterung des LR(k)-Verfahrens vorgeschlagen, die dieses Problem durch die Markierung von konfliktbehafteten Teilen der Eingabe und spätere Reduktion an diesen Stellen in vielen Fällen lösen kann. Die Zeit- und Platzkomplexität des LR(k)-Parsers wird dabei beibehalten und die Parametrisierung des Parsers erfolgt ähnlich zu LR(k) mit Tabellen. Neben der Untersuchung von theoretischen Eigenschaften des definierten Parsers liegt der Schwerpunkt auf der algorithmischen Erzeugung der benötigten Tabellen. Abschließend werden die implementierten Algorithmen experimentell untersucht