Evaluating Inherited Attributes Using Haskell and Lazy Evaluation

Abstract

Parser generators designed for imperative programming languages (C++, Java, etc), such as YACC and CUPS, inevitably run into difficulty handling inherited attributes. In the past, this difficulty has been handled in one of two ways: 1) the problem is ignored, and inherited attributes must be manually calculated later using extra passes over the parse tree; and 2) for the L-attributed class of grammars, the parser generator provides some sort of ”hack,” allowing the user to access previous elements of the stack with no safeguards preventing a user from accessing incorrect data. Many functional programming languages, however, provide an easy solution to this problem. Using lazy evaluation, a parser generator written for a function programming language can sidestep the entire problem, relying on the language system to evaluate attributes (regardless of whether they are inherited or synthesized) as it needs them. This paper discusses a method for evaluating inherited and synthesized attributes in Haskell, specifically using Happy, a parser generator for Haskell. This paper will present specific examples of parsing inherited attributes in both functional and imperative languages, followed by the presentation of an algorithm for computing any inherited attribute in Happy.