Midterm CSU 670
Fall 2005					October 18, 2005


Question 1:
============================================================
40 points

Writing a simple translator

Write a program that translates from the language of class dictionary
g1 to the language of the class dictionary g2.

g1:

Main = <s> String.
SPL = Block.
Block = "{" List(Declaration) "body" NList(Statement) "}".
Declaration = "(" Type Variable "=" Exp ")".
Type : Bool | Inte.
Bool = "bool".
Inte = "int".
Variable = Ident.
Exp : Simple | Compound.
Simple : Variable | Numbe.
Numbe = <val> int.
Compound = "(" <arg1> Exp Op <arg2> Exp ")".
Op : Plus | GT.
Plus = "+".
GT = ">".
Statement :
  Assignment | IfStat | WhileStat.
Assignment = "(" Variable "=" Exp ")".
IfStat = "(if" Exp <thePart> Block "else" <elsePart> Block ")".
WhileStat = "(while" Exp Block ")".
List(S) ~ {S}.
NList(S) ~ S {S}.


g2:

Main = <s> String.
SPL = Block.
Block = "(" List(Declaration) NList(Statement) ")".
Declaration = "(" Type Variable "=" Exp ")".
Type : Bool | Inte.
Bool = "bool".
Inte = "int".
Variable = Ident.
Exp : Simple | Compound.
Simple : Variable | Numbe.
Numbe = <val> int.
Compound = "(" <arg1> Exp Op <arg2> Exp ")".
Op : Plus | GT.
Plus = "+".
GT = ">".
Statement :
  Assignment | IfStat | WhileStat.
Assignment = "(" Variable "=" Exp ")".
IfStat = "(if" Exp <thePart> Block "else" <elsePart> Block ")".
WhileStat = "(while" Exp Block ")".
List(S) ~ "(" {S} ")".
NList(S) ~ "(" S {S} ")".

Example:


{ (int x = 10)
  (bool b = (0 > 0))
  body
    (x = 11)
    (while b { body (
      x = x) 
      (while c { body (
        y = y)
      })
    })
}


(((int x=10)
  (bool b=(0>0)))
    (
      (x=11)
      (while b(
        ()(
        (x=x)
	(while c(
	  ()(
	  (y=y)))))))))

White space (spaces and new lines) is not important.

Turn in a description of the process you would use to write 
the program and turn in the important parts of the program.
Explain why your program works.


Question 2:
============================================================
10 UNKNOWNs, 4 points per each: 40 points
Complete a program

Consider again class dictionary g1 from question 1.
Write a program that takes an SPL-object 
as input and prints the depth of all the blocks
that are contained in the SPL-object.
For example, for the input:

{ (int x = 10)
  (bool b = (0 > 0))
  body
    (x = 11)
    (while b { body (
      x = x) 
      (while c { body (
        y = y)
      })
    })
}

your program should print:

{(int x=10)(bool b=(0>0))body(x=11)(while b{body(x=x)(while c{body(y=y)})})}
Depth =1
{body(x=x)(while c{body(y=y)})}
Depth =2
{body(y=y)}
Depth =3

Find the UNKNOWNs below:

