triceratops

Evaluating Inherited Attributes Using Haskell and Lazy Evaluation

TriCollege Digital Repository

Title: Evaluating Inherited Attributes Using Haskell and Lazy Evaluation
Author: Moss, William B.
Advisor: Wonnacott, David G.
Department: Haverford College. Dept. of Computer Science
Type: Thesis (B.S.)
Running Time: 183012 bytes
Issue Date: 2005
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.
Subject: Parsing (Computer grammar)
Subject: Programming languages (Electronic computers)
Terms of Use: http://creativecommons.org/licenses/by-nc/3.0/us/
Permanent URL: http://hdl.handle.net/10066/1486

Files in this item

Files Description Size Format
2005MossW.pdf Thesis (Haverford users only) 178.7Kb PDF
Haverford_departmental_permission.pdf **Archive Staff Only** 30.60Kb PDF

Citation

Moss, William B.. "Evaluating Inherited Attributes Using Haskell and Lazy Evaluation". 2005. Available electronically from http://hdl.handle.net/10066/1486.

This item appears in the following Collection(s)

http://creativecommons.org/licenses/by-nc/3.0/us/ Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc/3.0/us/

Search


Advanced Search

Browse

My Account