Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CIs 505 > cis > Flashcards

cis Flashcards

1
Q

What should a store do?

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

A

map locations into values

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

To interpret an assignment L = R, we must

evaluate L to a
evaluate R to a

A

Location

value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What should an environment do?

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

A

map program variables into locations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

a store
an environment

A

a store

an environment

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the result of interpreting a command?

an updated environment
an updated store
a value

A

an updated store

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

never
when the expression is not pure
always

A

when the expression is not pure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

an interpreter?
a compiler?

A

possibly many times?

only once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does a lexical analysis

BOTH HAVE ANSWER
produce?
consume?

A

a list of tokens

a string of characters

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What does a parser
produce?
consume?

A

a syntax tree

a list of tokens

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

it will transition to NumberState 624, with no output

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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]

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

perhaps zero, perhaps one, perhaps more than one

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

at most one, perhaps zero

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q 
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

A

F TimesT F

F TimesT T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q 
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
::=

A

F TimesT F

T TimesT T

17
Q

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

A

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

18
Q

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

A

a list of tokens

19
Q

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

A

a list of tokens

a syntax tree

20
Q

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)

A

parFact (for parsing a factor)

parse (for parsing at top-level)

21
Q

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

A

they adhere to standard rules of arithmetic

they can be implemented by a bottom-up parser

22
Q

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

A

they can be implemented by a bottom-up parser

they can be easily implemented by a top-down parser

23
Q 
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

A

h (2 +7 )

5 * (g 7)

24
Q 
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

A

(5 + 3) * 4

25
Q

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

A

CBV evaluation of P does not terminate

CBV evaluation of P terminates with result 17

26
Q

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

A

CBN evaluation of P terminates with result 17

27
Q

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

A

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

28
Q 
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
A

y = 12, z = 7

29
Q

Match expressions with the result of evaluating them

(car ‘(5 . 7))

(cdr ‘(5 . 7))

(first ‘(5 . 7))

(rest ‘(5 . 7))

A

5

7

error

error

30
Q

Match expressions with the result of evaluating them

car ‘(5 7)
(cdr ‘(5 7))
(first ‘(5 7))
(rest ‘(5 7))

A 
(car '(5 7)) 
5
(cdr '(5 7)) 
'(7)
(first '(5 7)) 
5
(rest '(5 7)) 
'(7)
31
Q

?

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

A

4

32
Q

A closure contains (check all that applies)

a function body
a store
a formal parameter
an environment

A

a function body

a formal parameter
an environment

33
Q 
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:

A 
Answer 1:
x + w 
Answer 2:
w 
Answer 3:
x -> 7
34
Q 
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 ]
A 
Answer 1:
h (h y) 
Answer 2:
y 
Answer 3:
w + 2 
Answer 4:
w 
Answer 5:
empty
35
Q 
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

A

(lambda y B) E

CIs 505 (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions