CSE 428: Quizzes

Spring 2001, CSE 428: Quiz 2.4 - 25 Jan 2001

Please write your Name, Student ID, and Section at the top of the page.

[Points 1] What is the typical function of an interpreter (circle only one answer, please)
1. takes a program (represented as a parse tree) and executes it (i.e. simulates its execution)
2. takes a list of tokens and produces a parse tree
3. translates the source code of a program into machine code
4. takes a program and produces a list of tokens
5. takes a grammar and produces all possible parse trees
[Points 1] How is the environment used by an interpreter (circle only one answer, please)
1. to check whether an identifier has been declared
2. to store the value of previous (sub)expressions
3. to store and retrieve the associations between identifiers and values
4. to check whether there is only one declaration for each identifier
5. to check what are the resources available in the machine
[Points 4] Consider the mini language of expressions seen in class, defined by the grammar
```
   Exp ::=  Num | Ide | Exp Op Exp | let Ide = Num in Exp end
   Op  ::=  + | * | - | /
```
where Num and Ide are defined as usual. For each of the following expressions, say whether or not they are derivable from this grammar. (Note: you are not requested to say whether an expression is "correct", but only whether it can be derived from the grammar.)
1. let x = 1 in let y = x + 2 in y end Not derivable
2. let x = 1 in y + x end Derivable
3. let x = 1 in x end + let y = 2 in x end Derivable
4. let x = 1 + let y = 2 in x + y end end Not derivable
[Points 4] Consider the same language as in previous question, and the interpreter seen in class for that language. For each of the following expressions, say what is the result of the evaluation.
1. let x = 1 in x + let y = 2 in x + y end end 4
2. let x = 2 in let x = 1 in x end + x end 3
3. let y = 2 in y end + let x = 2 in x end 4
4. let x = 3 in let y = 2 in let x = 1 in x + y end end end 3