Circular Reference Attributed Grammars - their Evaluation and Applications
Magnusson, Eva LU and Hedin, Görel LU
(2003)
LDTA03 The third Workshop om Language Descriptions, Tools and Applications
82(3).
p.532-554
- Abstract
- 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... (More)
- 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 Java 1.2. We also revisit some of the classical examples of CAGs and show how their solutions are facilitated by CRAGs. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/634023
- author
- Magnusson, Eva
LU
and Hedin, Görel
LU
- organization
- publishing date
- 2003
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- fixed-point computations, Circular grammars, Attribute Grammars
- host publication
- ENTCS - Electronic Notes in Computer Science
- volume
- 82
- issue
- 3
- pages
- 20 pages
- publisher
- Elsevier
- conference name
- LDTA03 The third Workshop om Language Descriptions, Tools and Applications
- conference dates
- 2003-04-06
- external identifiers
-
- scopus:19044399100
- ISSN
- 1571-0661
- DOI
- 10.1016/S1571-0661(05)82627-1
- language
- English
- LU publication?
- yes
- id
- 4cbd718a-721b-4f44-ac1b-ab5585be2c94 (old id 634023)
- date added to LUP
- 2016-04-01 17:00:20
- date last changed
- 2022-02-05 20:03:28
@inproceedings{4cbd718a-721b-4f44-ac1b-ab5585be2c94,
abstract = {{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 Java 1.2. We also revisit some of the classical examples of CAGs and show how their solutions are facilitated by CRAGs.}},
author = {{Magnusson, Eva and Hedin, Görel}},
booktitle = {{ENTCS - Electronic Notes in Computer Science}},
issn = {{1571-0661}},
keywords = {{fixed-point computations; Circular grammars; Attribute Grammars}},
language = {{eng}},
number = {{3}},
pages = {{532--554}},
publisher = {{Elsevier}},
title = {{Circular Reference Attributed Grammars - their Evaluation and Applications}},
url = {{https://lup.lub.lu.se/search/files/4844086/634036.pdf}},
doi = {{10.1016/S1571-0661(05)82627-1}},
volume = {{82}},
year = {{2003}},
}