I. Review for the midterm exam
 A. VMs
------------------------------------------
          FOR YOU TO DO

What happens to a VM's PC register
if no halt (HLT) instruction is executed?

a. The VM notices that the program is
   done and halts.

b. The VM interprets each address
   as an instruction,
   and keeps adding 1 to the PC.

c. The VM stops when the PC reaches
   program's last instruction.

d. The VM is not supposed to stop,
   so it issues an error message when
   the PC reaches the program's last
   instruction.


------------------------------------------
------------------------------------------
           FOR YOU TO DO

What is a lexical address?

 a. A page number in a dictionary
 b. A pair of a numbers, (scopes, offset),
    giving the address of a name,
    where scopes = number of static links
                   to follow
          offset = word address in that AR
 d. An absolute address in the VM's memory
    for a variable (or constant).
 c. A pair of strings, (name, scope)
    where name = the identifier
          scope = the AR holding that name

------------------------------------------
------------------------------------------
            FOR YOU TO DO

Consider the following PL/0 program

  const bl = 32, nl = 10;
  var q, r, s, t;
  procedure F;
    var x, y, z;
    begin
      read y; # asking about y here
      q := y
    end;
  procedure G;
    read q;
  begin   # asking about q here
    read q;
    write q
  end.

For a word-addressed VM:
-What is the lexical address of the
 variable "q" at the point
 of the second comment?
  a. (0,0)
  b. (1,1)
  c. (0,2)
  d. (2,3)

-What is the lexical address of "y" at
 the point indicated by the first comment?
  e. (0,1)
  f. (1,1)
  g. (0,7)
  h. (0,0)
  
------------------------------------------
 B. Grammars and Parsing
------------------------------------------
         FOR YOU TO DO

How many statement ASTs represent
all of the following PL/0 code fragment?

    begin
      x := 1;
      y := x+2;
      z := 3*4+y-x;
      if odd z then x := 0 else y := 0
    end

1. one (1)
2. two (2)
3. three (3)
4. four (4)

------------------------------------------
------------------------------------------
              FOR YOU TO DO

Is the following a legal PL/0 statement
(true or false)?

    begin
      x := 1;
      y := x+2;
      z := 3*4+y-x;
    end

Which tokens are included in the above
PL/0 code? (choose all that apply):

  a. identsym "y"
  b. numbersym 4
  c. beginsym "begin"
  d. identsym "end"
  e. becomessym ":="
  f. semisym ";"
  g. lparensym "("
  h. rparensym ")"
  i. leqsym "<="
  
------------------------------------------
  1. lexical analysis and regular grammars
------------------------------------------
          FOR YOU TO DO

What are the tokens for the following
grammar?

<program> ::= { <def> } <exp>
<def> ::= ( define <ident> <exp> )
<exp> ::= <number> | <ident>
        | ( quote <ident> )
        | ( <exp> { <exp> } )
        | ( if <exp> <exp> <exp> )
where
  <number> ::= <digit> { <digit> }
  <ident> ::= <letter>
              { <letter-or-digit> }
  <letter> ::= a | b | c | ... | y | z
             | A | B | C | ... | Y | Z
             | + | - | * | / | = | ?



------------------------------------------
------------------------------------------
            FOR YOU TO DO

Consider C-style comments: /* ... */
in a lexical analyzer

What would be a regular expression for
such comments?




What would a regular grammar look like?








What would a DFA look like?














------------------------------------------
 C. parsing
------------------------------------------
          FOR YOU TO DO

Briefly describe how an AST differs from
a parse tree.







------------------------------------------
------------------------------------------
            FOR YOU TO DO

Given this grammar:

<program> ::= { <def> } <exp>
<def> ::= ( define <ident> <exp> )
<exp> ::= <number> | <ident>
        | ( quote <ident> )
        | ( <exp> { <exp> } )
        | ( if <exp> <exp> <exp> )
where
  <number> ::= <digit> { <digit> }
  <ident> ::= <letter>
              { <letter-or-digit> }
  <letter> ::= a | b | c | ... | y | z
             | A | B | C | ... | Y | Z
             | + | - | * | / | = | ?

Write a leftmost derivation for the string

   (if (eq? x (quote y)) 3 (+ y 2))

or explain why that is not possible.

