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

(/,\)

$(/,/)$

($(\,/)$)

$(\,/)$

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

  2. Give the AST for:

    image

  3. Traverse the AST in post order to produce the RPN.

  4. Give the result of evaluating the RPN.

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

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

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

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

  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:

    Exp1:

    Exp2:

    Context:

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

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

  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

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 Ans

    <rule1> <a/> </rule1>

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

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

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

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

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

  2. For the following grammar:

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

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

  3. Circle and label as 1, 2, …​ the scoping levels on the following:

    void a()
    { int N;
    	void b()
    	{ N = 2;
    		C(5.8);
    	}
    
    	void c(
    		float val)
    	{ cout << val;
    	  cout << N
    	}
    
    	N = 1;
    	b();
    }
  4. Static nesting level of definition:

    1. N:

    2. b:

    3. c:

    4. val:

  5. Static distance of identifiers at the given lines:

    1. Line 12, N

    2. Line 10, N

    3. Line 9, val

  6. Fill in stack information below through line 10 execution

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

    Static Activation Worksheet