(54K)
The attribute grammar (AG) is a formal framework to express both syntax and semantics of programming languages . An attribute grammar description comprises a set of productions (BNF rules) and a set of attribution rules defined over the attributes associated with the grammar.
Attribute grammars are easy to describe and understand because they describe ``what the programming language semantics is like'' but not ``how their attribution rules are actually implemented.'' An AG-based compiler-compiler takes an attribute grammar description of a programming language and generates an efficient compiler for it. Attribute grammar has been successfully used to describe various programming languages and their processors.
On the other hand, debugging an attribute grammar is not simple. Debugging an attribute grammar description using a standard debugger exposes the attribute grammar implementation such as the attribute evaluator, which is usually a program generated from the attribute grammar description, and the runtime representation of attributes and parse trees.
We propose AG-aware debugging techniques for attribute grammars. By ``AG-aware'' we mean that the debugger is aware of attribute grammars and thus debugging does not necessarily require knowledge about strategy and implementation of attribute evaluation. We apply an algorithmic debugging technique to attribute grammar, which is further incorporated with slice-based debugging technique as well. By means of query-based interaction with the compiler developer, both techniques effectively narrow the potential bug space in the attribute grammar description and eventually identify the incorrect attribution rule.
The benefit of our approach, independence from the implementation of particular AG-based compiler-compiler, is twofold: (1) the compiler developer is freed from understanding implementation of the compiler-compiler and (2) the proposed technique can be applied to other AG-based system.
Our hybrid debugging technique has been implemented as a visual debugging environment called Aki. It is written in Squeak Smalltalk. The resulting system has been used in our project that incorporates AG technologies in most phases of compiler construction - including transformation of intermediate code, optimization, and code generation.
Ikezoe, Y., Sasaki, A., Ohshima, Y., Wakita, K. and Sassa, M.:
Systematic Debugging of Attribute Grammars,
In Ducasse, M. (ed.) Proc. AADEBUG 2000 - 4th International Workshop
on Automated Debugging, pp. 235-240, Munich
(Aug. 2000).