CS 3723/3731 -- Review for Mid-Term Exam

CS 3723/3731 Programming Languages
Fall 2003 -- Review for Mid-Term Exam
Exam is Wednesday, 22 October 2003

Main Topics, Based on Recitations:

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:
- Constructing a scanner based on a DFA (using either gotos or a while loop and select based on a state variable).
- Practical example: the DFA for C-style comments, and the construction of a scanner for these comments.
- Practical example: the DFA for floating point constants, and the construction of a scanner for these constants:
  Recitation 2. Lexical Analysis and FSMs.
Formal Grammars and Languages:
- 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, metasymbols.
- Derivation sequences (leftmost and rightmost).
- Language which is accepted by (or recognized by) a formal grammar.
- Parse trees. (Each derivation sequence determines a unique parse tree, but a parse tree might have many derivations.)
- 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, 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 3. 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:
    Recitation 4. Shift reduce parsing.
- Recursive Descent Parsers:
  - 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, for 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:
- 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 for evaluator.
- 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.
Functions and arrays in C/C++/Java:
- Three handouts so far:
  Recitation 8.Functions and Arrays.
Run-time storage administration:
- One handout so far:
  Recitation 8. Runtime storage.
Other topics:
- Compiler overview.
- Contrasts:
  - syntax versus semantics,
  - run-time versus compile-time,
  - translation versus interpretation.

Most Important Topics and Sample Questions:

See the previous mid-term exams for sample questions (though be aware that this exam may be considerably different, even covering some different topics):
- 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:
- 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.)
- Run-time storage administration. (Use of a stack for function activation records and local storage. Use of the heap. Explicit allocation/deallocation. malloc and free in C: implementation. Automatic garbage collection.)

CS 3723/3731 Programming Languages Fall 2003 -- Review for Mid-Term Exam Exam is Wednesday, 22 October 2003

CS 3723/3731 Programming Languages
Fall 2003 -- Review for Mid-Term Exam
Exam is Wednesday, 22 October 2003