EE2-15 Language Processors
Lecturer(s): Dr Yiannis DemirisAims:
To introduce students to the concepts underlying the design and implementation of language processors.
Learning Outcomes:
By the end of the course, students will be able to answer these questions:
(1) What language processors are, and what functionality do they provide to their users? (2) What core mechanisms are used for providing such functionality?
(3) How are these mechanisms implemented?
Students will also be able to construct language processors.
Syllabus:
Part I: Fundamentals
Introduction to language processors; types of language processing; assemblers, compilers, preprocessors, interpreters and disassemblers; T-diagram representations of compilers; examples of language processors (GCC, Tex/Latex, Matlab, SysTran, Postscript, XML); compiling and running a compiler; cross-compilation and bootstrapping; semantics; conceptual structure of language processors; front and back-ends; passes; compiler width; criteria for the design and evaluation of language processors; history and evolution of language processors; A complete example of a language processor (an infix to postfix expression converter) in full detail; syntax-directed translation; attributes and annotated parse trees; tree-traversal methods
Part 2: Theoretical underpinnings of Language Processors
Introduction to grammars; basics: production rules and derivation of strings; formal definitions; Chomsky’s hierarchy; context-sensitive and context-free grammars; Turing machines; linearly-bound automata; push-down automata; regular grammars; finite-state automata; BNF/EBNF syntax; regular expressions and their limitations
Part II: Lexical analysis
Introduction to lexical analysis; tokens and attributes; deterministic and non-deterministic finite state automata; epsilon-transitions; equivalency of NFA and DFA; elimitation of e-transitions and non-deterministic transitions; epsilon-closures; subset construction; Thompson’s algorithm for converting a regular expression to a NFA; automatic construction of DFAs; DFA minimization; automatic generation of lexical analysers using Lex/Flex
Part III: Parsing
Introduction to parsing; leftmost and rightmost derivations; parsing ambiguities; top-down vs. bottom-up parsing; L{L/R}{k} notation; recursive-descent parsing; lookaheads and predictive-parsing; FIRST and FOLLOW sets and their computation; left-recursion and its elimination; left-factoring; transition diagrams & tables and their construction; bottom-up parsing; shift-reduce parsing; stack implementations; LR(k) parsing; LR/SLR/Canonical LR/LALR; construction of parsing tables; Automatic construction of parsers using YACC/Bison
Part IV: Context-handling
Introduction to context-handling; attributes and attribute grammars; dependency graphs; S- and L-attributed grammars; S-attributes and bottom-up parsing; inherited attributes; type-checking; symbol tables
Part V: Code Generation and Optimization
Introduction to code generation; intermediate code generation; types of intermediate code (Pascal P-Code; Java byte-code; 3-address code); translation of intermediate code to target code; instruction selection issues; storage management; memory, heap, and garbage collection; register allocation; flow graphs and basic blocks; converting 3-address statement sequences into basic blocks; local and global transformations; dead-code elimination; common-subexpression elimination; algebraic transformations; computation of next-use information; register and address descriptors; register allocation in detail: interference graphs, register allocation through graph colouring; Optimization: peep-hole optimisation; Flow of control optimisations; Removal of redundant loads and stores; Removal of unreachable code; Copy propagation; Code motion; Constant folding; data-flow analysis; code profiling;
Part VI: Case studies
GCC internals; front and back ends; Register-Transfer Language; Construction of an PASCAL to ARM assembly language processor (assessed laboratory coursework)
Assessment:
2-hour examination in June
Coursework contribution: 0%
Term: Spring
Closed or Open Book (end of year exam): Closed
Coursework Requirement
Laboratory Experiment
Non-assessed problem sheets
Oral Exam Required (as final assessment): yes
Prerequisite: None required
Course Homepage: http://www.iis.ee.ic.ac.uk/yiannis/lp
|
|