[My Crop Circles PIC] JavaArt Chapter 8.   A Compiler for Drawing Crop Circles


This chapter does not appear in the book.


Some years ago I made the mistake of using biorhythms as the basis for a magazine article about dynamic imaging on the Web. I naively thought that a bit of pseudoscience would be a 'fun way' to discuss how to create on-the-fly graphics, especially since the coding only involved sine waves. I was wrong people, who I can only kindly call "crazy-eyed loons", started coming out of the woodwork to ask my opinion on such worthy matters as Circatrigintan, Circavigintan and Circadiseptan cycles.

So it's with some trepidation that I turn to crop circles as a 'fun way' of describing the implementation of a compiler for a little programming language. To be clear: my admiration for crop circles extends only to the beauty of their design, emerging from little more than circles and straight lines. The pictures below shows three examples: formations from Folly Barn in 2001, Tegdown Hill 2003, and Windmill Hill 2003.

[Crop Circles PIC]

I am not a cereologist, an enthusiast who believes crop circles to be the work of extraterrestrials, manifestations of the Gaia hypothesis, or some magical mix of magnetic, radioactive and plasmic vortices. It seems extremely likely, to me at least, that every crop circle is the work of men (and occasionally women) armed with rope-and-plank contraptions called stompers.

Two good places to find out about crop circles is at the "How Stuff Works" site, or Wikipedia.

My interest in crop circle programming was triggered by three articles by Andrew Glassner in IEEE Computer Graphics and Applications, running in the October 2004 to January 2005 issues. He developed a little language called Crop, which understands line and circle drawing operations, and outputs PDF diagrams. For example, the PDF output for the three crop circles are shown below.

[Glassner's Crop Circles PIC]

A summary of the Crop language can be found at Glassner's website. However, he doesn't explain how the language's compiler is implemented.

A little programming language, as compared to a sizeable language such as C++, is aimed at a limited problem domain, which means that it doesn't need to offer the panoply of programming constructs in mainstream languages. This makes the language easier to learn and use, and also simplifies its compiler implementation; all good reasons for using Crop in this chapter.

Glassner's language uses a postfix syntax, which involves pushing and popping operands and operations on and off a stack while they're being evaluated. I've gone for more conventional infix notation for my version of the language, with extra syntactic 'sugar' (e.g. keywords such as "let" and "draw") to make it look more familiar to Java programmers, and incidentally to make Crop programs easier to compile. These are really just surface differences my language offers most of the same data types as Glassner's (e.g. numbers, points, lines, and circles), and operations (e.g. assignment, drawing, iteration).

I'll start by explaining my version of the Crop language through a series of examples, including code that generates the Figure 1 formations. The images at the top of this page shows its output.

Then I'll describe the three main parts of my Crop compiler, which are illustrated below.

[Crop Compiler PIC]

The Lexer reads in the text from a Crop Circles file as a stream of characters, and outputs a stream of tokens (e.g. variable names, keywords, numbers) to the Parser. The parser constructs a parse tree based on the Crop language's grammar, which is passed to the Evaluator. The evaluator employs the Apache Batik library to save Scalable Vector Graphics (SVG) drawing instructions into a file.

I call this application a compiler since the generated SVG code can be thought of as low-level instructions which will be rendered later by a browser or a SVG drawing application, such as Inkscape.

For readers familiar with compiler design, the lexer and parser are written directly in Java, without the aid of lex or yacc-style tools. Lexer employs Java's StreamTokenizer class, and Parser is a recursive descent parser that uses single token lookahead (i.e. it implements a LL(1) grammar). If those sentences just lost you, don't worry since this chapter explains all these ideas.




Dr. Andrew Davison
E-mail: ad@fivedots.coe.psu.ac.th
Back to my home page