The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

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 Java 1.2. We also revisit some of the classical examples of CAGs and show how their solutions are facilitated by CRAGs.

Publishing year

2003

Language

English

Pages

532-554

Publication/Series

ENTCS - Electronic Notes in Computer Science

Volume

82

Issue

3

Document type

Conference paper

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • fixed-point computations
  • Circular grammars
  • Attribute Grammars

Conference name

LDTA03 The third Workshop om Language Descriptions, Tools and Applications

Conference date

2003-04-06

Status

Published

Research group

  • LUCAS

ISBN/ISSN/Other

  • ISSN: 1571-0661