Titelaufnahme

Titel
Extending bison with attribute grammars / von Mihai Calin Ghete
Weitere Titel
Eine Erweiterung von Bison um Attributierte Grammatiken
Verfasser / Verfasserin Ghete, Mihai Calin
Begutachter / BegutachterinErtl, Anton
ErschienenWien, 2018
Umfangviii, 105 Seiten : Diagramme
HochschulschriftTechnische Universität Wien, Diplomarbeit, 2018
Anmerkung
Zusammenfassung in deutscher Sprache
Anmerkung
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (DE)Attributierte Grammatiken
Schlagwörter (EN)Attribute Grammars
URNurn:nbn:at:at-ubtuw:1-111606 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Extending bison with attribute grammars [1.09 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Attributierte Grammatiken wurden von Knuth eingeführt und stellen ein Formalismus dar, um die Semantik von kontextfreien Sprachen zu spezifizieren. Ein wesentlicher Bestandteil dessen ist die Attribut-Evaluation, die auf einer topologischen Sortierung eines gerichteten, zyklenfreien Graphens beruht. Diverse Ansätze wurden historisch entwickelt, um den resultierenden Rechenaufwand an die übersetzungszeit des Evaluators zu verlagern oder diesen durch einer Abschwächung des Formalismus zu reduzieren. Diese Arbeit beschreibt den konzeptuellen Hintergrund und die Implementierung eines vollständigen dynamischen (Laufzeit-) Attributevaluators innerhalb eines LALR(1) und GLR-Parsers und vergleicht dazu den dynamischen Ansatz mit solchen Ansätzen, die zur Übersetzungszeit stattfinden. Die dem dynamischen Evaluator zugrundeliegenden Algorithmen haben lineare Laufzeit und linearen Speicherbedarf in der Größe des Syntax-Baumes. Vergleichstests zeigen, dass dieser für praktische Zwecke performant genug ist. Der Evaluator unterstützt die Attributierung von GLR-Grammatiken, welche als Ergebnis einen einzigen gültigen Syntax-Baum haben. Der Kern des Evaluators steht außerdem auch als Laufzeit-Bibliothek zur Verfügung.

Zusammenfassung (Englisch)

Knuth's attribute grammars are a formalism for specifying the semantics of context-free languages. They imply an attribute evaluation step that requires finding a topological sorting of a directed acyclic graph. Historically, various approaches have been used to shift the resulting workload to the compile-time of evaluators or to reduce it by lowering the expressiveness of the formalism. This thesis describes the conceptual background and implementation of a fully expressive dynamic (run-time) attribute evaluator within an LALR(1) and GLR parser, and analyzes the trade-offs involved in both dynamic and various compile-time evaluation approaches. The resulting evaluator uses algorithms that are linear in time and space with regard to the size of the parse tree. Benchmarking suggests it is performant enough for practical purposes. The evaluator supports GLR attribute grammars that result in a single valid parse tree. In addition, the core of the evaluator is made available as a separate run-time library.

Statistik
Das PDF-Dokument wurde 13 mal heruntergeladen.