C311 Test 3

Use the following pure BNF grammar rules to answer Question 0 and 1.

<zigzag> ::= (<zag> , <zig>) | (<zig> , <zag>) | <wag>

<wag> ::= <zig> | <zag> | $<zigzag>$

<zag> ::= \

<zig> ::= /

0.  For each of the strings listed below, indicate all the syntactic categories of which it is a member, if any:

Examples:     \ is a <zag>, a <wag> and a <zigzag>.    

           \\ is not a member.

A. (/,\)     <zigzag>    

B. $(/,/)$        None     

C. ($(\,/)$)      None     

D. $(\,/)$       <wag>   <zigzag>  

1a. Give the full parse tree as a <zigzag> for: $(/,\)$

                  <zigzag>
                      |
                    <wag>
                      |
                 $ <zigzag> $
                    /     \
               ( <zig> , <zag> )
                   |       |
                  '/'     '\'

1b. Give the AST for: 



                        +
                      /    \
                     -       4
                  /    \
                 1      *
                       /   \
                      2     3
 

1c. Traverse the AST in post-order to produce the RPN.

    1 2 3 * - 4 +

1d. Give result of evaluating the RPN.

2. Give complete pure or extended BNF rules necessary to define basic Indiana license plate numbers.  The arrangement is one or two characters 1-92, followed by A-Z, followed by 1-9999.

    Examples: 10A2003 
                      22B1002
                        2B4
 
    <digit1-9> ::= 1 | 2 | ... | 9
    <digit0-9> ::= 0 | <digit1-9>
    <alpha>    ::= A | B | ... | Z
    <plate>     ::= ((<digit1-9> <digit0-9>) | <digit1-9>))
                            <alpha>
                            ( (<digit1-9> <digit0-9> <digit0-9> <digit0-9>)| (<digit1-9> <digit0-9> <digit0-9>) | (<digit1-9> <digit0-9>) | <digit1-9>))

3.    Use the following Language Three interpreter

1. List the line numbers in order executed by the following:
   
   val3( Plus(Var "z", Const 2), [("z", Const 3)]);
   
   5, 3, 1, 2, 4
   
2. List the line numbers in order executed by the following:
   
   val3( Apply( Fn("z",
                    Plus(Var "z", Const 2)),
                Const 3),
         []);
   
     13-14, 2, 5, 3, 1, 2, 4
    
3. What are V, Exp1, Exp2 and Context at Line 9 of val3 for the following?
   
   val3(Let(“Z”, Var “X”, Plus(Var “Z”, Var “Y”)), [(“X”,Const 2),(“X”,Const 3),(“Y”,Const 4)]);
   
   V "Z"                                        Exp1 __Var "X"_
   
   Exp2 __Plus(Var “Z”, Var “Y”)__    Context  [(“X”,Const 2),(“X”,Const 3),(“Y”,Const 4)]
    
4. Result of the following val3 call?
   
   val3( Times(Times(Const 4, Var “x”), Var “y”), [(“x”,Const 3),(“y”,Const 5),(“x”,Const 6)]);

          Const 60

 e. Result of the following val3 call?
 

    val3(Let(“f”,

            Fn(“X”, Times(Var “X”, Var “Y”)),

                Apply( Var “f”, Const 5)), [(“X”,Const 2),(“Y”,Const 3)]);

      Const 15    

 f. Give ML statement(s) to extend val3 to implement Inc, the increment operator. Examples:

    val3(Inc(Const 2), [(“Z”,Const 2)]); returns Const 3
    val3(Inc(Inc(Var “Z)), [(“Z”,Const 2)]); returns Const 4

    val3( Inc (Const x), _ ) = Const(x+1);

    val3( Inc (E), Context) = val3( Inc ( val3( E, Context)), Context);
 

4. Compute wp for the following:

1. y := x + 7; {y > 3} 
   
   {x > -4} y := x + 7; {y > 3}
    
2. x := x - y; {x > 4}
   
   {x > y+4} x := x - y; {x > 4}
    
3. y := x + 7; 
   x := y - 5; {x > 4}
   
   {x > 2} y := x + 7; {y > 9}
   {y > 9} x := y - 5; {x > 4}
    
4. if (x<5) then y:=y-7 else y:=y+8 {y > 10}

    {y > 17}
    if (x<5) then
         {y > 17} y:=y-7 {y > 10}
    else {y > 2 } y:=y+8 {y > 10}

5. Given the following DTD rules:

<!ELEMENT rule1 (a,b)>
<!ELEMENT rule2 ((a | b), b)>
<!ELEMENT rule3 (a*,b+)>
<!ELEMENT rule4 ((rule4, b) | b)>
<!ELEMENT rule5 (b+)>
<!ELEMENT a EMPTY>
<!ELEMENT b EMPTY>

    Which of the following are valid under the rules?

• NO  <rule1> <a/> </rule1>
• NO  <rule2> <b/> <a/> </rule2>
• YES <rule3> <a/> <b/> <b/> </rule3>
• NO  <rule4> <b/> <b/> <b/> </rule4>
• YES <rule4> <rule4> <rule4><b/></rule4> <b/></rule4> <b/> </rule4>
• YES <rule5> <b/> <b/> <b/> </rule5>

    Give the parse tree.
 

• <rule1> <a/> </b> </rule1>
  
               <rule1>
                /      \
            <a>     <b>
   
• <rule3> <b/> <b/> </rule3>
  
               <rule3>
                /      \
            <b>     <b>
   
• <rule4> <rule4> <rule4><b/></rule4> <b/></rule4> <b/></rule4>

                     <rule4>
                      /      \
               <rule4>   <b>
               /        \
        <rule4>   <b>
             |
          <b>

6. Add a rule for a right-associative operator % with precedence between $ and &.

    <e> ::= <e> $ <m> | <m>
    <m> ::= <m> & <r> | <r>
    <r> ::= ( <e> ) | 1 | 2 | 3 | 4

    <e> ::= <e> $ <new> | <new>
    <new> ::= <m> % <new> | <m>
    <m> ::= <m> & <r> | <r>
    <r> ::= ( <e> ) | 1 | 2 | 3 | 4