Other links:
Other links:
Course Objective: Starting 1950’s (FORTAN & LISP) innumerable programming languages have been designed, implemented, deployed, and re-engineered. Some are targeted for specific domains while many serve to be ‘general purpose’ and cross-domain. Yet all of them have one thing in common – the ability to express the computational needs for some real world problem, to act as a bridge between the man and the machine. In this evolution, several paradigms of computing emerged — functional, procedural, object-oriented, generic (meta programming), logic — to name the major few. And languages have been functional (LISP), procedural (C), logic (Prolog), or simply multiparadigm (C++).
Programming Languages are living entities of computation. They are born (designed and implemented), grow in their use, and fade out to others. Hence, long serving languages need regular re-births and / or
re-purposing (C++98 → C++11 → C++14 → · · ·). Understandably lot of languages (actually most) die when they stop serving their computing role. And a few are resurrected (like LISP), when we rediscover
their worth after decades.
As languages take their journey, we need to take care of two major aspects for every language – how does the semantics of the language work for the ’man’ and how is it efficiently translated to the ’machine’ for the ever-evolving processor paradigms and architectures.
This course on language translation attempts to address these two aspects through a few illustrative languages. It is practice oriented. So you will need to write a complete compiler for a tiny language.
Pre-requisites:
1. Programming in C / C++ / Python
2. Data Structures
3. Algorithms
Coverage:
1. Introduction: Why study Programming Languages?; Overview of Programming Paradigms and Languages: Imperative (Algorithms + Data): Fortran, Pascal, Algol, C, Cobol, Ada, Perl, Python, Object Oriented (Data + Model): C++, Java, C#, SmallTalk, Eiffel, Logic (Facts + Rules + Queries): Prolog, Functional (Functions): Haskell, Scheme, Lisp, ML; Commonality and Contrast of Semantics
2. Framework for Language Translation: Phases of a Compiler: Overview of Compilation Process, Compiler Front-end, Compiler Back-end; Sample Translation
3. Lexical Analysis: Fundamentals; Theory of Lexical Analysis: RE → NFA → DFA
4. Flex: Lexical Analyzer Generator: Flex (Fast Lexical Analyzer) Specification; Interactive Flex and Flex-Bison Flow
5. Syntax Analysis: Fundamentals: Grammar Rules, Derivations and Parsing, Parse Tree, Abstract Syntax Tree (AST); Top-Down Parsers: Recursive Descent / LL Parsers, Left-Recursion, Ambiguous Grammar; Bottom-Up Parsers: SR, LR(0), SLR(1), LR(1), LALR(1), LR(k) Parsers, Ambiguous Grammar
6. Bison: Syntax Analyzer / Parser Generator: Bison Specification; Example Specifications and Handling Ambiguous Grammars
7. Machine Independent Translation: Intermediate Representations: AST, DAG, SSA, RTL, CDFG, Three Address Code; Symbol Table: Scope, Interface, Implementation; Translation of C Features: Arithmetic Expressions, Boolean Expressions, Control Constructs, Types and Declarations, Type in Translation,
Arrays, Type Expressions, Functions, Scopes, Structures, C Pre-Processor (CPP) Directives; Translation of C++ Features (Optional): Namespace, Class, Inheritance, Templates, Exceptions
8. Run-time Environments: Memory Organization and Binding Protocol: Symbol and Address; Symbol Table; Activation Record (AR) / Stack Frame; Function Call Protocol; Optimization and I/O; Types at Run Time: int, double, Pointer, struct, Array, Function Pointer, Blocks, Global, Static
9. Target Code Generation: Converting Three Address Code to Target Code: Three Address Code Optimization, Memory Binding, Register Allocation and Assignment, Code Translation, Target Code Optimization; Three Address Code to Assembly: Simple Code Mapping by Table Lookup
10. Control Flow Graph (CFG) and Local Optimization: Optimization Issues; Basic Block and Control Flow Graph; Optimizing Basic Blocks; Extended Basic Blocks
11. Global Register Allocation (GRA): Issues and Problem Formulation; Simple GRA by Usage Count; Chaitin’s Algorithm: GRA by Graph Coloring
12. Simple Code Generators: Issues in Code Generation; Simple and Optimal Code Generation Algorithms; Peephole Optimizations
