Reference Attribute Grammars
When
This course has been given twice: during Spring 2010 and Spring 2011.
Prerequisites
Java and JUnit. Basic knowledge about scanning, parsing, and abstract syntax trees.
Introduction
With reference attribute grammars, static analyses can be implemented declaratively. Examples include name analysis, type checking, control-flow and dataflow analysis. This allows implementation of compilers and related tools to be done in a compact and extensible way. In this course, we study how to use reference attribute grammars for compiler-oriented applications, using the JastAdd metacompilation system.
Course leader
Görel Hedin, gorel AT cs.lth.se
Form
The course is divided into a number of course items. Each item contains some literature to read, and usually some exercises to do. For each course item you should write a short summary of 2-3 pages of what you have learnt, and things you wonder about and would like to discuss. We will then meet after each item for a short discussion. Commit your summary and experiments to a common repository the day before this discussion at the latest. Look through a couple of other summaries and experiments before the discussion. There will be a list for who looks at what.
After this course part, you may do an individual project during the summer. The project can be an implementation of a language from scratch, for example an experimental domain-specific language that you can use in your research. It could also be an extension of an existing language implementation, for example JastAddJ, either with new experimental language constructs, or for doing some special-purpose program analysis. We will have a meeting early fall where you will present your projects.
Credits
6 hp for participating in the theory part. An additional 3 hp for doing a project. 6 hp nominally corresponds to 4 weeks, i.e., 20 full work days, considering an academic year of 40 weeks. So, the idea is to spend around 3 days on each of the 7 items, and 2 weeks on the project.
Schedule
TBA
Course items
1. INTRODUCTORY TUTORIAL
Learn about reference attributes and related basic attribution mechanisms in JastAdd from the following introductory tutorial:
G. Hedin. Tutorial: An Introductory Tutorial on JastAdd Attribute Grammars GTTSE III, 166-200, LNCS 6491, 2011.
http://dx.doi.org/10.1007/978-3-642-18023-1_4
While you read, try to solve all the exercises, and try out the examples in practice, using JastAdd. An implementation of the examples is available at:
Try to think by yourself first, before looking at the solutions.
Also, do your own experiments:
Create a very small language, for example with A ::= B C; etc, and try out the attribution mechanisms on your own: reference attributes, parameterized attributes, collection attributes, and circular attributes. Write JUnit test cases to check the results. Look at the reference manual at jastadd.org if needed. Set up the project directory in the same way as for the tutorial, with an ant build-file, etc. Make sure all tests work before handing in.
2. NAME AND TYPE ANALYSIS
The tutorial above has some extremely simple name analysis for a flat scope. To get an idea of how name and type analysis for a normal programming language is typically solved in JastAdd, read the following paper:
T. Ekman and G. Hedin. Modular Name Analysis for Java Using JastAdd. GTTSE 2006: 422-436, LNCS 4143, Springer.
http://dx.doi.org/10.1007/11877028_18
And download, run, and inspect the implementation of JavaDemoNames, available at the JastAdd site:
The JavaDemoNames examples makes use of some mechanisms that were not covered in the introductory tutorial: rewrites, interfaces, and imperative aspects (.jadd files). If you need more information about any of this, look at the jastadd.org site, or ask Görel.
Also, do some experiments:
Create a very small language of your own with some kind of nested functions. Make it as simple as you can, with the goal of trying out some name and type analysis. Implement it, using the same approach as in JavaDemoNames, but avoid rewrites, interfaces and imperative aspects - you should not need them for this simple experiment.
Add a collection attribute for collecting compile-time errors in your AST root. Use contributions to add checks for various kinds of errors, such as undeclared names, multiply-defned names, incompatible types, etc.
Test your implementation using JUnit test cases.
3. INTEGRATING WITH A PARSER
In the two examples above, abstract syntax trees are created by manual code, using the creational API. As soon as you start working with larger languages and larger test cases, it is a good idea to integrate with a parser.
For JastAdd projects we usually use the LALR-based parser beaver. There is also a beaver preprocessor tool called JastAddParser that makes it easier to write the beaver specifications and to build the JastAdd ASTs. This tool also makes it possible to combine several parser specifications if you are extending you language modularly.
Download, run, and study the following projects to understand how to integrate a parser using beaver and JastAddParser.
- http://jastadd.org/tutorial/Lang.zip - This is an extremely small language, and the code can be used as boilerplate for your own project.
- http://jastadd.org/tutorial/Lang-Solution.zip - This is a small state machine language, very similar to the one studied during course item 1.
Extend your project from the last course item, to integrate a parser. Here is essentially what you need to do (let me know if I forgot to list something):
- Add the parsing tools to your tools directory: JFlex.jar, beaver.jar, beaver-rt.jar, JastAddParser.jar
- Write a .flex file for your language, defining the keywords and other tokens used in your language.
- Write a .parser file for your language, defining the parsing grammar and semantic actions for building the JastAdd AST. This file is processed by the JastAddParser.jar tool to produce the corresponding but more verbose beaver specifications.
- Update your build.xml file to incorporate the parser generation.
- Write a main program that will serve as the "compiler" of your language, reading in an input file and writing out any compile time errors in the file, preferrably including the line number. If you would like to add something resembling code generation, you can simply prettyprint the AST.
- Add at least one test program in your language, and the expected result, to show that the compiler works. Preferrably, add a JUnit test that checks this as well.
4. JASTADDJ
There is a complete Java compiler implemented in JastAdd. It is called JastAddJ, and it is used in research projects worldwide. Read about it in the following paper:
T. Ekman and G. Hedin. The JastAdd Extensible Java Compiler. OOPSLA 2007, 1-18
http://doi.acm.org/10.1145/1297027.1297029
Download, run, and inspect the implementation:
Make your own extension of Java 1.4, using the same approach as for Java 5.
To keep this exercise simple, I suggest you just add the foreach loop, looking at the implementation in Java 5. It is sufficient to extend the frontend part. You don't need to extend the backend.
5. ADDITIONAL MECHANISMS
There are a few more mechanisms that you have not yet tried out: rewrites, nonterminal attributes, inter-ast references, and interfaces. For some of them there is not so much documentation.
- For rewrites, see the name analysis paper above, and also the following paper: T. Ekman and G. Hedin. Rewritable Reference Attributed Grammars. ECOOP 2004.
http://dx.doi.org/10.1007/978-3-540-24851-4_7 - For nonterminal attributes, read the documentation and look at the JastAddJ implementation of generics (using the keyword "nta").
- For inter-ast references, look at the following paper (you don't need to read all of it, just the parts about inter-ast references): J. Åkesson, T. Ekman, G. Hedin: Implementation of a Modelica compiler using JastAdd attribute grammars, Science of Computer Programming. Volume 75, Issues 1-2, 1 January 2010, Pages 21-38. http://dx.doi.org/10.1016/j.scico.2009.07.003 . There are also some examples of inter-ast references in JastAddJ.
- For interfaces, look at the JastAddJ implementation (grep for "interface" and "implements").
Try our these mechanisms in your experimental langauge.
6.a INTEGRATING WITH ECLIPSE
Now that you have a parser, you can start integrating with Eclipse to get simple interactive support like an editor with syntax highlighting and feedback on your compile-time errors.
Instructions:
To be added. Or discuss with Emma.
6.b (Alternative to 6.a) EXPERIMENTS WITH KIAMA OR SILVER
Silver and Kiama are two other systems supporting reference attribute grammars. Read about these systems and implement your own small language from items 1-3 and 5 using either Silver or Kiama. What are the advantages and disadvantages of the different systems? Silver and Kiama do not support JastAdd-like rewrites, but they have a mechanism called forwarding which is somewhat similar. Some relevant pointers:
E. Van Wyk, O. de Moor, K. Backhouse, P. Kwiatkowski: Forwarding in Attribute Grammars for Modular Language Design. CC 2002. http://dx.doi.org/10.1007/3-540-45937-5_11
E. Van Wyk, D. Bodin, J. Gao, L. Krishnan: Silver: An extensible attribute grammar system. SCP Vol 75, Issue 1-2. Jan 2010, Elsevier. http://dx.doi.org/10.1016/j.scico.2009.07.004
A. M. Sloane. Lightweight Language Processing in Kiama. GTTSE 2009. LNCS 6491, Springer 2011. http://dx.doi.org/10.1007/978-3-642-18023-1_12
7. HISTORY AND OUTLOOK
Attribute grammars were introduced by Knuth in 1968. Reference attribute grammars are an extension where attributes may be reference to other syntax nodes, and not just ordinary values. There are many other attribute grammar systems, but very few support reference attributes.
Read Knuth's seminal paper on attribute grammars and my paper on reference attributes.
D. Knuth. Semantics of Context-Free Languages. Mathematical Systems Theory 2(2): 127-145 (1968). http://dx.doi.org/10.1007/BF01692511
G. Hedin. Reference Attributed Grammars. Informatica 24(2000) 301-317, Slovenia. http://www.cs.lth.se/home/Gorel_Hedin/publications/2000-RAGsInformatica-PreliminaryVersion.pdf
Find out briefly about some other well-known attribute grammar systems: Eli, Lrc, and the Synthesizer Generator.
Find out briefly about some other attribute grammar systems that use reference attributes: Silver, Kiama.