Evaluating Inherited Attributes Using Haskell and Lazy Evaluation

Date
2005
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Haverford users only
Tripod URL
Identifier
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.
Description
Citation
Collections