Dr. Nikolay Nikolaev

IS53011A Language Design and Implementation

TABLE OF CONTENTS:
SYLLABUS
...Course description
...Course aims
...Learning outcomes
...Textbooks
...Attendance
...Grading
...Examination Assesment
...Dates for Coursework Assignments
...Office hours
...References
...Internet Resources
COURSE OUTLINE FOR Autumn 2011

Course description

This course teaches the principles and techniques for construction of programming language processors. It offers algorithms for the design of language compilers and interpreters. There are covered the following fundamental topics: language definition, lexical analysis, syntax analysis, code generation and code optimization. Knowledge in regular and context-free language grammars, top-down and bottom-up parsing are provided. Emphasis is put on the pragmatics of compiler construction: syntax-directed translation, automatic code generation and strategies for machine-independent code improvement. A one-pass language compiler in Java is demonstrated.

back to top

Course aims

The objectives of the course in language, design, and implementation are:

to offer a description of a programming language compiler;
to give the theoretical principles of language interpretation;
to introduce the development issues in compiler construction;
to provide algorithms for syntactic, semantic language analysis, code generation and optimization;
to present automatic generator tools for language design;
to demonstrate the code of a simple language processor.

back to top

Learning outcomes

On successful completion of this module, students will be able to:

Subject-related Knowledge

explain the phases of programming language compilers;
understand the process of syntax-directed language translation;
perform lexical analysis using regular grammars;
perform syntax analysis using context-free grammars;
interpret top-down and bottom-up parsing algorithms;
generate machine independent three-address code;
optimize machine independent three-address code.

Subject-related Skills

develop nondeterministic and deterministic finite-state automata;
simulate the behavior of finite-state automata;
construct parse trees during syntax analysis.

Transferrable Skills

construct lexical analysers from given grammars;
analyse the results from language compilation.

back to top

Textbooks

Aho, A.V., Sethi, R. and Ullman, J.D.
Compilers: Principles, Techniques and Tools., Addison-Wesley Publ. Co., Reading, MA, 1988.

New Editions:
Aho, A.V., Sethi, R. and Ullman, J.D.
Compilers: Principles, Techniques and Tools., Prentice Hall International, Upper Saddle River, NJ, 2003.
Aho, A.V., Lam,M.S., Sethi, R. and Ullman, J.D.
Compilers: Principles, Techniques and Tools., Pearson Addison Wesley, Boston , MA, 2007.

back to top

Attendance

The students are advised to attend the lectures. Attendance to workshops is compulsory and will be monitored.

back to top

Grading

Excellent A = 70 - 100
Very Good B = 60 - 69
Good C = 50 - 59
Acceptable D = 40 - 49
Weak E = 35 - 39
Fail F = 0 - 34

back to top

Examination Assesment

One Written Examination: 80%
One Coursework Assignment: 20%

back to top

Dates for Coursework Assignment

Resit Coursework (2012): deadline 30 August 2012

Coursework Marking Scheme- every student should present:
a. NFA designed using the Thompson’s construction algorithm [15]
b. Program in Java that prints a decision, including:
b.i) Implementation of 1 stack and functions for its manipulation [20]
b.ii) Data Structures [5]
b.iii) Implementation of the move function [25]
b.iv) Implementation of the closure function [25]
c. Demonstration of the operation of the Java program including:
c.i) Printing of states while traversing the NFA [5]
c.ii) Printing of transitions while traversing the NFA [5]

Feedback on the Coursework Assignment: One week after the deadline the marks on the submissions will be ready, and every student will receive the comments on his work written by the lecturer on the presented worksheet (during the office hours or at convenient times by appointment).

back to top

Surgery hours

Monday 12:00 - 13:00 p.m.
Monday 16:00 - 17:00 p.m.

back to top

References

Watt,D.A. and Brown,D.F.
Programming Language Processors in Java,
Prentice-Hall, NY, 2000.

Appel,A.W.
Modern Compiler Implementation in Java,
Cambridge University Press, Cambridge, UK, 1998.

Hopcroft,J. and Ullman,J.D.
Introduction to Automata Theory, Languages and Computation,
Addison-Wesley Publ. Co., Reading, MA, 1979.

back to top

Internet Resources

Programming Language Processors in Java- Watt and Brown's book (sources)

Modern Compiler Implementation in Java- Appel's book (sources)

JLex: A Lexical Analyzer Generator for Java(TM)

CUP Parser Generator for Java

The Java Language Specification (2nd ed.)

back to top

Date

L/W

Topic / Assignment

3/October/2011

L

