Logo der Freien Universität BerlinFreie Universität Berlin

Fachbereich Mathematik und Informatik


Service-Navigation

  • Startseite
DE
  • DE: Deutsch
  • EN: English
Hinweise zur Datenübertragung bei der Google™ Suche
Fachbereich Mathematik und Informatik/Informatik/

Theoretische Informatik

Menü
  • Mitglieder

    loading...

  • Projekte

    loading...

  • Gäste

    loading...

  • Abschlussarbeiten

    loading...

  • Fotoalbum

    loading...

  • Veranstaltungen

    loading...

  • Software

    loading...

  • Stipendienprogramme

    loading...

  • Archiv

    loading...

Mikronavigation

  • Startseite
  • Informatik
  • Arbeitsgruppen
  • Theoretische Informatik
  • Abschlussarbeiten
  • Abgeschlossene Bachelorarbeiten
  • Erstellung eines GLL-Parsergenerators für kontextfreie Grammatiken

Miro Baeten:

Erstellung eines GLL-Parsergenerators für kontextfreie Grammatiken

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.

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

Service-Navigation

  • Startseite

Diese Seite

  • Drucken
  • RSS-Feed abonnieren
  • English