Activities per year
Abstract
Attribute Grammars (AGs) extend Context-Free Grammars with attributes: information gathered on the syntax tree that adds semantics to the syntax. AGs are very well suited for describing static analyses, code-generation and other phases incorporated in a compiler.
AGs are divided into classes based on the nature of the dependencies between the attributes. In this paper we examine the class of Linearly Ordered Attribute Grammars (LOAGs), for which strict, bounded size evaluators can be generated. Deciding whether an Attribute Grammar is linearly ordered is an NP-hard problem. The Ordered Attribute Grammars form a subclass of LOAG for which membership is tested in polynomial time by Kastens' algorithm (1980). On top of this algorithm we apply an augmenting dependency selection algorithm, allowing it to determine membership for the class LOAG. Although the worst case complexity of our algorithm is exponential, the algorithm turns out to be efficient for practical full-sized AGs. As a result, we can compile the main AG of the Utrecht Haskell Compiler without the manual addition of augmenting dependencies.
The reader is provided with insight in the difficulty of deciding whether an AG is linearly ordered, what optimistic choice is made by Kastens' algorithm and how augmenting dependencies can resolve these difficulties.
AGs are divided into classes based on the nature of the dependencies between the attributes. In this paper we examine the class of Linearly Ordered Attribute Grammars (LOAGs), for which strict, bounded size evaluators can be generated. Deciding whether an Attribute Grammar is linearly ordered is an NP-hard problem. The Ordered Attribute Grammars form a subclass of LOAG for which membership is tested in polynomial time by Kastens' algorithm (1980). On top of this algorithm we apply an augmenting dependency selection algorithm, allowing it to determine membership for the class LOAG. Although the worst case complexity of our algorithm is exponential, the algorithm turns out to be efficient for practical full-sized AGs. As a result, we can compile the main AG of the Utrecht Haskell Compiler without the manual addition of augmenting dependencies.
The reader is provided with insight in the difficulty of deciding whether an AG is linearly ordered, what optimistic choice is made by Kastens' algorithm and how augmenting dependencies can resolve these difficulties.
Original language | English |
---|---|
Pages | 49-60 |
Number of pages | 12 |
DOIs | |
Publication status | Published - 13 Jan 2015 |
Event | PEPM 2015 - Mumbai, India Duration: 13 Jan 2015 → 14 Jan 2015 |
Conference
Conference | PEPM 2015 |
---|---|
Country/Territory | India |
City | Mumbai |
Period | 13/01/15 → 14/01/15 |
Activities
- 1 Participation in conference
-
Linearly Ordered Attribute Grammars - with Automatic Augmenting Dependency Selection - PEPM 2015
L. Thomas van Binsbergen (Speaker)
Jan 2015Activity: Participating in or organising an event › Participation in conference
File