Linearly Ordered Attribute Grammars : with Automatic Augmenting Dependency Selection. / van Binsbergen, L. Thomas.

2015. 49-60 Paper presented at PEPM 2015, Mumbai, India.

Research output: Contribution to conferencePaperpeer-review

Published

Standard

Linearly Ordered Attribute Grammars : with Automatic Augmenting Dependency Selection. / van Binsbergen, L. Thomas.

2015. 49-60 Paper presented at PEPM 2015, Mumbai, India.

Research output: Contribution to conferencePaperpeer-review

Harvard

APA

Vancouver

Author

BibTeX

@conference{d2e698bf438542b5957ee9ec45856893,
title = "Linearly Ordered Attribute Grammars: with Automatic Augmenting Dependency Selection",
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.",
author = "{van Binsbergen}, {L. Thomas}",
year = "2015",
month = jan,
day = "13",
doi = "10.1145/2678015.2682543",
language = "English",
pages = "49--60 ",
note = "PEPM 2015 ; Conference date: 13-01-2015 Through 14-01-2015",

}

RIS

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 -