Newsletter sign-up
View all newsletters

Enterprise Java Newsletter
Stay up to date on the latest tutorials and Java community news posted on JavaWorld

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

JavaWorld.com > Java Development Tools >

Looking for lex and yacc for Java? You don't know Jack

How to get and use Sun's free automatic Java parser generator -- a unique new tool that's a must for Java compiler developers

By Chuck Mcmanis, JavaWorld.com, 12/01/96

  • Print
  • Feedback
.
Sun has released Jack, a new tool written in Java that automatically generates parsers by compiling a high-level grammar specification stored in a text file. This article will serve as an introduction to this new tool. The first part of the article covers a brief introduction to automatic parser generation, and my first experiences with them. Then the article will focus on Jack and how you can use it to generate parsers and applications built with those parsers, based on your high-level grammar.

Automatic compiler parser generation

A parser is one of the most common components of a computer application. It converts text that can be read by humans into data structures known as parse trees, which are understood by the computer. I distinctly remember my introduction to automatic parser generation: In college I had completed a class on compiler construction. With the help of my wife to be, I had written a simple compiler that could turn programs written in a language made up for the class into executable programs. I remember feeling very accomplished at that point.

In my first "real" job after college, I got an assigment to create a new graphics processing language to compile into commands for a graphics coprocessor. I started with a freshly composed grammar and prepared to launch into the multiweek project of putting together a compiler. Then a friend showed me the Unix utilities lex and yacc. Lex built lexical analyzers from regular expressions, and yacc reduced a grammar specification into a table-driven compiler that could produce code when it had successfully parsed productions from that grammar. I used lex and yacc, and in less than a week my compiler was up and running! Later, the Free Software Foundation's GNU project produced "improved" versions of lex and yacc -- named flex and bison -- for use on platforms that did not run a derivative of the Unix operating system.

The world of automatic parser generation advanced again when Terrence Parr, then a student at Purdue University, created the Purdue Compiler Construction Tool Set or PCCTS. Two components of PCCTS -- DFA and ANTLR -- provide the same functions as lex and yacc; however the grammars that ANTLR accepts are LL(k) grammars as opposed to the LALR grammars used by yacc. Furthermore, the code that PCCTS generates is much more readable than the code generated by yacc. By generating code that is easier to read, PCCTS makes it easier for a human reading the code to understand what the various pieces are doing. This understanding can be essential when trying to diagnose errors in the grammar specification. PCCTS quickly developed a following of folks who found its files easier to use than yacc.

The power of automatic parser generation is that it allows users to concentrate on the grammar and not worry about the correctness of the implementation. This can be a tremendous time-saver in both simple and complex projects.

Jack steps up to the plate

I rate tools by the generality of the problem they solve. As the requirement to parse text input comes up again and again, automatic parser generation rates pretty highly in my toolbox. Combined with the rapid development cycle of Java, automatic parser generation provides a tool for compiler design that is hard to beat.

  • Print
  • Feedback

Resources