Miro Baeten

Erstellung eines GLL-Parsergenerators für kontextfreie Grammatiken

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 14.02.2017

Kurzbeschreibung

Die Arbeit beschäftigt sich mit der Erstellung eines Parsergenerators für allgemeine kontextfreie Grammatiken unter Verwendung des GLL-Algorithmus, welcher mit ambigen Grammatiken in O(n^3) umzugehen weiß. Sein Einsatz bietet sich unter anderem in der Computerlinguistik, dem Software Reengineering und in Compilern an. Die Laufzeit wird durch die Verwendung von als Graphen strukturierten Stacks (GSS) sowie einem Shared Packed Parse Forest (SPPF) erreicht, der mehrerer valide Ableitungen zusammenfasst. Zunächst wird auf den Algorithmus, danach auf den Generator und die Parser eingegangen. Der Generator abstrahiert die Grammatiken in einem Modell, analysiert dieses und erzeugt daraus einen Parser, der sich an die asymptotische Laufzeit des Algorithmus hält. Damit die Parser ambige Grammatiken schneller ableiten können, wird der Algorithmus um eine Parallelisierung erweitert. Abschließend wird beleuchtet, wie der Parsergenerator in Zukunft ausgebaut werden kann. Bedeutend ist sowohl der weitere Umgang mit den SPPFs als auch die Verbesserung des GSS.