Building Parsers With Java(TM) (Paperback)

~ (Author)

Editorial Reviews

Product Description

(Pearson Education) An in-depth explanation of how to create parsers that recognize custom programming languages. The CD-ROM contains all of the examples from the text, the parser toolkit, and other helpful materials. System requirements not listed. Softcover. DLC: Java (Computer program language).

From the Inside Flap

The premise of this book is that by learning how to work with parsers, you can create new computer languages that exactly fit your domain. When you create a language, you give your language users a new way to control their computers. By learning about parsers, you learn to define the way your users interact with computers using text. Who Should Read This Book This book assumes you have a good understanding of Java and would like to learn how to do the following: Use a handful of tools to create new computer languages quickly. Translate the design of a language into code. Create new computer languages with Extensible Markup Language (XML). Accept an arithmetic formula from your user and compute its result.

Accept and apply matching expressions such as th*

one.

Create query languages that fire an engine. Program in logic and create a logic language parser. Make rules-based programming available to your users from within a Java application. Program in Sling, a new computer language that plots the path of a sling. Create computer languages that fill niches in the work you do. Using the Toolkit Code and the Sample Code

This book comes with a CD that contains all the code. Contents of the CD

The CD includes all the code of the fundamental parser classes, the logic engine, and all the examples. The CD also contains the javadoc documentation from the code, which explains class by class how the code works. Applying the Code on the CD

The code on the CD is free. It is copyrighted, so you may not claim that you wrote it. Otherwise, you may use the code as you wish. Hello World

The following program is a sufficient test to verify that you can use the

code from the CD. Load the code from the CD into your development environment.

Type in the following program, or load it from

ShowHello.java on the CD. package sjm.examples.preface; import sjm.parse.*; import sjm.parse.tokens.*; public class ShowHello { public static void main(String args) {

Terminal t = new Terminal();

Repetition r = new Repetition(t);

Assembly in = new TokenAssembly("Hello world!");

Assembly out = rpleteMatch(in);

System.out.println(out.getStack()); } }

Compiling and running this class prints the following: Hello, world, !

Once you get this running in your environment, you will be able to use all the fundamental classes and all the examples in this book. Coding Style

Some features of the coding style in this book may seem unusual. First, this book does not indent method signatures. This practice stems from the fact that the VisualAge development environment exports classes this way, resulting in a pair of curly braces at the end of a class. This convention has the happy effect of allowing a little more space before statements are wrapped within the narrow margins of this book.

Another feature of the coding style in this book that may give you pause is

the use of extremely short variable names. Methods in this book nearly always

perform a single service and thus are short. Temporary variables are never far

from their declarations, and there is usually no need for names longer than

one character. For example, it is not difficult in the preceding program to

discern that the variable t refers

to a Terminal object. In the

rare event that two variables of a given type occur in one method, they receive

meaningful names, such as in and out in the preceding example.

Comments in the code use javadoc

tags such as @param and @exception,

but the text usually omits these to save space. Comments for public methods

begin with Related Books

This book requires that you have a good knowledge of Java. It will help to have available a good resource on Java, particularly The Java Programming Language, by Ken Arnold and James Gosling.

This book makes many references to design patterns. Although this book explains the basics of each pattern as it is introduced, it will help to have at hand Design Patterns, by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides.

This book uses the Unified Modeling Language as a notation for describing object-oriented design. This book includes an appendix on this notation, but it will help to have available The Unified Modeling Language User Guide, by Grady Booch, James Rumbaugh, and Ivar Jacobsen.

These books and others are listed in the References section. Theoretical Context

This book does not assume that you understand compilers and language theory.

But if you are well grounded in these topics, you may want to know where

this book sits within established theory. This section explains the type of

parsers that this book covers and describes how this book differs from others

in terms of conventions regarding grammars and abstract syntax trees.

All parsers in this book are nondeterministic recursive-descent parsers. If

you are interested in learning about other types of parsers, the classic source

on this topic is Compilers: Principles, Techniques, and Tools Aho et

al.. The choice of nondeterministic recursive-descent parsers springs from

two objectives. The first is to empower a developer of a new little language

to easily transition from language design to the implementation of a parser.

The second objective is to answer the Extreme Programming question, "What is

the simplest thing that could possibly work?" Beck, page 30.

To simplify the coding of a parser from its design, a parsing technique should

let a developer translate a grammar directly into a parser. The sequences, alternations,

and repetitions in a grammar must correspond directly to instances of Sequence,

Alternation, and Repetition

classes. Furthermore, the developer should face few restrictions in the allowable

attributes of an input grammar. Nondeterministic recursive-descent parsing provides

a comparatively simple approach to meeting these objectives.

Nondeterminism is a central problem of parser construction; parsers do not

always know which path to take as they recognize text. Nondeterministic recursive-descent

parsing solves this problem by using sets to allow all possible parser

paths to proceed. This approach used to be too slow, but modern computers make

it sufficient for small languages, including all the languages in this book.

An advantage of this approach is that the parsers accept any context-free grammar

as long as the developer removes left recursion, by using a technique explained

in this book. Nondeterministic recursive-descent parsers provide a broadly applicable

and simply implemented approach to empowering developers of new languages.

The conventions in this book also differ from some conventions for writing grammars. Specifically, grammars in this book use class names to represent terminals and use semicolons to mark the end of rules. These standards support the simplicity of the translation from grammar to code.

Finally, this book is unusual in the little treatment it gives to abstract syntax trees (ASTs). It is common practice to parse input, create an AST, and then walk the tree. This book argues that it is more effective to build a target object as a parse completes, working on the result as each grammar rule succeeds. Most of the examples in this book build a useful result while parsing an input string, but none of the examples constructs an AST. Yacc and Lex and Bison and Flex

