Faculty of Science

Objectives

To define what constitutes a language; classes of languages that are useful in describing computer languages, and how they can be mechanically recognized and how a high-level language (HLL) may be transformed into code (i.e. machine code) executable by a computer; lexical and syntax analyses of HLL’s.

Contents

Basic notation and definitions; Words, alphabets and strings, languages; RECALL sets, relations;. Regular languages (RLs): recognition via finite automata; regular expressions; linear grammars; equivalence theorem (between regular expressions; ndfa and dfa’s); normalization of regular languages; mention closure properties (e.g. union, intersection, subsets,); Context-Free languages (CFLs): recognition via push-down automata (PDA); context-free grammars; their simplification; Chomsky normal form; existence on non-regular grammars; mention equivalence theorems between PDAs and CFLs; mention closure properties (e.g. union, inclusion of RL); decision problems (e.g. if a string belongs to a CFL; [non]/finite CFL; ambiguity;…); existence of context-sensitive languages; Chomsky hierarchy of languages; Overview of compilers; Brief history; basic concepts; compilers and interpreters; Symbol table: type of information stored; choice of data structure (e.g. array, linked-list, hash table); Lexical analysis: importance; definitions and terminology; specifying and identifying lexemes; error handling techniques: syntax analyses: importance of syntax analyser; deterministic/non-deterministic top-down syntax analysis; Mention: LL(k) grammars; deterministic/non-deterministic bottom-up syntax analysis, LR(k) grammars: “Long-range” syntax analysis (e.g. type-checking); error handling; type-checking with practical illustrations; Introduction to translation: Syntax-directed translation; syntax trees and attributes; semantic actions; inherited and synthesized attributes; Mention of compilation tools.

Prerequisite: