Assignment 1

After taking over the operation of the exotic Syntactic Expression train, your company received considerable media coverage and a calamitous drop in passengers following several money saving moves by management. The media drew attention to several mistakes where train cars were mixed in some embarrassing ways; local news reports gleefully carried stories where passenger and dining cars were placed behind (downwind) of circus cars of smelly elephants; passenger trains with no dining cars that had to call ahead for pizzas delivered at road crossings; and on at least one occasion engines placed at opposite ends of the train that played tug-of-war over the passenger cars. Management, proclaiming on the 6 o'clock news to be capable of thinking outside of the boxcar, decided to give someone else the responsibility (you) for solving the problem.

The railroad had five rules to form trains. The rules are stated where each letter stands for a car on the train: E for Engine, C for Caboose, B for a regular Boxcar, P for Passenger, S for a smelly boxcar, and D for Dining car.

1. Trains start with one or more Engines and end with one Caboose; neither can appear anywhere else.
2. Whenever Boxcars appear, they always come in pairs: BB, BBBB, SS, SB, BBSB, etc.
3. There cannot be more than four Passenger cars in a series.
4. A single dining car must follow each series of Passenger cars; it cannot appear anywhere else.
5. A smelly boxcar must never be in front of any Passenger car.

After pondering the problem and recognizing that checking the trains with your own eyeballs would be boring, time consuming, and miserable in times of bad weather, you conclude to send a computer to do the job in your place. To explain the rules to the computer you determine that:

1. The rules stated can be formally written as EBNF (extended Backus-Naur Form) description for <train>. This would follow the conventions as described in the text.
2. The EBNF can be translated into a XML DTD.
3. The train configurations (in the example) can be translated to XML and validated using a parser (such as the JavaScript parser listed below).

You decide as a basic evaluation for management to define and test each of the above a-l train configurations.

Software

The computer portion requires:

1. Defining the DTD for the train rules - write in any text editor and save in file train.dtd for example.
2. Defining the XML for a train using the train rules - write in any text editor and save in file train.xml for example.
3. Parsing the XML train definition - use Microsoft IE5 or Visual InterDev to execute JavaScript train.htm which loads train.xml and parses.

train.dtd - The DTD below defines the rules for a very simple train having only an engine followed by a single caboose.
 

train.xml - The XML defines a train that follows the rules of the DTD above.
 

train.htm - The JavaScript below parses any well-formed XML and displays the node names of the parse tree. The example works on IE browsers; if using another browser see the discussion at: http://www.w3schools.com/dom/dom_parser.asp.
 

<SCRIPT LANGUAGE="JavaScript"> 
var xmlDoc = new ActiveXObject("Microsoft.XMLDOM"); 
try { xmlDoc.load("train.xml"); 
      document.write("<pre>");
      traverse(xmlDoc.documentElement,"");
      document.write("</pre>");
}
catch(e) {   document.write(
               "URL "+xmlDoc.parseError.url+" Line "+xmlDoc.parseError.line+
               " position "+xmlDoc.parseError.linepos+" "+
               xmlDoc.parseError.srcText + " " + xmlDoc.parseError.reason);
} 

function traverse(node,indent) {
  var i, children, type = node.nodeTypeString;
  if (type == "element") {  
      document.write("<br>" + indent + node.nodeName); 
      children = node.childNodes; 
      if (children != null)  
           for (i=0; i<children.length; i++) 
                traverse (children.item(i), indent + "|    ");  
  }
} 
</SCRIPT> 

Internet Explorer - IE5 has an XML parser so can be used to execute the train.htm JavaScript program above. The following illustrates IE5 used to execute the train.htm with all files (train.htm, train.dtd and train.xml) stored in the C:\temp directory. The first example is a valid train while the second example has two engines when only one is allowed by the DTD definitions given in train.dtd above.
 

<!DOCTYPE train SYSTEM "train.dtd"> <train>   <E/>    <C/> </train>	<!DOCTYPE train SYSTEM "train.dtd"> <train>   <E/> <E/>   <C/> </train>

Assignment 2

To make assembling and disassembling trains more efficient by forming a train from several other complete trains, the company managers developed two additional rules:

1. Extend the train definition of Assignment 1 to allow complete trains to be connected end-to-end, that is the caboose of one train followed by the engine of another train. The rule is: 

   A train can follow a caboose. 

   For example: ESBCEPDC 

2. Extend above the train definition to allow complete trains to be embedded within other trains under the following rule:

   A train can follow a dining car.

   For example: EPDEBBCC 

Note that a valid result of these rules is that a train with a smelly boxcar can be inserted in front of a train with passenger cars. 

Turn In

1. Cover sheet with your name, date, and Homework 9.
2. Assignment 1
   1. DTD listing of EBNF for train grammar.
   2. XML listing for each of the a-l train example definitions and corresponding screen shot of parsing of each. Correct trains should be parsed, incorrect trains should produce an error.
3. Assignment 2
   1. DTD listing of EBNF for the extended train grammar.
   2. XML listing for each of the following trains and corresponding screen shot of parsing each.
      1. EBBPDBSCEPPDCEPPDC
      2. EBBPDEPDBSCEPPDCC
      3. EBBPDEPDEBBPDEPDBSCCCCEPDBSC

Document last modified: