4.2.4 The example revisited .................................. 99
4.2.5 CYK parsing with Chomsky Normal Form
................... 99
4.2.6 Undoing the effect of the CNF transformation
................ 101
4.2.7 A short retrospective of CYK
............................ 104
4.2.8 Chart parsing
........................................ 105
5 Regular grammars and finite-state automata
.................... 106
5.1 Applications of regular grammars
............................ 106
5.1.1 CF parsing
.......................................... 106
5.1.2 Systems with finite memory
............................. 107
5.1.3 Pattern searching
..................................... 108
5.2 Producing from a regular grammar
........................... 109
5.3 Parsing with a regular grammar
............................. 110
5.3.1 Replacing sets by states
................................ 111
5.3.2 Non-standard notation
................................. 113
5.3.3 DFA’s from regular expressions
.......................... 114
5.3.4 Fast text search using finite-state automata
.................. 116
6 General directional top-down methods
......................... 119
6.1 Imitating left-most productions
............................. 119
6.2 The pushdown automaton
................................. 121
6.3 Breadth-first top-down parsing
.............................. 125
6.3.1 An example
......................................... 125
6.3.2 A counterexample: left-recursion
......................... 127
6.4 Eliminating left-recursion
................................. 128
6.5 Depth-first (backtracking) parsers
........................... 130
6.6 Recursive descent
....................................... 131
6.6.1 A naive approach
..................................... 133
6.6.2 Exhaustive backtracking recursive descent
.................. 136
6.7 Definite Clause grammars
................................. 139
7 General bottom-up parsing
.................................. 144
7.1 Parsing by searching
..................................... 146
7.1.1 Depth-first (backtracking) parsing
........................ 146
7.1.2 Breadth-first (on-line) parsing
........................... 147
7.1.3 A combined representation
.............................. 148
7.1.4 A slightly more realistic example
......................... 148
7.2 Top-down restricted breadth-first bottom-up parsing
.............. 149
7.2.1 The Earley parser without look-ahead
......................
149
7.2.2 The relation between the Earley and CYK algorithms
..........
155
7.2.3 Ambiguous sentences
.................................. 156
7.2.4 Handling ε-rules
..................................... 157
7.2.5 Prediction look-ahead
..................................
159
7.2.6 Reduction look-ahead
.................................. 161
8 Deterministic top-down methods
............................. 164
8.1 Replacing search by table look-up
........................... 165
评论12