Module 3: Syntax Analysis

No. of lectures : 10

Topics Covered

1. Motivation and Issues
2. Basic Concepts and Definitions in Parsing
3. Principles of Top-Down parsing
4. Top-Down Parser Construction
5. Principles of Bottom-Up Parsing
6. Construction of LR Parsers
7. Automatic Generation of LR Parsers

Objectives

At the conclusion of the module, the student should be able to:

1. Understand the role of a parser, its interface with the scanner and the rest of the compiler.

2. Understand the basic concepts such as derivations, parse-trees, ambiguity and their relevance to parsing.

3. Construct equivalent Context Free Grammars using transformations such as left factoring, left recursion removal, etc. and know their relationship to the underlying parsing method.

4. Understand the algorithms that generate various useful information such as FIRST, FOLLOW, items and sets of items, etc., from a CFG.

5. Create LL(1), SLR(1), LALR(1) and LR(1) parsing tables manually for small grammars.

6. Relate the theoretical results of LR parsing to understand the behaviour of these parsers and also their capabilities.

7. Write grammar rules and actions in yacc to construct a parser for a subset of some programming language and test the same.