A variety of tools that facilitate parser building are freely available on

the Internet. The tools yacc and bison accept the design of a

language (its grammar) and generate a parser. The tools lex and

flex help to collect characters into words, numbers, or tokens.

All these tools generate C code, but there are newer tools that are oriented

toward Java, such as the javacc tool.

All these tools require a developer to design a parser in one language and then generate it in another language. For example, to use javacc you must enter a grammar according to the rules of javacc. Then you can feed these rules to the tool to generate the Java code of a parser.

The use of a generator forces you to work in two languages: the language of

the generator and the target language, C or Java. This book does not use generators,

advocating instead that you enter Java code directly from the grammar. Sequences,

alternations, and repetitions in the grammar become Sequence,

Alternation, and Repetition

objects in your code. The advantage is that the only language you need to know

to start creating parsers is Java.

An advantage of using generators such as yacc is that they produce parsers that are much faster than parsers built with the techniques used in this book. The value of this speed depends on the length of the language elements your parser must face. If you create a parser using the techniques in this book and find that you want more speed, you can consider porting your parser to use a tool such as yacc. At that point, you will be comfortable with the rules and meaning of your language, and that will make implementation in yacc much easier.

If you have used yacc or other parser generators, you will find the material in this book familiar territory. Similarly, learning the techniques in this book will prepare you to use parser generators. All parser tools share the aim of helping you to become a language developer. About the Cover

The cover illustration is original artwork by Steve Metsker. The art form is known as "ASCII-art" and calls for the artist to draw upon a limited set of characters. ASCII is a standard that, like Unicode, specifies a set of characters and their approximate appearance. The artist applies this palette to express meaning that transcends the value inherent in the characters.

The ASCII artist and the computer programmer summon meaning from the keyboard for differing purposes. Adherents of either art may seek and may achieve mastery over their characters, learning to conjure powerful objects from a primitive source. The dragon rider on the cover extends the mastery theme, depicting the knight's mastery over the dangerous and powerful dragon. The dragon represents the complexity of creating new computer languages; the knight represents you, who can master the dragon for your own purpose

0201719622P04062001

See all Editorial Reviews

Product Details

• Paperback: 371 pages
• Publisher: Addison-Wesley Professional (April 5, 2001)
• Language: English
• ISBN-10: 0201719622
• ISBN-13: 978-0201719628
• Product Dimensions: 9.1 x 7.4 x 1.1 inches
• Shipping Weight: 1.4 pounds (View shipping rates and policies)
• Average Customer Review: 4.3 out of 5 stars  See all reviews (18 customer reviews)
• Amazon.com Sales Rank: #357,484 in Books (See Bestsellers in Books)

Customer Reviews

Most Helpful Customer Reviews

37 of 38 people found the following review helpful:

5.0 out of 5 stars John Vlissides Foreword is right on the money, May 18, 2001

By	Robert Sartin (Austin, TX) - See all my reviews (REAL NAME)

The foreword says "Traditional parsing tools are overkill at best, antiquated and unusable at worst. The result? Ad hoc has become the parsing approach of choice.

But when I read this book, I had a change of heart."

So did I. I came across this book (a week and a half ago) when I was just about to begin designing a small language to embed in an application. I was loathing the task to come because the parser development tools are all oriented towards large languages and there's nothing to help with small ones. I really didn't want to go learn all about JavaCC or SableCC. They are both excellent tools, but overkill for my tiny language.

The first day, I read chapters 1-5 and wrote a couple of experimental attempts at pieces of our desired langauge to prove that it would work. The second day, reading material from chapters 4 (on testing), 5 (on data languages), and 6 (on transforming grammars), I paired with another developer and we developed the entire grammar for our little language. The third day, we used chapter 5 again and bits of chapters 10 (Matching Mechanics) and 16 (Parsing an Imperative Language) to develop the actions in our language.

Absolutely fantastic. Useful. Practical. On topic without the wasted digressions introducing basic Java concepts that are so prevalent in many Java books.

33 of 34 people found the following review helpful:

3.0 out of 5 stars Fair -- But somewhat incomplete, March 27, 2002

By	Brent Fulgham (Ventura, CA United States) - See all my reviews (REAL NAME)

This book is well written with few spelling/typographical errors. However, it's title is a bit misleading. I expected the book to explain how to develop a parser from the ground up (tokenizing the input strings, recognizing the syntax, dispatching to appropriate code based on the recognized symbols, etc.)

Instead, the book shows how to build parsers using the authors own parser toolkit. The toolkit seems to be quite good, with lots of useful facilities. However I found myself frustrated because it seemed like the most interesting topics were effectively avoided by making them part of the toolkit.

Want to build an interpreter? Use the author's "Engine" class -- just pass it your language rules. Want to parse a different language? Use the author's parser tools, just pass it information about the syntax.

Still, the book does provide good descriptions of the spaces between the low-level details of tokenizing and interpreting. It's just dissapointing that it doesn't provide more coverage of the "black arts" of parser design.

10 of 12 people found the following review helpful:

3.0 out of 5 stars Beware the Parser Framework!, October 26, 2003

By	Adam Pasztory "adampasz" (San Francisco, CA United States) - See all my reviews (REAL NAME)

I agree with the other 3-star reviews of this book. It's full of fascinating ideas about a very advanced topic, but the fact that everything is so dependent on the included framework makes it difficult to learn from. I think the best programming books teach you how to build step-by-step from the ground up. Instead, this book expects you to immerse yourself in the code first, and then figure things out from there.