Building Parsers with Java - Softcover

Metsker, Steven John Metsker

Softcover

ISBN 10: 0201719622 ISBN 13: 9780201719628

Publisher: Addison-Wesley Professional, 2001

Synopsis

Parser building is a powerful programming technique that opens a world of opportunity for designing how users interact with applications. By creating mini-languages, you can precisely address the requirements of your application development domain. Writing your own parsers empowers you to access a database more effectively than SQL to efficiently control the movement of an order through its workflow, to command the actions of a robot, and to control access privileges to transactions in a system. The repertoire of todays professional programmer should include the know-how to create custom languages. Building Parsers with Java shows how to create parsers that recognize custom programming languages. This book and its accompanying CD provide an in-depth explanation and clearly written tutorial on writing parsers, following the Interpreter Design Pattern. An easy-to-follow demonstration on how to apply parsers to vital development tasks is included, using more than a hundred short examples, numerous UML diagrams, and a pure Java parser toolkit to illustrate key points. You will learn *How to design, code, and test a working parser *How to create a parser to read a data language, and how

About this title

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

About the Author

Steven John Metsker is a Managing Consultant with Dominion Digital, an information technology and business process reengineering company. Steve specializes in object-oriented techniques for creating clean, powerful software, and he is the author of Building Parsers with Java™, Design Patterns Java™ Workbook, and Design Patterns in C# (all from Addison-Wesley).

Edition details

• Publisher: Addison-Wesley Professional
• Publication date: 2001
• ISBN 10: 0201719622
• ISBN 13: 9780201719628
• Binding: Paperback
• Language: English
• Edition number: 1
• Number of pages: 400