Concurrent Circular Reference Attribute Grammars (Extended Version)

Research output: Book/ReportReport


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.


Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science


  • Reference Attribute Grammar, Concurrency, Parallelization, Memoization, Circular Attributes
Original languageEnglish
PublisherDepartment of Computer Science, Lund University
Number of pages20
Publication statusPublished - 2017 Oct 18
Publication categoryResearch

Publication series

NameTechnical report, LU-CS-TR
PublisherLund University
No.Report 103
ISSN (Print)1404-1200

Total downloads

No data available

Related research output

Jesper Öqvist, 2018 Dec 19, Lund: Department of Computer Science, Lund University. 197 p.

Research output: ThesisDoctoral Thesis (compilation)

View all (1)

Related projects

Jesper Öqvist, Görel Hedin, Boris Magnusson & Emma Söderberg

Swedish Research Council


Project: DissertationIndividual research project

View all (2)