1. Why are character classes used, rather than individual characters, for the letter and digit transitions of a state diagram for a lexical analyzer?

There would be many more transitions required if individual characters were used (52 vs 1 for letter; 10 vs 1 for digit). It makes more sense to simply categorize them.

2. What are the two distinct goals of syntax analysis?

Syntax checking (correctness of program structure); Create a parse tree (some representation suitable for translation)

3. Describe the recursive-descent parser

Collection of subprograms -- each of which correctly identify (or reject) whether a sentence is a valid grammar. At most only one token is used for lookahead. Without it, the parser would not be able to recover.

4. Show a trace of the recursive descent parser expr grammar given in lab 3 for the string "a+b*c"

expr
|
+-> term
|   |
|   +-> factor
|       |
|       +-> var
|           |
|           +-> 'a'
|
+-> '+'
|
+-> term
    |
    +-> factor
    |   |
    |   +-> var
    |       |
    |       +-> 'b'
    |
    +-> '*'
    |
    +-> factor
        |
        +-> var
            |
            +-> 'c'

5. Write an EBNF rule that describes the for statement of Java or C++. Write the recursive-descent subprogram in OCaml or C. Assume that each part of the "head" is an expr

<for> ->  'f' '(' <expr> ';' <expr> ';' <expr> ')' '{' { <expr> ';'} '}'

OCaml:
----------

let rec for_loop s =
  let s = expect 'f' s in
  let s = expr (expect '(' s) in
  let s = expr (expect ';' s) in
  let s = expr (expect ';' s) in
  let s = expect '{' (expect ')' s) in
  let rec for_loop_helper s =
    if is_valid (accept '}' s) then
      accept '}' s
    else
      for_loop_helper (expect ';' (expr s))
  in for_loop_helper s;;

C:
----------

if (accept('f')) {
  expect('(');
  expr();
  expect(';');
  expr();
  expect(';');
  expr();
  expect(')');
  expect('{');
  while (true) {
    if (accept('}') {
      break;
    }
    expr();
    expect(';');
  }
}

6.  What is a reserved word?

A word that has a set meaning and cannot be redefined by the user. A reserved word also cannot be used in any way
other than whatever the rules for that reserved word dictate.

7. How can a variable be characterized?d

Name - named/not-named
Address - memory cell association
Type - determines data range and operations
Value - contents of memory cell
Lifetime - time bound to memory cell
Scope - range of statements which it is visible

8. After language design and implementation, when are the four times bindings can take place in a program?

Compile time: variable to type in C++/Java
Load time:    static variable to memory cell in C/C++
Runtime:      array access
Link time:    call to library subprogram

9. What is the lifetime of a variable?

The time during which it is bound to a particular memory cell

10. Assume the following JavaScript program was interpreted using static-scoping rules. What value of x is displayed in function sub1? Under dynamic-scoping rules, what value of x is displayed in function sub1?

Static: x = 5
Dynamic: x = 10

11. Consider the following C program and for each of the four marked points in this function, list each visible variable, along with the number of the definition statement that defines it.

1 - Visible: a, b, c, d
    a = definition 1
    b, c, d = definition 2

2 - Visible: a, b, c, d, e
    a = definition 1
    b = definition 2
    c, d, e = definition 3

3 - Visible: a, b, c, d
    a = definition 1
    b, c, d = definition 2

4 - Visible: a, b, c
    a, b, c = definition 1