3.5 Example: Designing a Grammar for a Track Robot

Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  3.   Building a Parser


Figure 3.4 shows a miniature factory for which we want to design a command language. The heart of the factory is a track robot, a machine that can move forward and backward along a track. The robot can pick up material from conveyor belts and place the material on other conveyors. The robot transports material in metal containers called "carriers." The basic flow of the factory has the robot pick and place carriers so that they go through two processing machines and arrive at an output conveyor. Carriers have bar code labels that the robot is able to scan, letting the robot ascertain the identity of a carrier and arrive at a machine's output.

Figure 3.4. A track robot. In this miniature automated factory, a simple robot runs along a track, picking and placing material on machines.


Humans tend to see the factory in Figure 3.4 as consisting of a track robot, two input and output conveyors, and two processing machines. The robot does not see the machines ”it sees only conveyors ”so our command language for the robot will be conveyor-centric. Here are some example commands for the robot:

 pick carrier from LINE_IN  place carrier at DB101_IN pick carrier from DB101_OUT place carrier at WB500_IN pick carrier from WB500_OUT place carrier at LINE_OUT scan DB101_OUT 

3.5.1 A Track Robot Grammar

You want a command parser that will recognize the language that will drive the robot. Initially, your grammar is


You need to define the command parser in terms of other parsers, and you know that you want to recognize three commands. So you can give the first rule of the grammar as

 command = pickCommand  placeCommand  scanCommand; 

You need to refine this grammar, expanding every parser on the right side of a definition until every subparser is defined or is a terminal. Consider the subparser pickCommand . You know that the robot is willing to pick up carriers; you only have to tell it the location. For a definition that matches your sample strings, you can augment the grammar:

 command     = pickCommand  placeCommand  scanCommand;  pickCommand = "pick" "carrier" "from" location; 

You could make the words "carrier" and "from" optional, but let's keep the language simple for now. With simplicity in mind, let's also assume that each word in quotes in the grammar will be a CaselessLiteral so that users can type "pick" , "Pick" , or "PICK" .

Judging by the sample command strings, a location is always a single word:

 command     = pickCommand  placeCommand  scanCommand;  pickCommand = "pick" "carrier" "from" location; location    = Word; 

You can complete the grammar design by defining the remaining subparsers ” placeCommand and scanCommand :

 command      = pickCommand  placeCommand  scanCommand;  pickCommand  = "pick" "carrier" "from" location; placeCommand = "place" "carrier" "at" location; scanCommand  = "scan" location; location     = Word; 

3.5.2 Checking for Left Recursion and Cycles

The grammar for the track robot language is complete, but only because it contains no left recursion and no cyclic dependencies. Left recursion exists if a parser's definition begins with itself. Cyclic dependencies exist if a parser's definition ultimately depends on itself. The grammar doesn't have these features so you can skip some steps described in Chapter 6, "Transforming a Grammar."


Building Parsers with Java
Building Parsers With Javaв„ў
ISBN: 0201719622
EAN: 2147483647
Year: 2000
Pages: 169

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net