cis

Question 1

What should a store do?

map program variables into locations
map locations into values
map program variables into values

Answer 1

map locations into values

Question 2

To interpret an assignment L = R, we must

evaluate L to a
evaluate R to a

Answer 2

Location

value

Question 3

What should an environment do?

map program variables into values
map program variables into locations
map locations into values

Answer 3

map program variables into locations

Question 4

What is needed to evaluate a command (check all that applies)

a store
an environment

Answer 4

a store

an environment

Question 5

What is the result of interpreting a command?

an updated environment
an updated store
a value

Answer 5

an updated store

Question 6

Interpreting an expression must return a value; when must it also return a changed store?

never
when the expression is not pure
always

Answer 6

when the expression is not pure

Question 7

For a given program, how often is each part of its abstract syntax tree examined by

an interpreter?
a compiler?

Answer 7

possibly many times?

only once

Question 8

What does a lexical analysis

BOTH HAVE ANSWER
produce?
consume?

Answer 8

a list of tokens

a string of characters

Question 9

What does a parser
produce?
consume?

Answer 9

a syntax tree

a list of tokens

Question 10

Consider the lexical analysis presented in the lecture notes. Assume it is in state NumberState 62, and that the next character is 4. What will then happen?

it will transition to NumberState 624, with no output

it will transition to InitState, and output the token NumT 624

it will transition to InitState, and output the token NumT 62

it will transition to NumberState 462, with no output

Answer 10

it will transition to NumberState 624, with no output

Question 11

Consider the lexical analysis presented in the lecture notes. Assume it is in state NumberState 62, and that the next character is +. What will then happen?

it will transition to InitState, output the token NumT 62, and advance the input pointer (skipping the + symbol)

it will stay in NumberState 62, and advance the input pointer (skipping the + symbol)

it will transition to InitState, output the token NumT 62, but not move the input pointer

Answer 11

it will transition to InitState, output the token NumT 62, but not move the input pointer

Question 12

Consider, as in the lecture notes, the grammar
::= NumT num
| OpenParenT CloseParenT
| PlusT
| MinusT
| TimesT
Which of the following token lists have at least two different parse trees?

[NumT 7, PlusT, NumT 3, PlusT, NumT 4]
[NumT 7, TimesT, NumT 3]
[NumT 7, PlusT, NumT 3]
[NumT 7, TimesT, NumT 3, PlusT, NumT 4]

Answer 12

[NumT 7, PlusT, NumT 3, PlusT, NumT 4]

[NumT 7, TimesT, NumT 3, PlusT, NumT 4]

Question 13

For a given (arbitrary) grammar, what can we say about the number of syntax trees for a given list of tokens?

perhaps zero, perhaps one, perhaps more than one

at least one, perhaps more

exactly one

at most one, perhaps zero

Answer 13

perhaps zero, perhaps one, perhaps more than one

Question 14

For a given unambiguous grammar, what can we say about the number of syntax trees for a given list of tokens?

at most one, perhaps zero

exactly one

at least one, perhaps more

perhaps zero, perhaps one,
perhaps more than one

Answer 14

at most one, perhaps zero

Question 15

Consider the (renamed) grammar from the notes:
   ::= 

   |   E PlusT T
   |   E MinusT T
   ::= 
      F
   |   T TimesT  F     (*)
   F ::=
       NumT nums
   |   OpenParenT E CloseParenT
and assume we replace the line marked (*). For which replacement(s) will the resulting grammar still be unambiguous?

F TimesT T
T TimesT T
F TimesT F

Answer 15

F TimesT F

F TimesT T

Question 16

Consider the (renamed) grammar from the notes:
   ::= 

   |   TimesT       (*)
   ::=
      NumT 
  |   OpenParenT  CloseParenT
and assume we replace the line marked (*). For which replacement(s) will the resulting grammar allow syntax trees for all token lists for which there is a syntax tree in the original grammar?

F TimesT T
T TimesT T
F TimesT F

PlusT
| MinusT
::=

Answer 16

F TimesT F

T TimesT T

Question 17

Consider the grammar
::=

   |   PlusT 
   |   MinusT 
   |   TimesT      
   ::=
      NumT 
  |   OpenParenT  CloseParenT
Which properties does it have (check all that apply)

allows a syntax tree for all token lists for which there is a syntax tree

in the grammar from the notes

addition and subtraction are both left-associative

multiplication has precedence over addition and subtraction

multiplication is left-associative

unambiguous

Answer 17

allows a syntax tree for all token lists for which there is a syntax tree

addition and subtraction are both left-associative

multiplication is left-associative

unambiguous

Question 18

What does a (top-down) parsing function expect as input (check all that apply)

a list of tokens
a string of characters
a syntax tree

Answer 18

a list of tokens

Question 19

What does a (top-down) parsing function return as output (check all that apply)

a list of tokens
a string of characters
a syntax tree

