CMSC 430: THEORY OF LANGUAGE TRANSLATION

Catalog Description

Formal translation of programming languages, program syntax and semantics. Finite state recognizers and regular grammars. Context free parsing techniques such as LL(k) and LR(k). Code generation, improvement, syntax directed translation schema.

Prerequisites

CMSC 330.

Topics

Prerequisite material. Run-time organization of programming languages (ch. 7): storage allocation, addressing nonlocal variables and parameters, arrary references.
Overview (ch. 1 & 2)
Regular Languages (ch. 3): regular languages and regular expressions, NFAs and DFAs, minimizing the states of a DFA.
Context-Free Languages (ch. 4): context-free grammars: ambiguity, precedence, associativity, bottom-up parsing: SLR(k), LALR(k) and LR(k) grammars, grammar transformations: left factoring and removal of left recursion, top-down parsing: recursive descent and LL(1).
Syntax-Directed Translation and Attribute Grammars (ch. 5): type checking, S-attributed and L-attributed grammars.
Intermediate Code Generation (ch. 8): boolean expressions with explicit values and short-circuit evaluation, control flow in conditional statements, backpatching.
Code Generation (ch. 9, 10): basic blocks and flow graphs, DAGs, generating code from DAGs.
Code Optimization (ch. 10): global data flow analysis of structured programs, iterative solutions to data flow equations.

Course Text

Aho, Sethi and Ullman. Compilers: Principles, Techniques and Tools , Addison-Wesley.
Mason. lex & yacc, O'Reilly & Associates.

Typical Grading and Workload

Examinations
- 20% - Midterm
- 30% - Final
50% - Projects
- Convert a regular expression to a minimum-state DFA.
- A lexical analyzer using lex.
- A basic parser using yacc.
- Type checking for a block-structured language.
- Code generation for a RISC machine.
- Basic code optimization.