Concurrent Circular Reference Attribute Grammars (Extended Version)

Research output: Book/ReportReport

Standard

Concurrent Circular Reference Attribute Grammars (Extended Version). / Öqvist, Jesper; Hedin, Görel.

Department of Computer Science, Lund University, 2017. 20 p. (Technical report, LU-CS-TR; Vol. 2017-254, No. Report 103).

Research output: Book/ReportReport

Harvard

Öqvist, J & Hedin, G 2017, Concurrent Circular Reference Attribute Grammars (Extended Version). Technical report, LU-CS-TR, no. Report 103, vol. 2017-254, Department of Computer Science, Lund University.

APA

Öqvist, J., & Hedin, G. (2017). Concurrent Circular Reference Attribute Grammars (Extended Version). (Technical report, LU-CS-TR; Vol. 2017-254, No. Report 103). Department of Computer Science, Lund University.

CBE

Öqvist J, Hedin G 2017. Concurrent Circular Reference Attribute Grammars (Extended Version). Department of Computer Science, Lund University. 20 p. (Technical report, LU-CS-TR; Report 103).

MLA

Öqvist, Jesper and Görel Hedin Concurrent Circular Reference Attribute Grammars (Extended Version) Technical report, LU-CS-TR; Report 103. Department of Computer Science, Lund University. 2017.

Vancouver

Öqvist J, Hedin G. Concurrent Circular Reference Attribute Grammars (Extended Version). Department of Computer Science, Lund University, 2017. 20 p. (Technical report, LU-CS-TR; Report 103).

Author

Öqvist, Jesper ; Hedin, Görel. / Concurrent Circular Reference Attribute Grammars (Extended Version). Department of Computer Science, Lund University, 2017. 20 p. (Technical report, LU-CS-TR; Report 103).

RIS

TY - BOOK

T1 - Concurrent Circular Reference Attribute Grammars (Extended Version)

AU - Öqvist, Jesper

AU - Hedin, Görel

PY - 2017/10/18

Y1 - 2017/10/18

N2 - 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.

AB - 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.

KW - Reference Attribute Grammar

KW - Concurrency

KW - Parallelization

KW - Memoization

KW - Circular Attributes

M3 - Report

T3 - Technical report, LU-CS-TR

BT - Concurrent Circular Reference Attribute Grammars (Extended Version)

PB - Department of Computer Science, Lund University

ER -