FORMAL LANGUAGES AND COMPILING TECHNIQUES

Instruction per Week : 4 Hrs Sessionals : 20
Duration of Examination: 3 Hrs Univ.Exam : 80

UNIT - I

Theory of computation - Introduction, basic concepts.
Finite Automata - DFA, NFA, Regular languages and regular grammars - Regular expressions, connection between regular expressions and regular languages, regular grammars.
Closure properties of regular languages.

UNIT - II

Context-Free Languages - CFG, Parsing and ambiguity, context free grammars and programming languages.
Simplification of context free grammars - Methods, normal forms.
Push-down automata - Non-deterministic push down automata, PDA and CFG
Pumping Lemmas
Introduction to Turning machine.

UNIT - III

Compiler - Introduction, Phases of compiler.
Lexical Analysis - role, specification of tokens, recognition of tokens, LEX.

UNIT - IV

Syntax Analysis - role of parser, top-down parsing, Bottom-up parsing, YACC.
Symbol Table organization.

UNIT - V

Semantic Analysis
Code generation
Code optimization

Suggested Reading :

1. Peter Linz. “ An Introduction of Formal Languages and Automata”, Narosa 2001
2. J.P.Bennett, “Introduction to Compiling Techniques”, Mc-Graw Hill, 1996.