Answer 19

a list of tokens

a syntax tree

Question 20

For the top-down parser listed in the notes, which functions (check all that apply) may need to report an error (by raising an exception)?

parFact (for parsing a factor)
parse (for parsing at top-level)
parExp (for parsing an expression)
parTerm (for parsing a term)

Answer 20

parFact (for parsing a factor)

parse (for parsing at top-level)

Question 21

What is true (check all that apply) about grammars that make arithmetic operators left associative?

they adhere to standard rules of arithmetic
they can be implemented by a bottom-up parser
they can be easily implemented by a top-down parser

Answer 21

they adhere to standard rules of arithmetic

they can be implemented by a bottom-up parser

Question 22

What is true (check all that apply) about grammars that make arithmetic operators right associative?

they adhere to standard rules of arithmetic
they can be implemented by a bottom-up parser
they can be easily implemented by a top-down parser

Answer 22

they can be implemented by a bottom-up parser

they can be easily implemented by a top-down parser

Question 23

Consider the first-order program
   h z = 5 * z;   
   g y = 2 + y; 
  h (g 7)
With the substitution approach to evaluation, what will h (g 7) rewrite to in the first step, using 

Call-By-Value

Call-By-Name

Answer 23

h (2 +7 )

5 * (g 7)

Question 24

Consider the first-order program
   f z = z * 4;
   g y = y + 3;
  f (g 5)
With Call-By-Name evaluation, the first step is
  f (g 5) => (g 5) * 4
What is the result of the second step?

8 * 4
5 + 3 * 4
(5 + 3) * 4

Answer 24

(5 + 3) * 4

Question 25

Assume that for a given program P, CBN evaluation terminates with result 17. What is then possible? (check all that applies) CBV evaluation of P does not terminate CBV evaluation of P terminates with result 17 CBV evaluation of P terminates with result 27

Answer 25

CBV evaluation of P does not terminate | CBV evaluation of P terminates with result 17

Question 26

Assume that for a given program P, CBV evaluation terminates with result 17. What is then possible? (check all that applies) CBN evaluation of P terminates with result 27 CBN evaluation of P terminates with result 17 CBN evaluation of P does not terminate

Answer 26

CBN evaluation of P terminates with result 17

Question 27

Assume that for a given program P, CBN evaluates to 37 using n steps, and CBV evaluates to 37 using v steps. How may n and v relate? (check all that applies) n < v is possible n = v is possible n > v is possible

Answer 27

n < v is possible n = v is possible n > v is possible

Question 28

``` Consider the first-order program h z = g (5 + z); g y = 3 * y; h 7 Consider the environment approach to evaluation (using CBV), with dynamic scope. In which environment is the body of g, that is 3 * y, evaluated? ``` ``` y = 12, z = 7 z = 7 y = 12 y = 7, z = 7 y = 7 ```

Answer 28

y = 12, z = 7

Question 29

Match expressions with the result of evaluating them (car '(5 . 7)) (cdr '(5 . 7)) (first '(5 . 7)) (rest '(5 . 7))

Answer 29

5 7 error error

Question 30

Match expressions with the result of evaluating them | car '(5 7) (cdr '(5 7)) (first '(5 7)) (rest '(5 7))

Answer 30

``` (car '(5 7)) 5 (cdr '(5 7)) '(7) (first '(5 7)) 5 (rest '(5 7)) '(7) ```

Question 31

Assume we have the declarations ``` (struct Leaf (int)) (struct Binary (tree1 tree2)) (define (f t) (cond [(Leaf? t) (+ 1 (Leaf-int t))] [(Binary? t) (f (Binary-tree2 t))])) ``` Which number is the result of the call (f (Binary (Binary (Leaf 5) (Leaf 9)) (Binary (Leaf 7) (Leaf 3)))) #?

Answer 31

4

Question 32

A closure contains (check all that applies) a function body a store a formal parameter an environment

Answer 32

a function body a formal parameter an environment

Question 33

``` The result of evaluating (lambda x. lambda w. x + w) 7 is a closure with body: [ Select ] ``` formal parameter: [ Select ] environment: [ Select ] Answer 1: Answer 2: Answer 3:

Answer 33

``` Answer 1: x + w Answer 2: w Answer 3: x -> 7 ```

Question 34

``` The result of evaluating (lambda h. lambda y. h (h y)) applied to (lambda w.w + 2) is a closure with body: [ Select ] ``` formal parameter: [ Select ] and an environment that binds h to a closure with body: [ Select ] formal parameter: [ Select ] environment: [ Select ]

Answer 34

``` Answer 1: h (h y) Answer 2: y Answer 3: w + 2 Answer 4: w Answer 5: empty ```

Question 35

``` Which expression is evaluated in the same way as let y = E in B ``` E (lambda y B) B (lambda y E) (lambda y B) E (lambda y E) B

Answer 35

(lambda y B) E