Module Code - Title:
CS4158
-
PROGRAMMING LANGUAGE TECHNOLOGY
Year Last Offered:
2025/6
Hours Per Week:
Grading Type:
N
Prerequisite Modules:
CS4111
CS4112
CS4411
CS4512
CS4013
Rationale and Purpose of the Module:
To provide students with an understanding of production systems, phrase structure generative grammars, the languages generated by these grammars, and the abstract state machines that elucidate the parsing process. To provide students with an understanding of how recognition/parsing programs can be systematically derived from grammars, especially by means of parser generators. To provide an understanding of the notion of syntax directed translation, and how it can be implemented in parser-based tools, especially applied to code-generation, and documentation of programs.
Syllabus:
- Notion of Phrase Structure;
- Notion of Post's Production Systems;
- Chomsky's definition of Phrase structure Generative Grammars, and Hierarchy of Grammars. Sentential Forms and Languages generated by Context Free Grammars;
- Regular expressions, Regular sets, and Regular Grammars;
- Classification of Abstract State Machines, Configurations, Transitions;
- Construction of Recognising Finite State machines from Regular Grammars and Coversely Program Design based on Regular Expressions;
- Construction of Lexical Analysers including use of Generators such as LEX/FLEX;
- Leftmost and Rightmost derivation of sentences from Context Free Grammars, Parse trees, and ambiguity of Grammars;
- Top Down Parsing (Recursive Descent) Techniques;
- Bottom Up (LR) Parsing Techniques;
- Notion of an Item, Closure of a set of Items, Transitions between sets of items, and canonical collections of valid items;
- Parser Generators such as YACC/BISON and their use in syntax directed translation.
Learning Outcomes:
Cognitive (Knowledge, Understanding, Application, Analysis, Evaluation, Synthesis)
On successful completion of this module, students should be able to:
1. Convert a legal mathematical expression into prefix and postfix forms;
2. Create Post Production Systems for specified string sets;
3. Categorize grammars as regular, context sensitive, context free or unrestricted;
4. Generate a succinct grammar that describes a set of similar language instances;
5. Generate Finite State Automatons for given grammars which can successfully recognise a string conformant to that grammar;
6. Apply top-down parsing for a given LL(1) grammar and language instance;
7. Develop lexical analysers and syntax analysers for a specified language using 'lexical analyserÆ and 'parser generator' software (such as Flex and Bison);
8. Decide on the appropriate choice of parsing technique for a given grammar;
Affective (Attitudes and Values)
On successful completion of this module students should be able to:
1. Appreciate the importance of formulation and representation in problem solving;
2. Acknowledge the large contribution of mathematics to compiler theory.
Psychomotor (Physical Skills)
How the Module will be Taught and what will be the Learning Experiences of the Students:
Research Findings Incorporated in to the Syllabus (If Relevant):
Prime Texts:
Tony Cahill (2006)
A Small History of Parsing
, University of Limerick
J. R. Levine, T. Mason and D. Brown (1995)
Lex and Yacc
, O'Reilly Nutshell Series
Charles Fischer and Richard LeBlanc (1991)
Crafting a Compiler with C
, Addison-Wesley
Other Relevant Texts:
Programme(s) in which this Module is Offered:
Semester(s) Module is Offered:
Module Leader:
Jim.Buckley@ul.ie