As an example:
   )(
is not in the language of this grammar.

















------------------------------------------
------------------------------------------
           FOR YOU TO DO

Write a suitable abstract syntax
for the following concrete syntax

<func> ::= function <type> <ident>
               ( <params> )
               <expr>
<type> ::= ...
<params> ::= <empty> | <param> {, <param>}
<param> ::= <ident> : <type>
<expr> ::= <ident> | ...









------------------------------------------
------------------------------------------
          FOR YOU TO DO
          
What would be a suitable C typedef for
AST for a language that includes <func>?




















------------------------------------------
 D. static analysis
------------------------------------------
          FOR YOU TO DO

What kind of errors are checked for
during declaration checking?








------------------------------------------
II. more review
 A. static analysis
------------------------------------------
           FOR YOU TO DO

Besides declaration checking,
what other kinds of checking of PL/0
programs should be done statically?




------------------------------------------
 B. systems software
------------------------------------------
             FOR YOU TO DO

What does a compiler do overall?

 a. It compiles things
 b. It translates things from one language
     to another
 c. It lists many error messages
 d. First it does lexical analysis,
     then parsing, then static analysis,
     then code generation.
     
------------------------------------------
  1. VMs and processors
------------------------------------------
            FOR YOU TO DO

How does a jump (JMP) instruction affect
the PC in a VM

 a. It replaces the address in the PC
     with an address from the instruction
 b. It causes the PC to
     rise above the floor
 c. It replaces the address in the PC
     with an address from the instruction
     which is then incremented by 1.
 d. The VM's PC is unaffected by such an
     instruction.

------------------------------------------
  2. Support for subroutines
------------------------------------------
           FOR YOU TO DO

Which of the following best describes
"static scoping"?

 a. A rule that keeps telescopes hidden
     in C program files
 b. A rule that makes each variable name
     refer to the most recent declaration
     of that name during a program's
     execution
 c. A rule that says what declarations
     a static variable in a C program
     refers to.
 d. A rule that makes each name refer to
     the closest textually surrounding
     declaration of that name.
     
------------------------------------------
------------------------------------------
           FOR YOU TO DO

Which of the following best describes
"dynamic scoping"?

 a. A rule that keeps telescopes
     constantly flying on airplanes.
 b. A rule that makes each variable name
     refer to the most recent declaration
     of that name during a program's
     execution
 c. A rule that says what declarations
     a static variable in a C program
     refers to.
 d. A rule that makes each name refer to
     the closest textually surrounding
     declaration of that name.
     
------------------------------------------
------------------------------------------
           FOR YOU TO DO

Why is static scoping useful for
programming?

 a. Because static scoping is used in
     the Unix shell.
 b. Because static scoping is easier to
     implement than dynamic scoping.
 c. Because static scoping makes names
     used in code refer to declarations
     that are evident in the program text.
 d. Because static scoping requires
     static links to be used when
     accessing local variables declared
     in surrounding scopes.

------------------------------------------
------------------------------------------
            FOR YOU TO DO

What are static links used for in a VM?

 a. To make a static fence
 b. To follow static scoping
 c. To create a static URL
 d. To ensure that each variable refers
     to the most recent declaration
     for that variable's name


------------------------------------------
------------------------------------------
          FOR YOU TO DO

How are static links used with lexical
addresses in VM?

 a. The first component of a lexical
     address indicates how many static
     links to traverse.
 b. The second component of a lexical
     address indicates how many static
     links to traverse.
 c. The first component of a lexical
     address indicates how many pairs of
     static and dynamic links to traverse.
 d. The second component of a lexical
     address indicates how many pairs of
     static and dynamic links to traverse.
------------------------------------------
 C. parsing
------------------------------------------
           FOR YOU TO DO

What parts of the grammar of PL/0 could
NOT be parsed using regular expressions?

 a. Matching parentheses and begin-end
 b. Recognizing numeric literals like 3402
 c. Recognizing reserved words
 d. Recognizing multiple-character tokens
     like ":=" and "<="
     

Could we write a parser for PL/0
without using a stack or recursion?

 a. no
 b. yes


------------------------------------------
------------------------------------------
            FOR YOU TO DO

In EBNF notation, what does ::= mean?

 a. These two things are equal.
 b. The left side is proportional to
     the right side.
 c. The left side can become
     the right side.
 d. The left side can jump to
     the right side.


In BNF notation, what does | mean?

 a. It means "or";
     it separates alternatives
 b. It means "and";
     it separates consecutive terms
 c. It means nothing, it is just used
     to make the formatting look better
 d. It means that parsing stops at that
     point
     

------------------------------------------
------------------------------------------
             FOR YOU TO DO

Consider the following grammar
in EBNF notation:

 <program> ::= { <rule> }
 <rule> ::= <term> :- <term>
                     { <sep> <term> } .
 <term> ::= <factor>
          | <factor>
                  ( <term> { , <term> } )
 <factor> ::= <var> | <atom>
 <var> ::= <CapitalizedIdent>
 <atom> ::= <lowercase-ident>
 <sep> ::= , | ;
   where
    <var> ::= <CapitalLetter> { <letter> }
    <atom> ::= <lowercaseletter>
                    { <letter> }
    <CapitalLetter> ::= A | B | ... | Z
    <lowercaseletter> ::= a | b | ... | z
    <letter> ::= <CapitalLetter>
               | <lowercaseletter>

Is the following a legal program?

   Practice :- true.

Is the following legal?

   ancestor(A,C) :- parent(B,C),
                    ancestor(A,B).
   ancestor(C,C).
------------------------------------------
        What would it take to fix it, if necessary?
------------------------------------------
             FOR YOU TO DO

What is an AST?

 a. The Association of
     Surgical Technologists
 b. Aspartate Transferase
 c. An Allocated Syntax Tree
 d. An Abstract Syntax Tree

------------------------------------------
 D. symbol tables
------------------------------------------
              FOR YOU TO DO

What is a symbol table used for
in a compiler?

 a. It tracks the metaphors
     that are compiled
 b. It stores information about
     identifiers
 c. It attributes meaning to identifiers
 d. It represents the deep meaning of
     each identifier
     
------------------------------------------
------------------------------------------
            FOR YOU TO DO

Which kind of information is NOT
something that a compiler should store
in its symbol table.

 a. The type of an identifier
 b. The age of a symbol
 c. The number of hit movies that the
     symbol has made
 d. The deeper meaning of the symbol
 
------------------------------------------
------------------------------------------
             FOR YOU TO DO

Assume that there is a global variable
  tok, of type token
with a field named typ of type token_type
and that the type token_type is an enum
that includes:
  identsym, definesym, numbersym,
  quotesym, eofsym, lparensym, rparensym
and that there is a global function
  eat(token t), that:
     issues an error message if tok != t,
     and advances to the next token
        by executing   tok = lexer_next();
and that there are functions
  parseNumber(), parseIdentExp(), and
  parseExp()
that parse the nonterminals <number>,
  <ident>, and <exp>

Write the code in C for a 
recursive descent parser that recognizes
the following EBNF grammar. (Note: you
don't have to build ASTs for this.)

 <program> ::= <form> { <form> }
 <form> ::= <number> | <ident>
          | <left> <s-cont> )
 <left> ::= (
 <form-cont> ::= quote <ident>
               | define <ident> <exp>
               | <exp> { <exp> }

































------------------------------------------
------------------------------------------
        FOR YOU TO DO

What should be done to change
a parser that just recognizes a language
into one that returns ASTs?

 a. Send it to the Mayo Clinic for a
    liver test.
 b. Change the void return types to return
    the type AST*, build and return an AST
    in each parsing function.
 c. Change the void return types to return
    the type AST* and return NULL in each
    parsing function.
 d. Build the symbol table during the
    traversal and look for duplicate
    and missing declarations for idents.
    
------------------------------------------
------------------------------------------
         FOR YOU TO DO

What would a suitable abstract syntax be
for the grammar:

 <program> ::= { <form> }
 <form> ::= <number> | <ident>
          | <left> <s-cont> )
 <left> ::= (
 <form-cont> ::= quote <ident>
               | define <ident> <exp>
               | <exp> { <exp> }










What would a suitable AST type be for
the above grammar?











------------------------------------------
------------------------------------------
        FOR YOU TO DO

Write, in C, a parser that returns ASTs
for the above grammar












































------------------------------------------