ContextfreeGrammar

Using circular attributes to compute nullable, first, and follow.

This is an example of a JastAdd project that makes heavy use of circular attributes. A language "CFG" is defined that allows context-free grammars to be written on a typical Backus-Naur Form. JastAdd aspects with circular attributes are used for defining the following properties:

• nullable(): true if a nonterminal can derive the empty string.
• first(): the set of terminal symbols that derivations of a nonterminal can start with
• follow(): the set of terminal symbols that can follow a nonterminal in a derivation

The definitions of nullable(), first(), and follow() are natural to express using mutually recursive equations. For example, the value of nullable() for a nonterminal depends on the value of nullable() for other nonterminals, possibly including itself. Similarly for the first() set which in addition depends on nullable(). And similarly for the follow() set which in addition depends on first() and nullable(). These equations can be mapped in a straight-forward way to circular attributes.

To make use of circular attributes, their values should be arranged in a lattice of finite height, and all equations monotonic, i.e., such that they can only raise the attribute to a higher level in the lattice. The computation of the attribute can then be performed with a terminating iteration. The nullable() attribute makes use of a boolean lattice with FALSE at the bottom and TRUE at the top. Equations can only raise the value from the starting value FALSE.

The first() and follow() attributes make use of set lattices with the empty set at the bottom and the set of all terminal symbols at the top. The equations can only raise the value to sets including more terminal symbols.

The implementation also makes use of a reference attribute decl() which binds uses of nonterminals (i.e., nonterminal occurrences in the right-hand side of productions) to declarations of the corresponding nonterminal (i.e., nonterminal occurrences in the left-hand side of a production). The decl() attribute is used for propagating information about nonterminal declarations directly to their uses.

For a more detailed discussion of the example, see the article "Circular Reference Attributed Grammars - Their Evaluation and Applications".

Contents of this directory

• ContextfreeGrammar.zip for downloading the example to your computer
• grammars
  • CFG.ast: abstract grammar for the language describing context-free grammars.
  • CFGrammar.jjt: parsing and AST-building grammar for the CFG language (input to the tool jjtree). An example explaining how jjtree interacts with JastAdd is available here
• aspects
  • NameAnalysis.jrag: Defines name analysis for nonterminal names in the CFG language: Each use of a nonterminal name (NUse) has a reference attribute decl() that refers to the appropriate declaration of the nonterminal (NDecl).
  • Nullable.jrag: Uses circular attributes for computing whether a nonterminal is nullable or not: Each nonterminal declaration (NDecl) has a boolean attribute nullable().
  • First.jrag: Uses circular attributes for computing the set of first symbols for nonterminals: Each nonterminal declaration (NDecl) has a set attribute first() whose elements are the terminal symbols (represented as Strings) that belong to the First set.
  • Follow.jrag: Uses circular attributes for computing the set of follow symbols for nonterminals: Each nonterminal declaration (NDecl) has a set attribute follow() whose elements are the terminal symbols (represented as Strings) that belong to the Follow set.
  • PrettyPrint.jrag: Defines a string attribute pp() that is a prettyprinted representation of a CFG.
• tests: package containing JUnit test cases.
  • TestNullable.java: tests the computation of nullable as defined in Nullable.jrag.
  • TestFirst.java: tests the computation of the first set as defined in First.jrag.
  • TestFollow.java: tests the computation of the follow set as defined in Follow.jrag.
  • TestNameAnalysis.java: tests the name analysis as defined in NameAnalysis.jrag.
  • TestParser.java: tests the prettyprinting as defined in PrettyPrint.jrag.
• TestGrammars: directory containing input and output files to the JUnit test cases. The input files are grammars written in the CFG language. Output files are only available for the large grammars, and contain the results of computing nullable, first, and follow.
  • TestGrammarSimple: A very simple context-free grammar.
  • A number of context-free grammars exercising various special cases of empty and alternative productions:
    • TestEmptyProd
    • TestEmptyAlternativeProd
    • TestAlternativeEmptyProd
    • TestAlternativeProd
    • TestFirstEmptyAlternatives
  • TestAppelGrammar: A small but nontrivial example grammar, taken from Andrew Appel's book "Modern Compiler Implementation in Java".
  • TestManyProds: A small grammar with a few productions, only used for testing the prettyprinting functionality.
  • Test of Java grammar. The grammar is sorted alphabetically to facilitate comparison with expected results.
    • TestJavaGrammarSorted: A context-free grammar for Java, sorted alphabetically.
    • TestJavaGrammarNullableResult: The expected result for the computation of nullable for each nonterminal.
    • TestJavaGrammarFirstResult: The expected result for the computation of the First set for each nonterminal.
    • TestJavaGrammarFollowResult: The expected result for the computation of the Follow set for each nonterminal.
• testframework: package containing classes useful for testing
  • FileContentsTestCase.java: Can compare the contents of two files, ignoring whitespace.
  • TestAll.java: Used for finding all testcases when running tests from a terminal window.
• tools: directory containing all the tools you need to run this JastAdd project (jastadd, javacc, junit).
• build.xml: Ant build file to be used from a terminal window and from Eclipse
  • Use the targets build (default), test, and clean, when working from a terminal window. For example, type

    ant	generate all java files and compile them
    ant test	run all test cases
    ant clean	remove all generated files and all the class files for both generated and handwritten java files

  • Use the targets gen and cleanGen when working from eclipse (see Running JastAdd Under Eclipse):

    ant gen	generate all java files
    ant cleanGen	remove all generated files and their class files.

• AST: package containing files generated by the tools (JavaCC and JastAdd). This directory is not present when the project is "clean". The directory will contain parser files generated by JavaCC and AST files generated by JastAdd.