Start a new search?

SCC.312: Languages and Compilation

Department: Computing and Communications (School of) NCF Level: FHEQ/QCF/NQF6//RQF6
Study Level: Part II (yr 3) Credit Points: 15.0
Start Date: 15-01-2018 End Date: 23-03-2018
Available for Online Enrolment?: Y Enrolment Restriction: Only available to students majoring in delivering department
Module Convenor: Dr PE Rayson

Syllabus Rules and Pre-requisites

  • Prior to SCC.312, the student must have successfully completed:

Curriculum Design: Outline Syllabus

  • This is a core fundamental module in Computer Science which will introduce the students to formal languages,
    grammars, automata and how these concepts relate to programming in terms of compilers and the compilation
    The first half of the course will introduce formal languages and will include an introduction to syntax and semantics, phrase structure grammars and the Chomsky Hierarchy as well as processes such as derivation and parsing. We will highlight grammar equivalence and ambiguity in Context Free grammars and its implications. The relationship between languages and abstract machines will be explored. The concept of computation will be presented alongside Turing's thesis, alternative models of computation (functional languages, etc.) and applications of abstract machine representations.
    The second half of the course will provide an introduction to the compilation process including lexical analysis and syntactic analysis, LL(1) and LR(1) languages and recursive descent. To complete this part of the course, semantic analysis and the symbol table will lead into the synthesis phase: intermediate representations, target languages and structures and finally code generation.

Curriculum Design: Single, Combined or Consortial Schemes to which the Module Contributes

    • BSc/MSci Computer Science
    • BSc/MSci Computer Science Innovation
    • BSc/MSci Software Engineering
    • BSc/MSci IT for Creative Industries
    • BEng/MEng Computer Systems Engineering
    • BSc Management and IT
    • BSc/ BA Computer Science and  European Languages
    • BSc/ BA Computer Science and Music
    • BSc/ BA Computer Science and Mathematics
    • BSc/BA Accounting, Finance and Computer Science
    • BSc Natural Sciences
  • 60% Exam
  • 40% Coursework

Assessment: Details of Assessment

  • The coursework will comprise a number of pieces. The first set (worth a total of 20%) will be set as practical workbooks containing a number of questions to provide formative assessment of students’ progress against learning outcomes in the first half of the course on phrase structure grammars, languages and machines. These will be supported with lab sessions although will not be assessed directly in the practical labs. The second coursework (worth 20%) will typically be a programming piece of coursework on building a syntax recogniser for a small programming language. Typical deadlines would be in weeks 3, 4 and 8 of the ten week course. The exam will have a duration of 150 minutes (i.e. 2.5 hours). Students have to choose 3 out of 4 questions, for each question they can get a maximum of 20 marks.

Educational Aims: Subject Specific: Knowledge, Understanding and Skills

  • This module aims:

    • To introduce students to the theory of formal languages, and how it relates to programming languages. 
    • To study the relationship between formal languages and abstract machines, and how it relates to compilation.
    • To give students a basic understanding of the compilation process for a high-level programming language, both analysis (lexical, syntactic and semantic) and synthesis. 

Educational Aims: General: Knowledge, Understanding and Skills

  • The aim more generally in this module is to encourage students to engage with more theoretical aspects of computer science in order to complement practical skills in other parts of the degree. We aim to give the students knowledge and understanding so that they are able to see the links to other disciplines such as linguistics on formal languages and are able to explain the challenges of compilation in the context of software development and computer science more widely.

Learning Outcomes: Subject Specific: Knowledge, Understanding and Skills

  • At the end of the course the students should:

    • be able to recognise and classify the four different types of phrase structure grammar (regular, context-free, context-sensitive and unrestricted) according to the Chomsky Hierarchy
    • be able to construct and use the abstract machine appropriate to each grammar (finite state recogniser, pushdown recogniser, Turing Machine) and use this to check the validity of strings
    • appreciate key principles of languages, grammars and machines such as syntax, semantics, ambiguity, equivalence, determinism and non-determinism and how this relates to real life situations such as compilers
    • be able critically to evaluate each grammar or machine and understand the various limitations of each
    • have a basic understanding of the concept of well-specified problems that cannot be solved, in particular the Halting Problem.
    • be able to describe the general features of the compilation process (lexical analysis, syntactic analysis, semantic analysis, code generation and optimisation) in the context of a typical procedural language.
    • be able to describe the general features of, and constraints on, the syntactic analysis phase of a compiler
    • be able to create a recursive descent parser for a simple programming language, making changes to the grammar as appropriate
    • be able to create and use SLR(1) parsing tables for a simple context-free grammar, explaining how to recognise that a grammar is not SLR(1)
    • be able to describe the basic features of the semantic analysis phase and the synthesis section of a compiler, particularly as applied to modern programming languages such as Java and C#


Learning Outcomes: General: Knowledge, Understanding and Skills

  • On successful completion of this module, participants will have demonstrated their capacity to:

    1.  reflect more productively on the formal underpinnings of programming languages and the compilation process and how it relates to programming more generally
    2.  design algorithms in a formal manner separated from the usual constraints of programming
    3. explain and justify more formally the limitations of certain programming formalisms

Contact Information

If you encounter any difficulties accessing Online Courses Handbook information please contact the Student Registry:

If you require further details in relation to academic content please contact the appropriate academic department directly.

Related Pages