Circular Reference Attributed Grammars - their Evaluation and Applications
Author
Summary, in English
This paper presents a combination of Reference Attributed Grammars (RAGs) and Circular Attribute Grammars (CAGs). While RAGs allow the direct and easy specification of non-locally dependent information, CAGs allow iterative fixed-point computations to be expressed directly using recursive (circular) equations. We demonstrate how the combined formalism, Circular Reference Attributed Grammars (CRAGs), can take advantage of both these strengths, making it possible to express solutions to many problems in an easy way. We exemplify with the specification and computation of the nullable, first, and follow sets used in parser construction, a problem which is highly recursive and normally programmed by hand using an iterative algorithm. We also present a general demand-driven evaluation algorithm
for CRAGs and some optimizations of it. The approach has been implemented and experimental results include computations on a series of grammars including that of Java 1.2. We also revisit some of the classical examples of CAGs and show how their solutions are facilitated by CRAGs.
for CRAGs and some optimizations of it. The approach has been implemented and experimental results include computations on a series of grammars including that of Java 1.2. We also revisit some of the classical examples of CAGs and show how their solutions are facilitated by CRAGs.
Publishing year
2007
Language
English
Pages
21-37
Publication/Series
Science of Computer Programming
Volume
68
Issue
1
Full text
- Available as PDF - 257 kB
- Download statistics
Document type
Journal article
Publisher
Elsevier
Topic
- Computer Science
Keywords
- fixed-point computations
- Attribute grammars
- Circular grammars
Status
Published
Research group
- LUCAS
ISBN/ISSN/Other
- ISSN: 0167-6423