Preface |
|
v | |
|
|
xiii | |
Introduction and Preliminaries |
|
1 | (2) |
|
|
3 | (12) |
|
|
3 | (2) |
|
|
5 | (4) |
|
1.2.1 Parsing natural language |
|
|
5 | (2) |
|
1.2.2 Robustness in grammar-driven parsers |
|
|
7 | (1) |
|
|
8 | (1) |
|
|
9 | (6) |
|
|
10 | (1) |
|
1.3.2 Structure of the Book |
|
|
10 | (15) |
|
|
15 | (20) |
|
2.1 Context-free grammars |
|
|
15 | (3) |
|
2.2 Parsing algorithms and schemata |
|
|
18 | (7) |
|
2.3 The formalism of parsing schemata |
|
|
25 | (7) |
|
|
25 | (1) |
|
2.3.2 Parsing systems and parsing schemata |
|
|
26 | (4) |
|
2.3.3 Correctness of parsing schemata |
|
|
30 | (1) |
|
2.3.4 Relations betweeen parsing schemata |
|
|
30 | (2) |
|
2.4 Advantages of parsing schemata |
|
|
32 | (3) |
|
Compiling and Executing Parsing Schemata |
|
|
35 | (66) |
|
3 A compiler for parsing schemata |
|
|
37 | (26) |
|
|
37 | (4) |
|
|
39 | (1) |
|
|
40 | (1) |
|
|
41 | (1) |
|
|
42 | (2) |
|
|
44 | (4) |
|
3.5 The code generation process |
|
|
48 | (5) |
|
|
48 | (2) |
|
3.5.2 Deduction step classes |
|
|
50 | (1) |
|
3.5.3 Deducation step code generation |
|
|
51 | (1) |
|
3.5.4 Search specifications |
|
|
52 | (1) |
|
|
53 | (7) |
|
3.6.1 Static analysis and index descriptors |
|
|
54 | (3) |
|
3.6.2 Generation of indexing code |
|
|
57 | (3) |
|
3.6.3 Deduction step indexing |
|
|
60 | (1) |
|
|
60 | (3) |
|
4 Practical complexity of constituency parsers |
|
|
63 | (38) |
|
4.1 Parsing natural language with CFGs |
|
|
64 | (6) |
|
|
70 | (6) |
|
4.2.1 Tree-adjoining grammars |
|
|
70 | (3) |
|
4.2.2 Substitution and adjunction |
|
|
73 | (2) |
|
|
75 | (1) |
|
4.3 Parsing schemata for TAG |
|
|
76 | (2) |
|
4.4 Parsing schemata fior the XTAG English grammar |
|
|
78 | (8) |
|
|
79 | (1) |
|
4.4.2 Feature structure unification |
|
|
80 | (3) |
|
|
83 | (3) |
|
4.5 Comparing several parsers for the XTAG grammar |
|
|
86 | (3) |
|
4.6 Parsing with artifically-generated TAGs |
|
|
89 | (7) |
|
4.7 Overhead of TAG parsing over CFG parsing |
|
|
96 | (3) |
|
|
99 | (2) |
|
Parsing Schemata for Error-Repair Parsers |
|
|
101 | (60) |
|
5 Error-repair parsing schemata |
|
|
103 | (28) |
|
|
103 | (1) |
|
5.2 Error repair in parsing schemata |
|
|
104 | (7) |
|
5.2.1 The formalism of error-repair parsing schemata |
|
|
105 | (3) |
|
5.2.2 A tree distance for edit distance-based repair |
|
|
108 | (3) |
|
5.3 Lyon's error-repair parser |
|
|
111 | (10) |
|
|
113 | (8) |
|
5.4 Obtaining minimal distance parses |
|
|
121 | (3) |
|
5.5 Global and regional error repair |
|
|
124 | (5) |
|
5.5.1 Performance of global and regional parsers |
|
|
128 | (1) |
|
|
129 | (2) |
|
6 Transforming standard parsers into error-repair parsers |
|
|
131 | (30) |
|
6.1 From standard parsers to error-repair parsers |
|
|
131 | (4) |
|
6.1.1 Outline of the transformation |
|
|
132 | (3) |
|
6.2 Formal description of the error-repair transformation |
|
|
135 | (8) |
|
6.2.1 Some properties of trees and items |
|
|
135 | (2) |
|
6.2.2 Some properties of deduction steps |
|
|
137 | (2) |
|
6.2.3 The error-repair transformation |
|
|
139 | (4) |
|
6.3 Proof of correctness of the error-repair transformation |
|
|
143 | (12) |
|
6.3.1 Proof of Theorem 6.1 |
|
|
145 | (3) |
|
6.3.2 Proof of Theorem 6.2 |
|
|
148 | (7) |
|
6.4 Optimising the results of the transformation |
|
|
155 | (3) |
|
|
158 | (3) |
|
Parsing Schemata for Dependency Parsers |
|
|
161 | (84) |
|
7 Dependency parsig schemata |
|
|
163 | (44) |
|
|
163 | (2) |
|
7.2 The formalism of dependency parsing schemata |
|
|
165 | (4) |
|
7.3 Parsing schemata for projective dependency parsers |
|
|
169 | (11) |
|
|
169 | (2) |
|
|
171 | (1) |
|
7.3.3 Eisner and Satta (1999) |
|
|
172 | (1) |
|
7.3.4 Yamada and Matsumoto (2003) |
|
|
173 | (1) |
|
7.3.5 Lombardo and Lesmo (1996) and other Earley-based parsers |
|
|
174 | (2) |
|
|
176 | (4) |
|
7.3.7 Covington's projective parser (Covington, 2001) |
|
|
180 | (1) |
|
7.4 Relations between dependency parsers |
|
|
180 | (4) |
|
7.4.1 Yamada and Matsumoto (2003) sr→ Eisner (1996) |
|
|
181 | (1) |
|
7.4.2 Eisner and Satta (1999) sr→ Eisner (1996) |
|
|
182 | (1) |
|
|
183 | (1) |
|
7.5 Proving the correctness of dependency parsers |
|
|
184 | (2) |
|
7.5.1 Eisner and Satta (1999) is correct |
|
|
184 | (1) |
|
7.5.2 Yamada and Matsumoto (2003) is correct |
|
|
185 | (1) |
|
7.5.3 Eisner (1996) is correct |
|
|
186 | (1) |
|
7.6 Parsing schemata for non-projective dependency parsers |
|
|
186 | (7) |
|
7.6.1 Pseudo-projectivity |
|
|
187 | (1) |
|
7.6.2 Attardi (2006) and the MHk parser |
|
|
187 | (3) |
|
7.6.3 MST parser (McDonald et al., 2005b) |
|
|
190 | (2) |
|
7.6.4 Covington's non-projective parser (Covington, 1990;2001) |
|
|
192 | (1) |
|
7.7 Parsing schemata for Link Grammar parsers |
|
|
193 | (11) |
|
7.7.1 Sleator and Temperley's LG parser |
|
|
196 | (2) |
|
7.7.2 Adapting projective dependency parsers to LG |
|
|
198 | (2) |
|
7.7.3 Eisner (1996) for LG |
|
|
200 | (1) |
|
7.7.4 Eisner and Satta (1999) for LG |
|
|
201 | (2) |
|
7.7.5 Yamada and Matsumoto (2003) for LG |
|
|
203 | (1) |
|
|
204 | (3) |
|
8 Mildly non-projective dependency parsing |
|
|
207 | (38) |
|
|
207 | (2) |
|
|
209 | (2) |
|
|
211 | (16) |
|
|
211 | (3) |
|
8.3.2 Proof of correctness for WG1 |
|
|
214 | (12) |
|
8.3.3 Computational complexity of WG1 |
|
|
226 | (1) |
|
|
227 | (4) |
|
|
227 | (3) |
|
8.4.2 Proof of correctness for WGk |
|
|
230 | (1) |
|
8.4.3 Computational complexity of WGk |
|
|
230 | (1) |
|
8.5 Parsing ill-nested structures |
|
|
231 | (12) |
|
8.5.1 The MG1 and MGk parsers |
|
|
231 | (3) |
|
|
234 | (1) |
|
8.5.3 Proof of correctness for MGk |
|
|
234 | (7) |
|
8.5.4 Mildly ill-nested dependency structures |
|
|
241 | (2) |
|
|
243 | (2) |
|
|
245 | (8) |
|
|
247 | (6) |
|
|
250 | (3) |
List of Acronyms |
|
253 | (2) |
Bibliography |
|
255 | (14) |
Index |
|
269 | |