Main {
{{
  static UNKNOWN1 cg;
  public static void main(String args[]) throws Exception {
    SPL m = SPL.UNKNOWN2(System.in);
    cg = new UNKNOWN3(true,false);
    m.depth();
    System.out.println("done");
    System.out.println();
}}
}

Block {
  void print() to * (PrintVisitor);
}


SPL {
{{
void depth(){
  Main.cg.traverse(UNKNOWN4,"from UNKNOWN5 to UNKNOWN6",new Visitor() {
   int dep;
   public void start() {UNKNOWN7;}
   void before(UNKNOWN8 host) {
    UNKNOWN9;
    host.print();
    System.out.println();
    System.out.println("Depth =" + dep);}
   void after(UNKNOWN10 host) { dep--;}
   }
   );};
}}
}

Question 3:
============================================================
31 UNKNOWNs, 0.5 points each: 15.5 points
Parsing

Consider again class dictionary g1.
The display method:

SPL {
  void display() to * (DisplayVisitor);
}

prints for this input:

{(int x=10)(bool b=(0>0))body(x=11)
  (while b{body(x=x)(while c{body(y=y)})})}

the following output. Find the UNKNOWNs.

: SPL  (
<block> : UNKNOWN1  (
  <declaration_list> : UNKNOWN2  {
    <first> : Nonempty_Declaration_List  (
      <it> : UNKNOWN3  (
        <type> : UNKNOWN4  ( )
        <variable> : Variable  (
          <ident>  : Ident "UNKNOWN5" )
        <exp> : UNKNOWN6  (
          <val>  : int "UNKNOWN7" ) )
    <next> : Nonempty_Declaration_List  (
      <it> : UNKNOWN8  (
        <type> : UNKNOWN9  ( )
        <variable> : UNKNOWN10  (
          <ident>  : Ident "UNKNOWN11" )
        <exp> : UNKNOWN12  (
          <arg1> : UNKNOWN13  (
            <val>  : int "UNKNOWN14" )
          <op> : UNKNOWN15  ( )
          <arg2> : UNKNOWN16  (
            <val>  : int "UNKNOWN17" ) ) ) ) ) }
  <statement_nlist> : Statement_NList  {
    <first> : Nonempty_Statement_NList  (
      <it> : UNKNOWN18  (
        <variable> : UNKNOWN19  (
          <ident>  : Ident "UNKNOWN20" )
        <exp> : UNKNOWN21  (
          <val>  : int "UNKNOWN22" ) )
    <next> : Nonempty_Statement_NList  (
      <it> : UNKNOWN23  (
        <exp> : UNKNOWN24  (
          <ident>  : Ident "UNKNOWN25" )
        <block> : UNKNOWN26  (
          <declaration_list> : Declaration_List  { }
          <statement_nlist> : Statement_NList  {
            <first> : Nonempty_Statement_NList  (
              <it> : UNKNOWN27  (
                <variable> : UNKNOWN28  (
                  <ident>  : Ident "UNKNOWN29" )
                <exp> : UNKNOWN30  (
                  <ident>  : Ident "UNKNOWN31" ) )
		  ...

Find the UNKNOWNs.

Question 4
===========================================================

Question 4.1
5 points

For the following class dictionary:

Container = <contents> List(Item) Capacity <totalWeight> Weight.
Item : Simple | Container common <itemWeight> Weight.
Weight = <v> int.
Simple = .
Capacity = <v> int.
List(S) ~ {S}.

the Java compiler compiler complains:

Error: Left recursion detected: "_Container... 
--> _Item_List... --> _Nonempty_Item_List... 
--> _Item... --> _Container..."

Propose a simple way to eliminate this left recursion as well
as any other ambiguity problems with this class dictionary.

Question 4.2
5 points

Consider the class dictionary:

Container = "container" <contents> List(Item) Capacity <totalWeight> Weight.
Item : Simple | Container common <itemWeight> Weight.
Weight = <v> int.
Simple : Apple | Orange.
Apple = "an" "apple".
Orange = "an" "orange".
Capacity = <v> int.
List(S) ~ {S}.

This class dictionary has LL(1) problems. Repair them by making a
minimal number of changes that make the class dictionary LL(1).

Question 4.3
10 points

Consider the following class dictionary.

A = <bs> List(B).
B = <cs> List(C).
C = <ds> List(D).
D = "d".
List(S) ~ {S} .

It is ambiguous. Propose the simplest way to make this
class dictionary non-ambiguous, more specifically: LL(1).


Question 5:
============================================================
13 UNKNOWNs, 2 points per UNKNOWN: 26 UNKNOWNs
Class dictionary design

Design a class dictionary that accepts the following input
and similar inputs. Find the UNKNOWNs below.


{
  A /+/ B
  B / C
  C /+/ D bypassing -> A b B
  C /+/ E bypassing -> A b2 B
  C / F
  F /+/ G through -> X y Y
  G /+/ H bypassing -> A1 b2 B2
  H / J
  J /+/ *
}


Graph = List(UNKNOWN1) EOF.
UNKNOWN2 = <source> UNKNOWN3 Op <target> UNKNOWN4 [Constraint].
Op : UNKNOWN5.
Flexible = "/+/".
Strict = UNKNOWN6.
V : VertexName | Star.
Star = UNKNOWN7.
Constraint : UNKNOWN8 | UNKNOWN9 common UNKNOWN10.
Positive = "through" .
Negative = "bypassing" .
Triple = UNKNOWN11 <source> VertexName LabelName <target> VertexName.
LabelName = Ident.

List(S) ~ "UNKNOWN12" {S} "UNKNOWN13".
VertexName = Ident.