Language Compiler Design: The Phases of a Compiler,
Building Languages from Grammars, Language Interpretation.
Text: pp.1-23 (Chapter 1).
A Simple Language Compiler I: Sintax-Definitions and
Translations, Recognizing Lexical Elements.
Text: pp.25-32, 54-58 (Chapter 2).

3/October/2011

W

Implementing a Lexical Analyser in Java: Scannig,
Symbol Tables, Using Stack Machines.
Text: pp.118-124 (Section 4.5, Watt and Brown's book).

10/October/2011

L

A Simple Language Compiler II: Parse Trees,
Grammar Ambiguities, Associativity of Operators.
Text: pp.33-40 (Chapter 2).
A Simple Language Compiler III: Basic Approaches
to Parsing, Optimizations of Translators.
Text: pp.41-53 (Chapter 2).

10/October/2011

W

Implementing a Parser in Java: Recursive Parsing,
Connecting Parsers with Lexical Analysers (SPL.java).
Text: pp.69-78 (Section 2.9).

17/October/2011

L

Lexical Analysis: Regular Expressions,
Strings and Languages, Translation Diagrams.
Text: pp.83-104 (Chapter 3).
Language Recognition: Finite-State Automata (FSA),
Nondeterministic NFA and Deterministic DFA Automata.
Text: pp.113-120 (Chapter 3).

17/October/2011

W

Making NFA from Regular Expressions: Implementing
the Thompson's Construction Algorithm.
Text: pp.122-127 (Chapter 3).

24/October/2011

L

Converting NFA to DFA: The Subset Construction
Algorithm, Computation of Closures.
Text: pp.117-121 (Chapter 3).
Optimizing Finite-State Automata: Minimizing the
States of Deterministic Finite-State Automata.
Text: pp.134-146 (Chapter 3).

24/October/2011

W

Automatic Lexical Analyzer Generators: The Lex
Language and Software Tool (for Unix and Linux).
Text: pp.128-133 (Chapter 3).

31/October/2011

L

Syntax Analysis: Context-Free Grammars (CFG),
Derivations, Parse Trees, Elimination of Left Recursion.
Text: pp.159-180 (Chapter 4).
Top-Down Parsing: LL Grammars, Recursive-
Descent Parsing, Nonrecursive Predictive Parsing.
Text: pp.181-188 (Chapter 4).

31/October/2011

W

Building Predictive Parsing Tables: Computing the
First and Follow Functions, Error Recovery.
Text: pp.188-194 (Chapter 4).

14/November/2011

L

Bottom-Up Parsing: LR Grammars, Shift-Reduce
Parsers, Handlers, Stack Implementation.
Text: pp.195-202 (Chapter 4).
Operator Precedence Parsing: Precedence Relations,
Making Operator Precedence Relations.
Text: pp.203-207 (Chapter 4).

14/November/2011

W

Interpreting Operator Precedence Parsers: Building
Operator Precedence Functions.
Text: pp.208-215 (Chapter 4).

21/November/2011

L

The LR Parsing Algorithm: Model of an LR Parser,
Advantages of LR Parsing Machines.
Text: pp.215-220 (Chapter 4).
Constructing LR Parsing Tables: The Sets-of-Items
Construction Algorithm, Closure and Goto Operations.
Text: pp.221-226 (Chapter 4).

21/November/2011

W

Interpreting Simple LR Parsers: Developing Parse
Tables, SLR Shift-Reduce Parsing.
Text: pp.227-230 (Chapter 4).

28/November/2011

L

Syntax Directed Translation: Syntax Directed
Definitions, Synthesized and Inherited Attributes.
Text: pp.278-292 (Chapter 5).
Type Checking: Type Checking of Declarations
Type Checking of Expressions and Commands.
Text: pp.343-363 (Chapter 6)

28/November/2011

W

Automatic Parser Generators: The Yacc Language
and Software Tool (for Unix and Linux)
Text: pp.257-266 (Chapter 4).

5/December/2011

L

Intermediate Code Generation: Machine
Independent Languages, Three-Address Code.
Text: pp.463-472 (Chapter 8).
Code Generation: Processing Declarations,
Expressions, Commands, and Procedures.
Text: pp.473-497 (Chapter 8)

5/December/2011

W

Generating Three-Address Machine Language
Code for a Simple Example Program.
Text: pp.507-510 (Chapter 8).

12/December/2011

L

Code Optimization: Improving Transformations,
Optimizing Compiler, Sources of Optimization.
Text: pp.585-600 (Chapter 10).

12/December/2011

W

Code Improving Transformations: Eliminating Common
Subexpressions, Loop-Invariants, Code Motion,
Elimination of Induction Variables.
Text: pp.633-644 (Chapter 10).