TY - CONF
T1 - Linearly Ordered Attribute Grammars
T2 - PEPM 2015
AU - van Binsbergen, L. Thomas
PY - 2015/1/13
Y1 - 2015/1/13
N2 - 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.
AB - 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.
U2 - 10.1145/2678015.2682543
DO - 10.1145/2678015.2682543
M3 - Paper
SP - 49
EP - 60
Y2 - 13 January 2015 through 14 January 2015
ER -