Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Concurrent Circular Reference Attribute Grammars (Extended Version)

Öqvist, Jesper LU and Hedin, Görel LU orcid (2017) In Technical report, LU-CS-TR
Abstract
Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools. Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently.

We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools. Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes.

We have implemented our algorithms in Java, for the JastAdd metacompiler. We evaluate the implementation on a JastAdd-specified compiler for the Java... (More)
Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools. Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently.

We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools. Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes.

We have implemented our algorithms in Java, for the JastAdd metacompiler. We evaluate the implementation on a JastAdd-specified compiler for the Java language, demonstrating very low latencies for interactive attribute queries, on the order of milliseconds. Furthermore, initial experiments show a speedup of about a factor 2 when using four parallel compilation threads. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Book/Report
publication status
published
subject
keywords
Reference Attribute Grammar, Concurrency, Parallelization, Memoization, Circular Attributes
in
Technical report, LU-CS-TR
issue
Report 103
pages
20 pages
publisher
Department of Computer Science, Lund University
report number
2017-254
ISSN
1404-1200
project
Contributions to Declarative Implementation of Static Program Analysis
ELLIIT LU P05: Scalable Language Tools for Cyber-Physical Systems
language
English
LU publication?
yes
id
4809a5fc-f7e3-4082-bf41-314091c98e0d
date added to LUP
2017-10-19 11:50:17
date last changed
2021-05-06 08:22:46
@techreport{4809a5fc-f7e3-4082-bf41-314091c98e0d,
  abstract     = {{Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools.  Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently.<br/><br/>We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools.  Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes.<br/><br/>We have implemented our algorithms in Java, for the JastAdd metacompiler.  We evaluate the implementation on a JastAdd-specified compiler for the Java language, demonstrating very low latencies for interactive attribute queries, on the order of milliseconds. Furthermore, initial experiments show a speedup of about a factor 2 when using four parallel compilation threads.}},
  author       = {{Öqvist, Jesper and Hedin, Görel}},
  institution  = {{Department of Computer Science, Lund University}},
  issn         = {{1404-1200}},
  keywords     = {{Reference Attribute Grammar; Concurrency; Parallelization; Memoization; Circular Attributes}},
  language     = {{eng}},
  month        = {{10}},
  number       = {{2017-254}},
  series       = {{Technical report, LU-CS-TR}},
  title        = {{Concurrent Circular Reference Attribute Grammars (Extended Version)}},
  url          = {{https://lup.lub.lu.se/search/files/33513876/report.pdf}},
  year         = {{2017}},
}