Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Circular Reference Attributed Grammars - their Evaluation and Applications

Magnusson, Eva LU and Hedin, Görel LU orcid (2007) In Science of Computer Programming 68(1). p.21-37
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 that of 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:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
fixed-point computations, Attribute grammars, Circular grammars
in
Science of Computer Programming
volume
68
issue
1
pages
21 - 37
publisher
Elsevier
external identifiers
  • wos:000249185700003
  • scopus:34547468967
ISSN
0167-6423
DOI
10.1016/j.scico.2005.06.005
language
English
LU publication?
yes
id
a42d66bd-599e-4d45-b783-a5de8b652497 (old id 633959)
date added to LUP
2016-04-01 15:26:22
date last changed
2022-02-12 07:55:02
@article{a42d66bd-599e-4d45-b783-a5de8b652497,
  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<br/><br>
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.}},
  author       = {{Magnusson, Eva and Hedin, Görel}},
  issn         = {{0167-6423}},
  keywords     = {{fixed-point computations; Attribute grammars; Circular grammars}},
  language     = {{eng}},
  number       = {{1}},
  pages        = {{21--37}},
  publisher    = {{Elsevier}},
  series       = {{Science of Computer Programming}},
  title        = {{Circular Reference Attributed Grammars - their Evaluation and Applications}},
  url          = {{https://lup.lub.lu.se/search/files/4392975/633996.pdf}},
  doi          = {{10.1016/j.scico.2005.06.005}},
  volume       = {{68}},
  year         = {{2007}},
}