On completing this course the student will have a clear understanding of the role of formal grammars for both languages and computers. The student will
- 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
- understand and be able to implement a simple lexical analyzer
- 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 explain the basic features of the JLex and CUP tools for creating lexical and syntax analysers
- 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#
