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. Where precisely is a variable reduced?   Line 3 and 1
    
4. Where precisely is a function body reduced? Line 14 - val3(Body, (Formal, ...

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>