Test 2 Review

Use the following BNF grammar rules for the following questions.

<zigzag> ::= (<zag> , <zig>) | (<zig> , <zag>) | <wag>
<wag> ::= <zig> | <zag> | $<zigzag>$
<zag> ::= \
<zig> ::= /
  1. For each of the following strings, indicate all syntactic categories of which it is a member, if any.

    Ex:  is a <zag>, a <wag>, and a <zigzag>

    Question Ans

    (/,\)

    <zigzag>

    $(/,/)$

    None

    ($(\,/)$)

    None

    $(\,/)$

    <wag> <zigzag>

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

    Answer
              <zigzag>
                  |
                <wag>
                  |
             $ <zigzag> $
                /     \
           ( <zig> , <zag> )
               |       |
              '/'     '\'
  3. Give the AST for:

    image

    Answer
                +
              /    \
             -       4
          /    \
         1      *
               /   \
              2     3
  4. Traverse the AST in post order to produce the RPN.

    Answer: 1 2 3 * - 4 +

  5. Give the result of evaluating the RPN.

    image

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

    Examples: 10A2003, 22B1002, 2B4
    Answer
        <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>))

Use the following Language Three interpreter:

1.  let rec lookup V L =
     let (var,value)::T = L in
      if V=var then value else lookup V T;;

2.  let rec val3 exp context = match exp with
3.    | Const x -> Const x
4.    | Var V -> lookup V context
5.    | Plus (Const x, Const y) -> Const (x+y)
6.    | Plus (x, y) -> val3 (Plus(val3 x context, val3 y context)) context
7.    | Times (Const x, Const y) -> Const (x*y)
8.    | Times (x, y) -> val3 (Times(val3 x context, val3 y context)) context
9.    | Let (V, exp1, exp2) -> val3 exp2 ((V, val3 exp1 context)::context)
10.   | Fn (formal, body) -> Fn(formal, body)
11.   | Apply (Fn(formal, body), actual) -> val3 body ((formal, val3 actual context)::context)
12.   | Apply (Var v, actual) -> val3 (Apply (val3 (Var v) context, actual)) context;;
  1. List the line numbers executed by the following:

    val3 (Plus (Var "z"), Const 2) [("z", Const 3)];;

    Answer: 6, 4, 1, 3, 5

  2. List the line numbers in order executed by the following:

    val3 (Apply (Fn ("z", Plus (Var "z", Const 2)), Const 3)) [];;

    Answer: 11, 3, 6, 4, 1, 3, 5

  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)];;

    Table 1. Answer

    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)]

    Answer: Const 60

  5. 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)]

    Answer: Const 15

  6. Give the F# statement(s) to extend val3 to implement Inc, the increment operator. Examples:

    • val3 (Inc (Const 2))[];; Returns Const 3

    • val3 (Inc (Inc (Var "Z"))) [("Z", Const 2)] Returns Const 4

      Answer

| inc Const x -> Const(x+1)
| Inc E -> val3 (Inc (val3 E context)) context

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>
  1. Which of the following are valid under the rules?

    Rule Answer

    <rule1> <a/> </rule1>

    NO

    <rule2> <b/> <a/> </rule2>

    NO

    <rule3> <a/> <b/> <b/> </rule3>

    YES

    <rule4> <b/> <b/> <b/> </rule4>

    NO

    <rule4> <rule4> <rule4><b/></rule4> <b/></rule4> <b/> </rule4>

    YES

    <rule5> <b/> <b/> <b/> </rule5>

    YES

For the following grammar:

    <e> ::= <e> $ <m> | <m>
    <m> ::= <m> & <r> | <r>
    <r> ::= ( <e> ) | 1 | 2 | 3 | 4
  1. Add a rule for a right-associative operator % with precedence between $ and &.

    Ans:
        <e> ::= <e> $ <new> | <new>
        <new> ::= <m> % <new> | <m>
        <m> ::= <m> & <r> | <r>
        <r> ::= ( <e> ) | 1 | 2 | 3 | 4
  2. Circle and label as 1, 2, …​ the scoping levels on the following:

    image

  3. Static nesting level of definition:

    1. N 1

    2. b 1

    3. c 1

    4. val 2

  4. Static distance of identifiers at the given lines:

    1. Line 12, N: 0

    2. Line 10, N 1

    3. Line 9, val 0

  5. Fill in stack information below through line 10 execution

                 Stack    Address
             |           |428
             |           |427
             |           |426
             |           |425
             |           |424
             |           |423
             |           |422
             |           |421
             |           |428
             |           |427
             |           |426
      AR(c)  |    415    |425 SL
             |           |424 IP
             |    419    |423 DL
             |    5.8    |422 val
      AR(b)  |    415    |421 SL
             |    6      |420 IP
             |    415    |419 DL
      AR(a)  |    OS     |418 SL
             |    14     |417 IP
             |    OS     |416 DL
             | 1, **2**  |415 N
  6. Complete the following:

    image