Extending bison with attribute grammars

Abstract

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.

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.