AUTOMATA THEORY AND COMPILER DESIGN

Structural Representations

• Automata and Complexity
• Central Concepts of Automata Theory – Alphabets, Strings, Languages, Problems

Nondeterministic Finite Automata

• Formal Definition
• Application
• Text Search
• Finite Automata with Epsilon-Transitions

Deterministic Finite Automata

• Definition of DFA
• How A DFA Process Strings
• The Language of DFA
• Conversion of NFA with €-transitions to NFA without €-transitions
• Conversion of NFA to DFA

Regular Expressions

• Finite Automata and Regular Expressions
• Applications of Regular Expressions
• Algebraic Laws for Regular Expressions
• Conversion of Finite Automata to Regular Expressions

Pumping Lemma for Regular Languages

• Statement of the pumping lemma
• Applications of the Pumping Lemma

Context-Free Grammars

• Definition of Context-Free Grammars
• Derivations Using a Grammar
• Leftmost and Rightmost Derivations
• The Language of a Grammar
• Parse Trees
• Ambiguity in Grammars and Languages

Push Down Automata

• Definition of the Pushdown Automaton
• The Languages of a PDA
• Equivalence of PDA and CFG’s
• Acceptance by final state

Turing Machines

• Introduction to Turing Machine
• Formal Description
• Instantaneous description
• The language of a Turing machine

Undecidability

• Undecidability
• A Language that is Not Recursively Enumerable
• An Undecidable Problem That is RE
• Undecidable Problems about Turing Machines

The structure of a compiler

Lexical Analysis

• The Role of the Lexical Analyzer
• Input Buffering
• Recognition of Tokens
• The Lexical- Analyzer Generator Lex

Syntax Analysis

• Introduction
• Context-Free Grammars
• Writing a Grammar
• Top-Down Parsing
• Bottom- Up Parsing
• Introduction to LR Parsing: Simple LR, More Powerful LR Parsers

Syntax-Directed Translation

• Syntax-Directed Definitions
• Evaluation Orders for SDD's
• Syntax-Directed Translation Schemes
• Implementing L-Attributed SDD's

Intermediate-Code Generation

• Variants of Syntax Trees
• Three-Address Code

Run-Time Environments

• Stack Allocation of Space
• Access to Nonlocal Data on the Stack
• Heap Management