JastAdd
This is our old website.
Broken links can occur.
A new website is under construction.

Knuth's Binary Numbers

In his seminal article on attribute grammars from 1968, Semantics of Context-Free Languages, Knuth provided an example grammar computing the values of binary numbers. The example is a nice illustration of attribute grammars because it is small and simple, and makes use of both inherited and synthesized attributes. This directory contains the corresponding JastAdd implementation.

Knuth's example

Context-free grammar

Knuth uses the following context-free grammar to defines the structure of binary numbers

N ::= L
N ::= L "." L
L ::= B
L ::= L B
B ::= "0"
B ::= "1"

Examples of binary numbers following this grammar are both integral numbers like 0, 1, 10, 11, 100, and so on, and rational numbers with an integral and a fractional part, like 1.1, 1.01, 10.01, and so on.

In the JastAdd abstract grammar for this example, the nonterminals N, L, and B, are renamed to BinaryNumber, BitList, and Bit. Furthermore, the productions are given explicit names like IntegralNumber, RationalNumber, SingularBitList, PluralBitList, Zero, and One. See BinaryNumber.ast for details.

Attribution

The idea is to compute the values of the binary numbers using an attribute grammar. Here are a number of test cases:

Binary number

Value (in decimal notation)

0

0

1

1

101

5

0.1

0.5

0.01

0.25

10.01

2.25

1101.01

13.25

 

Knuth provides a couple of different attribute grammars to define the computation. The first one uses synthesized attributes only. The second one, which he argues is closer to the way people usually think about the binary notation, uses both inherited and synthesized attributes. The latter attribution is the one we will illustrate using JastAdd.

In this attribution, each bit has a synthesized attribute value which is a rational number that takes the position of the bit into account. For example, the first bit in the binary number 10.01 will have the value 2 and the last bit will have the value 0.25. In order to define these attributes, each bit also has an inherited attribute scale used to compute the value of a One bit as value = 2scale. So for the bits in 10.01, scale will be 1, 0, -1, -2, respectively.

If we have the values of the individual bits, these values can simply be summed up to the total value. This is done by adding synthesized attributes value both for bit lists and for binary numbers. In order to compute the scale attribute for the individual bits, an inherited attribute scale is added also for bit lists (representing the scale of the rightmost bit in that list), and a synthesized attribute length for bit lists, holding the length of the list.

Knuth uses the abbreviations v, s, and l for the value, scale, and length attributes. The table below shows Knuth's resulting attribute grammar.

Syntactic rules

Semantic rules

B ::= "0"

v(B) = 0

B ::= "1"

v(B) = 2s(B)

L ::= B

v(L) = v(B)
s(B) = s(L)
l(L) = 1

L1 ::= L2 B

v(L1) = v(L2) + v(B)
s(B) = s(L1)
s(L2) = s(L1) + 1
l(L1) = l(L2) + 1

N ::= L

v(N) = v(L)
s(L) = 0

N ::= L1 "." L2

v(N) = v(L1) + v(L2)
s(L1) = 0
s(L2) = - l(L2)

 

The corresponding attribute grammar specified in JastAdd is shown in BinaryNumberValue.jrag. The attributes and equations are exactly the same as in Knuth's example, but using fully spelled out names and (aspect) Java syntax for accessing attributes and the different parts of a production.

Contents of this directory

  • BinaryNumbers.zip for downloading the example to your computer
  • tools: directory containing all the tools you need to run this JastAdd project
    • junit.jar contains the JUnit framework
    • jastadd2.jar contains the JastAdd generation program
  • BinaryNumber.ast abstract grammar for the binary numbers language (input to jastadd).
  • BinaryNumberValue.jrag: An attribute grammar defining how to compute the value of a binary number.
  • 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 AST files generated by JastAdd. This directory is not present when the project is "clean".
  • tests: package containing JUnit test cases and related input and output files
    • BinaryNumbersTests.java: test cases for computing the values of some binary numbers. The test cases create ASTs explicitly by new calls.
  • testframework: package containing classes useful for testing
    • TestAll.java: Used for finding all tesetcases when running tests from a terminal window.
  • release.txt Release and version information about the example

References

  1. D. E. Knuth. Semantics of Context-free Languages. Mathematical Systems Theory, 2(2):127-145. Springer-Verlag, 1968.