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.

  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