E-Book Content
Grammars and Parsing Johan Jeuring Doaitse Swierstra
c 2001 by Johan Jeuring and Doaitse Swierstra. Copyright
2
Contents 1 Goals 1 1.1 History 2 1.2 Grammar analysis of context-free grammars 1.3 Compositionality 4 1.4 Abstraction mechanisms 4
3
2 Context-Free Grammars 7 2.1 Languages 8 2.2 Grammars 11 2.2.1 Notational conventions 14 2.3 The language of a grammar 15 2.3.1 Some basic languages 17 2.4 Parse trees 19 2.4.1 From context-free grammars to datatypes 2.5 Grammar transformations 22 2.6 Concrete and abstract syntax 28 2.7 Constructions on grammars 31 2.7.1 SL: an example 33 2.8 Parsing 35 2.9 Exercises 36 3 Parser combinators 41 3.1 The type ‘Parser’ 43 3.2 Elementary parsers 46 3.3 Parser combinators 49 3.3.1 Matching parentheses: an example 3.4 More parser combinators 58 3.4.1 Parser combinators for EBNF 58 3.4.2 Separators 61 3.5 Arithmetical expressions 63 3.6 Generalised expressions 66 3.7 Exercises 67 4 Grammar and Parser design 71 4.1 Step 1: A grammar for the language 4.2 Step 2: Analysing the grammar 72 3
72
56
22
4
CONTENTS
4.3 4.4 4.5
4.6 4.7 4.8
Step 3: Transforming the grammar 73 Step 4: Deciding on the types 73 Step 5: Constructing the basic parser 74 4.5.1 Basic parsers from strings 75 4.5.2 A basic parser from tokens 76 Step 6: Adding semantic functions 77 Step 7: Did you get what you expected 80 Exercises 80
5 Regular Languages 83 5.1 Finite-state automata 84 5.1.1 Deterministic finite-state automata 84 5.1.2 Nondeterministic finite-state automata 86 5.1.3 Implementation 89 5.1.4 Constructing a DFA from an NFA 92 5.1.5 Partial evaluation of NFA’s 95 5.2 Regular grammars 95 5.2.1 Equivalence of Regular grammars and Finite automata 5.3 5.4 5.5
Regular expressions Proofs 105 Exercises 109
101
6 Compositionality 113 6.1 Lists 1