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> ::= /

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 









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

Give the AST for:

Traverse the AST in post order to produce the RPN.

Give the result of evaluating the RPN.

Give complete pure or extended BNF rules necessary to define basic Indiana license plate numbers. The arrangement is one or two characters 199, followed by AZ, followed by 19999.
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;;

List the line numbers executed by the following:
val3 (Plus (Var "z"), Const 2) [("z", Const 3)];;

List the line numbers in order executed by the following:
val3 (Apply (Fn ("z", Plus (Var "z", Const 2)), Const 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:

Result of the following val3 call?
val3 (Times (Times (Const 4, Var "x"), Var "y")) [("x", Const 3); ("y", Const 5); ("x", Const 6)]

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

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>

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>

For the following grammar:
<e> ::= <e> $ <m>  <m> <m> ::= <m> & <r>  <r> <r> ::= ( <e> )  1  2  3  4
Add a rule for a rightassociative operator % with precedence between $ and &.

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(); }

Static nesting level of definition:

N:

b:

c:

val:


Static distance of identifiers at the given lines:

Line 12, N

Line 10, N

Line 9, val


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

Complete the following: