Laufzeitanalyse und Optimierung von Parsern für LR-reguläre Grammatiken

Gegenstand der vorliegenden Arbeit ist die Laufzeitanalyse und Optimierung von Parsern für LR-reguläre Grammatiken. Die Arbeit gliedert sich in zwei Teile. Im ersten Teil werden LR-basierte Parseverfahren mit regulärem Lookahead untersucht. Mit Hilfe sog. Partitionierungstabellen können Parser konstruiert werden, deren Laufzeit stets linear in der Länge der zu verarbeitenden Eingabe ist. Unabhängig davon wird für das LAR(m)-Parseverfahren ein innovatives, hinreichendes Kriterium entwickelt, das die lineare Laufzeit des resultierenden Parsers anhand der gegebenen Grammatik testet. Im zweiten Teil wird der Leo-Parser, eine Erweiterung des bekannten Earley-Parsers, für den Spezialfall LR-regulärer Grammatiken untersucht. Es wird eine kompakte Variante des Leo-Algorithmus erarbeitet, die eine beschränkte Laufzeit für jedes Eingabezeichen und damit eine asymptotisch optimale Laufzeit garantiert; die Laufzeiteigenschaften werden detailliert bewiesen