Institut für Computersprachen
Programmiersprachen und Übersetzer
 | Diplomarbeit |
|---|---|
| Titel | Ein fehlerkorrigierender LALR(1)-Parsergenerator |
| Autor | Tschenett, Helmuth |
| Erscheinungsjahr | 1990 |
| Abstract | In dieser Diplomarbeit werden alle Algorithmen, die zur Implementierung eines fehlerkorrigierenden LALR(1)-Parsergenerators notwendig sind, ausführlich beschrieben. Für die wichtigste und zugleich komplizierteste Aufgabe eines LALR(1)-Parsergenerators - die Bestimmung der für die Analyse notwendigen Lookaheadmengen - wird einer der schnellsten zur Zeit bekannten Algorithmen vorgestellt. Durch Verwendung einiger Eigenschaften der LALR-Syntaxanalyse sowie Algorithmen zur effizienten Speicherung dünnbesetzter Matrizen, gelingt es, den Speicherplatzbedarf der Analysetabellen auf ca. 5% der ursprünglichen Größe zu verringern, ohne daß dabei die optimale Zugriffszeit verloren geht. Ein sehr wichtiger aber oft vernachlässigter Teil eines Parsergenerators ist die Implementierung der Fehlerbehebung. Hierfür wurde eine neue Methode erarbeitet, die in den meisten Fällen eine optimale Fehlerkorrektur erlaubt. Eine Anpassung an bestimmte Fehlerhäufigkeiten ist dabei möglich. Im ersten Teil der Diplomarbeit wird der Begriff Syntaxanalyse genauer betrachtet und untersucht, was man im Bereich des Übersetzerbaus darunter versteht. Weiters wird der Zusammenhang zwischen LL(k)- und LR(k)-Analyse in Bezug auf Grammatiken und Sprachen beschrieben. |
| Status | Verfügbar |