Next:
Contents
 
Contents
Notes on
Formal Language Theory and Parsing
James Power
Department of Computer Science
N
ATIONAL
U
NIVERSITY OF
I
RELAND,
M
AYNOOTH
Maynooth, Co. Kildare, Ireland.
James.Power@May.ie
This version prepared on 29 November 2002
Contents
REGULAR LANGUAGES
Regular Expressions
Non-Deterministic Finite-State Automata
Converting a regular expression to a NFA - Thompson's Algorithm
Kleene's Theorem
Converting a NFA to a Regular Expression
Deterministic Finite-State Automata
Constructing a DFA from an NFA (``Subset Construction'')
DFA minimisation
Further Properties of Regular Languages
Total DFA
Closure of Regular Languages
Other Decision Problems for FSAs
Grammars
Regular Grammars
Converting an FSA to a Regular Grammar
Limitations of Regular Languages
The Pumping Lemma: Examples
CONTEXT-FREE LANGUAGES
The Chomsky Hierarchy
Grammars for Programming Languages
BNF Notation
Derivations and Parse Trees
Leftmost and Rightmost Derivations
Modifying Grammars
Left Factoring
Eliminating Ambiguity
Eliminating Immediate Left Recursion
Eliminating Indirect Left Recursion
Eliminating
-productions
Eliminating Unit Productions
PUSH-DOWN AUTOMATA
Formal Definition
Converting a CFG to a PDA
Converting a PDA to a CFG
Deterministic PDAs
Non-Deterministic CFLs
Proving that a Language is not Context-Free
The Pumping Lemma for context-free languages
The Pumping Lemma: Examples
Limitations of the Pumping Lemma
The Closure of Context-Free Languages
Decision Problems for Context-Free Languages
TOP-DOWN PARSING
Recursive Descent Parsing
Lookahead
FIRST and FOLLOW
Implementing a Parser
The
Parsers
Early's Parser
Early's Items
Early's Algorithm
Unger's Method
BOTTOM-UP PARSING
Bottom-Up (Shift-Reduce) Parsing
items
Kernel Items
The closure and move operations on items
Handle-recognising DFAs and LR(0) Parsers
Construction of a handle-recognising DFA
Operation of a handle-recognising DFA
The
parsers
Inadequte States
SLR(1) Parsers
Parsers
Constructing LR(1) Item sets
Parsers
Tomita's Parser
CYK Method
About this document ...
James Power 2002-11-29