CS 375, Compilers: Study Guide for Midterm Exam

Date: Friday, August 1, 2008, in class.

Reading:

Material covered in class:

• Major phases of a compiler; what the phases do; data flow between phases.
• Formal definition of a grammar; chart about grammar classes.
• Regular languages: grammar definitions, uses; local ambiguity: examples, ways to handle. Relationship of finite automata and regular grammars; linear nature of a derivation from a regular grammar.
• Regular expressions: definition; be able to construct a regular expression for a language, or to construct the language denoted by a regular expression. Relation between regular expressions and finite automata; automatic construction of finite automata from regular expressions.
• Lexical analyzer: what constructs are parsed; type of grammar used; need for speed. lex.
• Context-free languages: grammar definition, memory needed for parsing. Notations for defining the syntax of a language: BNF, Pascal-style transition diagrams. Ambiguous grammars vs. unambiguous grammars. Augmented transition network; Yacc. What kinds of language constructs are context-free?
• Derivation from a context-free grammar: relationship to parse tree, notations for a derivation, definition of a language in terms of derivations.
• Operator precedence grammar and parser: definitions; precedence numbers, associativity. How operator precedence parser works (be able to work an example).
• Top-down parsing: definition; why backup may be required; for what kinds of languages does it work well; recursive descent parser; problems with left recursion; left factoring; implementation of top-down parser by a recursive program: be able to write a procedure for a construct such as an IF statement.
• Shift-reduce parser: use of stack; four actions of shift-reduce parser; relationship to canonical derivation; how parse tree is constructed using shift-reduce parser.
• Symbol tables: methods of organization; speed, advantages, disadvantages of each; comparisons; be able to select a method for a particular application. Search is more frequent than insertion. Symbol tables for block-structured languages. What things are put in symbol tables? Examples of symbols in a compiler. Deletion of symbols: when it is needed; relation to table organization methods. Methods of storing identifier names. Use of indirection or auxiliary table structures.
• Data area and base-offset addressing; storage allocation algorithm; allocation of data in records; word alignment and padding; variant records.
• Address calculations for array references (know the formulas). Address calculations for access to fields of a record; determining types of accesses to parts of a structure. Be able to calculate the size of an array of records; be able to calculate the address offsets for access to an array element and record field.

Vocabulary