Syntactic Specification and Analysis with Attributed Grammars

Abstract

Attributed grammars have traditionally been used for the semantic specification of programming languages and for the implementation of the translation phase of compilers. We investigate attributed grammars as an efficiently parsable syntactic specification mechanism that can handle many of the non-context-free aspects of programming language syntax. A formal definition of attributed grammars is provided, and the notion of an attributed derivation is examined. We identify a parsable class of attributed grammars, called strong ALL(k), and the corresponding parser is developed as an extension of the strong LL(k) technique. Algorithms are presented for testing the strong ALL(k) property and for generating the strong ALL(k) parser. Finally, a number of applications are considered, establishing ALL(k) grammars as an effective tool for handling context-sensitivity in programming languages, and for reducing the size of programming language grammars.