F29LP - Language Processors

Aims

To develop skills in programming language definition

To develop skills in programming language implementation

Syllabus

1. Regular Expressions (1.1 1. Construct Regular Expressions from Language Specification, 1.2 2. Given Regular Expression, construct Language Specification)

2. Formal Grammars (2.1 1. Formal Language Definition, 2.2 2. Grammars; Production Rules; BNF, 2.3 3. Types of Language and grammars, 2.4 4. Construct grammars of specific type for given formal language, 2.5 5. Produce left-most or right-most derivations for a given sentence, 2.6 6. Construct parse trees for a given sentence, 2.7 7. Understand ambiguity and how to prove that a given sentence is ambiguous)

3. Grammars and Parsing (3.1 1. Further understanding of ambiguity and its relationship to specific grammars and associated parse trees, 3.2 2. Eliminating ambiguity, 3.3 3. Understanding of different types of recursion in grammars, 3.4 4. Understanding desirability of recursion types in different parsing algorithms, 3.5 5. Eliminating left-recursion, 3.6 6. Understanding non-determinism and why it is not desirable in relation to parsing algorithms, 3.7 7. Eliminating non-determinism)

4. Deterministic Finite Automata (DFA) (4.1 1. Definition of DFAs, understanding what they are, and what they do, 4.2 2. Language of a DFA, 4.3 3. Constructing DFAs from language specifications, 4.4 5. Specifying the language of a given DFA; in English, set-theoretic notation, or using regular expressions, 4.5 6. Understanding the relationship between DFAs, regular languages, regular grammars, and regular expressions, 4.6 7. Understanding and applying the Pumping lemma)

5. Non-deterministic Finite Automata (NFA) (5.1 1. Definition of NFAs, understanding what they are, and what they do, 5.2 2. Understanding the difference between DFAs and NFAs, intuitively, but also in their formal definitions, 5.3 3. Understanding and constructing Computation Trees, 5.4 4. Constructing NFAs from language specifications, 5.5 5. Specifying the language of a given DFA; in English, set-theoretic notation, or using regular expressions, 5.6 6. Understanding the relationship between NFAs, regular languages, regular grammars, and regular expressions, 5.7 7. Converting NFAs to DFAs, 5.8 8. Understanding, constructing and analysing NFAs with epsilon-moves)

6. Pushdown Automata (PDA) (6.1 1. Formal Definition of PDAs, understanding what they are, and what they do above and beyond DFAs and NFAs, 6.2 2. Understanding of the details of transitions in PDAs, 6.3 3. Specifying PDA transitions in table, and graphical notation, 6.4 4. Instantaneous Descriptions IDs, 6.5 5. Different PDA modes of acceptance, 6.6 6. Constructing PDAs from language specifications or context-free grammars, 6.7 7. Specifying the language of a given PDA; in English, set-theoretic notation, or using Context-free grammars, 6.8 8. Understanding the relationship between Context-free languages and grammars, 6.9 9. Deterministic PDAs)

7. Compilers and Interpreters (7.1 1. Introducing Compilers and Interpreters; and the difference between them, 7.2 2. Different phases of a compiler and why they are necessary, 7.3 3. The difference between concrete syntax and abstract syntax, 7.4 4. A high-level view of how to represent the different kinds of syntax, 7.5 5. The difference between frontend and backend of compilers, 7.6 6. Different kinds of errors in different phases, 7.7 7. Overall role of optimisation)

8. Programming Language Interpreters (8.1 1. Describing a programming language in abstract syntax, 8.2 2. Representing programming languages and programs as an abstract data types and their members, 8.3 3. Writing / implementing an interpreter for simple expressions, 8.4 4. Writing an interpreter for the SIMP toy programming language)

9. Code Generation (9.1 1. Generating code in a low-level programming language e.g. MIPS from a high-level language; for the following constructs:, 9.2 - Nested expressions, 9.3 - Variables, 9.4 - Branching, 9.5 - Blocks, 9.6 - I/O, 9.7 2. Which high-level concepts use which memory segments, 9.8 3. Registers, 9.9 4. MIPS, its Instructions and use of Registers, , 9.10 5. Code Generation: SIMP to MIPS for the above constructs)

10. Function Calls (10.1 1. realising function calls via subroutines in MIPS, 10.2 2. passing arguments and returning results in MIPS, 10.3 3. Ensuring that subroutines do not overwrite each other’s registers using Stack Frames)

11. Compiler Optimisations (11.1 1. Different optimisation techniques, 11.2 2. Different places where to implement optimisations, 11.3 3. Why optimisation during code generation might be sub-optimal, 11.4 4. Peephole optimisation, 11.5 5. Constant folding/constant propagation, 11.6 6. Other optimisations)

12. Lexical Analysis (12.1 1. What is Lexical Analysis, 12.2 2. Write a simple Lexer, 12.3 3. Lexical Generators and how they work, 12.4 4. Write a Lexer using a Lexical Generator)

13. Parsers (13.1 1. The difference between a recogniser and a parser, 13.2 2. Writing a Recursive Descent Parser; and when this is possible, 13.3 3. The difference between concrete and abstract syntax, 13.4 4. LL1 grammars)