Dublin descriptors

expected learning outcomes

knowledge and
understanding

After successfully completing the course, the student:

• knows the fundamental notions and models of artificial  language, regular and context-free language, regular expression, finite and pushdown automaton, determinism and non-determinism, grammar (BNF and extended), syntax tree, ambiguity, and their relationships of equivalence and inclusion
• knows the basic transformations of automata and grammars, for exposing determinism, eliminating redundancy and ambiguity, and normalizing automaton and grammar forms
• knows the fundamental abstract syntactic structures of artificial languages: list, hierarchical list, nested block, expression and parenthetical structure
• knows the notion of parsing an artificial language, the basic LR (bottom-up) and LL (top-down) LR deterministic parsing algorithms, their generalizations to an extended grammar (EBNF), their relations with language families, grammars and automata, and the general deterministic Early parsing algorithm
• knows the fundamental notions of translation and semantic, syntax-directed translation, attribute grammar, static flow analysis, for defining the semantics of an artificial language
• knows the fundamental operations and data structures of the compiler for a programming language: lexical and syntax analyzer and machine code generator, and symbol table and syntax tree

applying knowledge
and understanding

After successfully completing the course, the student:

• is able to transform regular expressions, grammars and automata, for exposing determinism, removing redundancy, ambiguity and errors, or normalizing them
• is able to design regular expressions and grammars for modelling syntactic structures or a whole artificial language, starting from an informal description or a prerequisite list, and is able to add simple semantics to an artificial language by means of a syntax-directed scheme or an attribute grammar
• is able to design a deterministic parser for an artificial language, of type (extended) LR, LL or Early, to use it to compute a syntax tree, and to autonomously design a simple code generator for compiling the language into low-level (machine or assembly) code, also by using the standard complier-design tools Flex and Bison
• is able to autonomously design a simple semantic analyzer for an artificial language, based on the attribute grammar model

lifelong learning skills

After successfully completing the course, the student:

• is able to autonomously understand and model the syntax and semantics of new artificial languages, in particular the programming ones
• is able to autonomously understand and model the structure of a compiler for a new simple artificial language, with limited optimization, or for an extension of an existing one with new features
• is able to contribute in bringing artificial language functionalities and technology into complex software systems and applications

Type of assessment

Description

Dublin descriptor

Written test

Solution of numerical problems

·        analyze the behaviour of a regular expression, a grammar or an automaton

Exercises focusing on design aspects

• design grammars and automata for informally specified syntactic structures
• design a syntax analyzer (LR, LL, Early, possibly extended) for simple grammars, and simulate its behaviour
• design small parts of a translator or semantic analyzer, for simple grammars
• update a prototypal compiler (modelled in C language) for a simple programming language (Java-like) and add to it syntactic and semantic features, to extend the language compiled

1,2

1, 2, 5