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

Please write your Name, Student ID, and Section at the top of the page.
  1. [Points 1] What is the typical function of a compiler (circle only one answer, please)

    1. takes a program (represented as a parse tree) and executes it
    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

  2. [Points 1] What is the purpose of the environment in an interpreter (circle only one answer, please)

    1. it provides the list of identifiers that are valid in the grammar
    2. it keeps the value of previous (sub)expressions
    3. it keeps the pointer to the parse tree
    4. it maintains the associations between identifiers and their values
    5. it tells the interpreter what are the resources available in the machine

  3. [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 x = x + 2 in x end       Not derivable
    2. let x = 1 in y end       Derivable
    3. let x = 1 in x end + let y = x in y end       Not derivable (declaration y = x is not allowed)
    4. let x = 1 + y = 2 in x + y end       Not derivable

  4. [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 let y = 2 in x + y end end       3
    2. let x = 1 in let x = 2 in x end + x end       3
    3. let x = 1 in x end + let x = 2 in x end       3
    4. let x = 1 in let y = 2 in let x = 3 in x + y end end end       5