F29LP Language Processors

Dr Arash EshghiKayvan Karim

Course co-ordinator(s): Dr Arash Eshghi (Edinburgh), Kayvan Karim (Dubai).


  • To develop skills in programming language definition
  • To develop skills in programming language implementation

Detailed Information

Pre-requisite course(s): F28PL Programming Languages .

Location: ALP, Dubai, Edinburgh.

Semester: 2.


Language definition:

  • lexicon: non-terminal & terminal symbols, type 3 grammars, regular expressions, finite state automata, Moore & Mealey machines, left & right recursion
  • concrete syntax: type 2 grammars & BNF, factoring grammars, converting left to right recursion, LL(K) & LR(K) grammars, push down automata, parsing
  • abstract syntax: abstract syntax from concrete syntax
  • static semantics: types
  • dynamic semantics: overviews of axiomatic, denotational & operational semantics; introduction to structural operational semantics (SOS) for declarations, expressions, statements

Language implementation:

  • lexical analysis
  • syntax analysis: recursive descent for LL(1)
  • abstract syntax tree (AST) construction
  • AST pretty printing
  • overview of interpreter/abstract machine
  • AST interpretation
  • static analysis of AST: e.g. type checking, identifier resolution

code generation e.g.: register/memory allocation, structured constructs as test/jump, structured data as structured memory sequences, stack discipline for

  • blocks/subroutines, parameter passing
  • run time environment: e.g. heap allocation, garbage collection, debugging support
  • compiler construction tools e.g. Lex, Yacc, JavaCC based on simple imperative language

Learning Outcomes: Subject Mastery

Understanding, Knowledge and Cognitive Skills Scholarship, Enquiry and Research (Research-Informed Learning)

  • Ability to construct & manipulate lexical & syntactic definitions
  • Understanding of relationship between grammars & automata
  • Ability to construct lexical & syntactic analysers from definitions
  • Familiarity with static & dynamic semantics, and associated formalisms
  • Ability to generate & traverse ASTs
  • Ability to construct AST-based analysers, interpreters & code generators for simple languages
  • Understanding of run-time environments
  • Ability to use compiler construction tools

Learning Outcomes: Personal Abilities

Industrial, Commercial & Professional Practice Autonomy, Accountability & Working with Others Communication, Numeracy & ICT

  • Appreciation of problem solving as language definition & implementation
  • Ability to apply appropriate language oriented formalisms, tools & techniques in solving problems
  • Skills in engineering complex software artefacts

SCQF Level: 9.

Credits: 15.