Main Topics, Based on Recitations:

• Overview:
  • Compiler overview.
    Contrasts:
    • syntax versus semantics,
    • run-time versus compile-time,
    • translation versus interpretation.
  • Overview diagram.

• Initial work on languages and on translating them:
  • Simple example: translating a program with gotos into one without. In any "normal" programming language, it is always possible to do such translation.
    Recitation 1. No goto.

• Scanners and the Use of Automata:
  • Online discussion of Finite State Machines: finite state machines.
  • Constructing a scanner based on a Finite State Machine (using either gotos or a while loop and select based on a state variable).
  • Practical example: the FSM for C-style comments, and the construction of a scanner for these comments:  comments.
  • Practical example: the FSM for floating point constants, and the construction of a scanner for these constants:
    Recitation 2. Lexical Analysis and FSMs.
  • Extended example: a scanner for tokens, including floating point constants, comments, identifiers, and single character tokens. Programming this scanner, including a symbol table:
    Recitation 3: Scanner.

• Formal Grammars and Languages:
  • Brief online material about formal grammars: Formal (CF) grammars.
  • Definition of formal grammar, also called a context-free grammar or a BNF grammar.
  • Terms to know: start symbol, terminal symbols, non-terminal symbols, grammar rules (also called replacement rules), metasymbols.
  • Replacement sequences (also called Derivation sequences): leftmost and rightmost.
  • Language which is accepted by (or recognized by) a formal grammar. In general there are many different grammars that define the same language.
  • Parse trees. Depends on a specific replacement sequence, which in turn depends on the grammar. Change the grammar, even in the language stays the same, and you'll change the parse trees. Each replacement sequence determines a unique parse tree, but a parse tree might have many replacement sequences.
  • Ambiguity. Definition: If there is a sentence with more than one parse tree, or with more than one leftmost derivation, or with more than one rightmost derivation.
    • Ambiguity is bad.
    • Remove ambiguity by either:
      • rewriting the grammar, keeping the language the same, such as changing

        
           E  ---->  E + E       (AMBIGUOUS)
           E  ---->  E * E
           E  ---->  ( E )
           E  ---->  id

        to

        
           E  ---->  E + T       (NOT AMBIGUOUS)
           E  ---->  T
           T  ---->  T * F
           T  ---->  F
           F  ---->  ( E )
           F  ---->  id

      • introducing special rules, such as
        • Precedence of one operator over another. (Present with + and * in the first example above.)
        • Associativity of an operator (left-to right or right-to-left). (Present with both + and * in the first example above.)
        • Rule that an else matches then nearest unmatched if. (Present in the following example:

          
             stmt  ---->  "if" "(" expr ")" stat               (AMBIGUOUS)
             stmt  ---->  "if" "(" expr ")" stat "else" stat
          

  • Practice with formal grammars:
    Recitation 4. Formal Grammars

• Parsers and the Use of Grammars:
  • Simple Shift-Reduce Parsers:
    • A simple version of more powerful methods often used in real compilers. These more powerful methods don't require the grammar to be rewritten as often as recursive descent does.
    • Carries out the parse working backwards from an initial sentence to the start symbol. Constructs a rightmost derivation backwards.
    • Uses a stack for symbols. Input symbols are always (eventually) shifted onto the stack, but in some circumstances a string of one or more symbols (mixed terminals or non-terminals) might be "reduced", that is, matched with the right side of a grammar rule that is used for backwards replacement on the stack by the single non-terminal on the left side of the rule.
    • Whether to shift or reduce is controlled by a table which says what to do based on the symbol on the top of the stack and on the "current" symbol. (The more powerful parsers use similar but more complicated methods.)
    • Work with a simple shift-reduce parser: SR Parser Worksheet.
  • Recursive Descent Parsers: Recursive descent parsing
    • Top-down parser, starts with the start symbol and works down toward the given sentence (string of terminal symbols), constructing a leftmost derivation.
    • Must rewrite grammar to avoid left recursion. (There are other possible problems also, beyond the scope of this course.) The simple grammar above would be rewritten:

      
         E  ---->  T { "+" T }          ({} means "zero of more times")
         T  ---->  F { "*" F }          (terminals are in quotes or id)
         F  ---->  "(" E ")"
         F  ---->  id
      

    • Write a function corresponding to each non-terminal symbol in the grammar. The code of the function mirrors the right side of the rule.
    • Simple examples for
      • simple arithmetic expressions,
      • Lisp S-expressions.
    • Parser for the Tiny^TM language, used in the next and following two recitations:
      Recitation 5. Recursive descent parsing.

• Use of Parsers to Carry Out Translation or Other Tasks: Syntax directed translation
  • Add extra code (semantic actions) to the parser, either
    • In with the code of the functions representing each non-terminal in recursive descent.
    • Code attached to each grammar rule in shift-reduce. The code is executed each time a rule is used in a reduction.
  • Two examples based on recursive descent parser of arithmetic expressions:
    • Translate to RPN (in C),    C source.
    • Translate to RPN (in Java)    Java source.
    • Evaluator for arithmetic expressions    C source.
  • Initial translator of assignment statements and arithmetic epxressions to MIPS code:
    Recitation 6. Initial translator.
  • Final translator to MIPS code that adds while and if-then-else statements:
    Recitation 7. while and if-then-else.

• Run-time storage administration:
  • Write-up about run-time storage administration: Run-time storage.
  • Topics:
    • Static storage, as in Fortran (originally), and for variables declared static.
    • Stack-based storage. Used for function implementation. A function's activation record holds all the storage an information needed by a given active instance of a function (with recursive calls there may be several active instances of any given function). See the example: dangle example
  • Heap-based storage and dynamic allocation. Topics here include garbage and garbabe collection, memory leaks, and active pointers to garbage.
  • One recitation so far that illustrates the run-time stack (on-time due date before exam):
    Recitation 8. Runtime storage.

• See the previous mid-term exams for sample questions (though be aware that this exam may be considerably different, even covering some different topics):
  • Fall 2004 Exam (Answers).
  • Spring 2004 Exam
  • Fall 2003 Exam (Answers).
  • Spring 2003 Exam.
  • Fall 2002 Exam (Answers).
  • Spring 2002 Exam (Answers).
  • Fall 2001 Exam (Answers).
  • Spring 2001 Exam (Answers).

• All the above topics are important, but there is emphasis on:
  • Scanners and tokens. The role of FSMs.
  • Formal grammars. (Definitions, replacement sequences, parse trees, ambiguity, extended notations.)
  • Parsers. (Bottom-up: shift-reduce, top-down: recursive descent, making a grammar suitable for recursive descent, actually writing a recursive-descent parser, including when to scan.)
  • Syntax-directed translation. (The use of a parser to carry out a task such as translation, by adding code to the "bare" parser.)
  • The specific course compiler project: implementing the Tiny^TM language in Recitations 5, 6, and 7.
  • Run-time storage administration. (Static storage. auto storage. Use of a stack for function activation records and local auto storage.)