Laboratory Exercise 5, February 12

Objectives

The objectives of this exercise are

Turning in Your Project

Turn in a printout of  your project printout as requested by your TA.

Preparing for Lab

You will need to use two separate Internet Explorer windows for the grammar portion of this exercise. 

To Do

Testing

Bring up your scanner.  Run it on each of the following four input files.  Print the results in each case.  Be sure your usual team information is in the upper left hand corner of each page.

Parsing

Click here to bring up the grammar animator.  You will be given directions in class on its use, although most will be self explanatory.

Arithmetic Expressions -- Exercise 1

For this exercise, you will be parsing the string 
a * b + c * b
  1. Bring up the grammar called Arithmetic Exp #1.  To do this, click the Access Grammar Tools Menu button in the animation window.  This brings up another list; click select a different grammar from menu.  Finally click on the desired grammar.  You can now begin working.

    Use this grammar to construct as many different parse trees as you can for this string (a * b + c * b).  After each parse tree has been completed, print it before proceeding to the next problem.  Note, to print, you need to do the following:
    1. put your cursor over the pane containing the grammar applet.
    2. hold down the <ALT> key and hit the Print Screen key.  This puts the image in the Internet Explorer window onto the clipboard.
    3. Open an empty Word page.
    4. Paste into this page.  The Internet Explorer image should now appear there.
    5. Add your usual team info using Word into the upper left corner.
    6. Print the page.

  2. Complete the same exercise using the grammar called Arithmetic Exp #2

  3. Complete the same exercise with the grammar called Arithmetic Exp #3.  

Arithmetic Expression -- Exercise 2

In this exercise you are to try to figure out how the design of a grammar affects practical parsing.  You will be using the arithmetic expression grammars #2 and #3.  Use two Internet Explorer windows, one for each grammar, so that you can compare the two. 

One of the desirable properties of a grammar used for parsing is that we be able to continue parsing with minimal information from the scanner.  We don't want to require the parser to have to get multiple tokens from the scanner just to decide which rule to apply in the current stage of the parse.  To see what we mean, try the following exercises with arithmetic expression grammars #2 and #3. Suppose that the parser is beginning to build the parse tree with <expression> as the root.  At this point suppose that the parser calls the scanner for the next token, and suppose that the scanner returns id.  Apply all the rules in both grammars #2 and #3 that you are certain can be applied (starting with <expression> and always applying the rules to the leftmost nonterminal leaf at any stage) given only the information that the next token is id. 

After the parser can proceed no further, it calls the scanner for the next token.  The scanner returns the token "+".  Again, for both grammars, apply as many rules as you are certain you can apply given this one token before proceeding. Repeat the process for token intlit. Repeat the process for token "+". Repeat the process for token id. Repeat the process for token eof. 

For which grammar could you get the farthest in parsing at each step knowing just the single next token in the input stream?  Print the parse made by that grammar and on the back of that sheet discuss what seemed to make that grammar work well for parsing and why parsing with just one token of information did not work well for the other grammar.

mPascal

Bring up the grammar called microPascal #1 in the applet. Use it to parse the following program.  Notice that this grammar has the same properties as the "better" grammar from the previous exercise.  You can proceed easily through the parse, knowing exactly which rule to apply at any step by just looking at the next token in the program that has not yet appeared in the parse tree. 
     begin
       read(Num);
       Num := Num + 5 * Num;
       write(Num);
     end.
The entire tree will likely not print on the printer, but position your applet window so that the root of the tree is in view and centered, and print that portion.  Sign your team names to the page.

Working with EBNF and CFGs

Connect to the Resources page on our web and bring up the EBNF definition of mPascal.  Use it to do the following.  Give your answers on a sheet of paper with your team names in the upper left corner.
  1. Convert the EBNF rule for StatementSequence into equivalent CFG rules.
  2. Convert the EBNF rule for IfStatement into equivalent CFG rules.
  3. Convert the EBNF rule for WhileStatement into equivalent CFG rules.
  4. Convert the EBNF rule for ForStatement into equivalent CFG rules.
  5. Convert the EBNF rule for SimpleExpression into equivalent CFG rules.
  6. Use the EBNF rules to determine whether the statement X := -A * B is legal.
  7. Use the EBNF to determine whether the statement X := -A * -B is legal.

To Turn In

Turn in your scanner output and the results of the grammar exercises.  Be sure your team information is in the upper left corner:
  1. Your group number
  2. The lab number
  3. Today's date
  4. Your team names and e-mail addresses