Mercurial > cpython-lru_cache-weakref
annotate Parser/parser.c @ 13778:f6e4a9dd67cd legacy-trunk
Rename the "parser" package to "parsers" to be compatible with the PyXML
project.
| author | Fred Drake <fdrake@acm.org> |
|---|---|
| date | Mon, 31 Jul 2000 23:59:54 +0000 |
| parents | e78153e179fb |
| children | 6f6f965c5e2d |
| rev | line source |
|---|---|
| 145 | 1 /*********************************************************** |
|
13255
916fb024ce94
Change copyright notice.
Guido van Rossum <guido@python.org>
parents:
12970
diff
changeset
|
2 Copyright (c) 2000, BeOpen.com. |
|
916fb024ce94
Change copyright notice.
Guido van Rossum <guido@python.org>
parents:
12970
diff
changeset
|
3 Copyright (c) 1995-2000, Corporation for National Research Initiatives. |
|
916fb024ce94
Change copyright notice.
Guido van Rossum <guido@python.org>
parents:
12970
diff
changeset
|
4 Copyright (c) 1990-1995, Stichting Mathematisch Centrum. |
|
916fb024ce94
Change copyright notice.
Guido van Rossum <guido@python.org>
parents:
12970
diff
changeset
|
5 All rights reserved. |
| 145 | 6 |
|
13255
916fb024ce94
Change copyright notice.
Guido van Rossum <guido@python.org>
parents:
12970
diff
changeset
|
7 See the file "Misc/COPYRIGHT" for information on usage and |
|
916fb024ce94
Change copyright notice.
Guido van Rossum <guido@python.org>
parents:
12970
diff
changeset
|
8 redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES. |
| 145 | 9 ******************************************************************/ |
| 10 | |
| 6 | 11 /* Parser implementation */ |
| 12 | |
| 13 /* For a description, see the comments at end of this file */ | |
| 14 | |
| 15 /* XXX To do: error recovery */ | |
| 16 | |
| 86 | 17 #include "pgenheaders.h" |
| 6 | 18 #include "assert.h" |
| 19 #include "token.h" | |
| 20 #include "grammar.h" | |
| 21 #include "node.h" | |
| 22 #include "parser.h" | |
| 23 #include "errcode.h" | |
| 24 | |
| 25 | |
|
4839
4567e158d20c
Rename DEBUG macro to Py_DEBUG
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
26 #ifdef Py_DEBUG |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
27 extern int Py_DebugFlag; |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
28 #define D(x) if (!Py_DebugFlag); else x |
| 6 | 29 #else |
| 30 #define D(x) | |
| 31 #endif | |
| 32 | |
| 33 | |
| 34 /* STACK DATA TYPE */ | |
| 35 | |
|
13447
a89f7f268de4
Nuke all remaining occurrences of Py_PROTO and Py_FPROTO.
Tim Peters <tim.peters@gmail.com>
parents:
13256
diff
changeset
|
36 static void s_reset(stack *); |
| 6 | 37 |
| 38 static void | |
| 13659 | 39 s_reset(stack *s) |
| 6 | 40 { |
| 41 s->s_top = &s->s_base[MAXSTACK]; | |
| 42 } | |
| 43 | |
| 44 #define s_empty(s) ((s)->s_top == &(s)->s_base[MAXSTACK]) | |
| 45 | |
| 46 static int | |
| 13659 | 47 s_push(register stack *s, dfa *d, node *parent) |
| 6 | 48 { |
| 49 register stackentry *top; | |
| 50 if (s->s_top == s->s_base) { | |
| 51 fprintf(stderr, "s_push: parser stack overflow\n"); | |
| 52 return -1; | |
| 53 } | |
| 54 top = --s->s_top; | |
| 55 top->s_dfa = d; | |
| 56 top->s_parent = parent; | |
| 57 top->s_state = 0; | |
| 58 return 0; | |
| 59 } | |
| 60 | |
|
4839
4567e158d20c
Rename DEBUG macro to Py_DEBUG
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
61 #ifdef Py_DEBUG |
| 6 | 62 |
| 63 static void | |
| 13659 | 64 s_pop(register stack *s) |
| 6 | 65 { |
|
2044
281e40652e23
Parser/tokenizer.c (tok_nextc): zap tok->buf after freeing;
Guido van Rossum <guido@python.org>
parents:
1848
diff
changeset
|
66 if (s_empty(s)) |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
67 Py_FatalError("s_pop: parser stack underflow -- FATAL"); |
| 6 | 68 s->s_top++; |
| 69 } | |
| 70 | |
|
4839
4567e158d20c
Rename DEBUG macro to Py_DEBUG
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
71 #else /* !Py_DEBUG */ |
| 6 | 72 |
| 73 #define s_pop(s) (s)->s_top++ | |
| 74 | |
| 75 #endif | |
| 76 | |
| 77 | |
| 78 /* PARSER CREATION */ | |
| 79 | |
| 80 parser_state * | |
| 13659 | 81 PyParser_New(grammar *g, int start) |
| 6 | 82 { |
| 83 parser_state *ps; | |
| 84 | |
| 85 if (!g->g_accel) | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
86 PyGrammar_AddAccelerators(g); |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
87 ps = PyMem_NEW(parser_state, 1); |
| 6 | 88 if (ps == NULL) |
| 89 return NULL; | |
| 90 ps->p_grammar = g; | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
91 ps->p_tree = PyNode_New(start); |
| 6 | 92 if (ps->p_tree == NULL) { |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
93 PyMem_DEL(ps); |
| 6 | 94 return NULL; |
| 95 } | |
| 96 s_reset(&ps->p_stack); | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
97 (void) s_push(&ps->p_stack, PyGrammar_FindDFA(g, start), ps->p_tree); |
| 6 | 98 return ps; |
| 99 } | |
| 100 | |
| 101 void | |
| 13659 | 102 PyParser_Delete(parser_state *ps) |
| 6 | 103 { |
|
79
6c43e5476de6
Free parse tree when deleting parser.
Guido van Rossum <guido@python.org>
parents:
6
diff
changeset
|
104 /* NB If you want to save the parse tree, |
|
6c43e5476de6
Free parse tree when deleting parser.
Guido van Rossum <guido@python.org>
parents:
6
diff
changeset
|
105 you must set p_tree to NULL before calling delparser! */ |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
106 PyNode_Free(ps->p_tree); |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
107 PyMem_DEL(ps); |
| 6 | 108 } |
| 109 | |
| 110 | |
| 111 /* PARSER STACK OPERATIONS */ | |
| 112 | |
| 113 static int | |
| 13659 | 114 shift(register stack *s, int type, char *str, int newstate, int lineno) |
| 6 | 115 { |
|
12970
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
116 int err; |
| 6 | 117 assert(!s_empty(s)); |
|
12970
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
118 err = PyNode_AddChild(s->s_top->s_parent, type, str, lineno); |
|
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
119 if (err) |
|
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
120 return err; |
| 6 | 121 s->s_top->s_state = newstate; |
| 122 return 0; | |
| 123 } | |
| 124 | |
| 125 static int | |
| 13659 | 126 push(register stack *s, int type, dfa *d, int newstate, int lineno) |
| 6 | 127 { |
|
12970
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
128 int err; |
| 6 | 129 register node *n; |
| 130 n = s->s_top->s_parent; | |
| 131 assert(!s_empty(s)); | |
|
12970
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
132 err = PyNode_AddChild(n, type, (char *)NULL, lineno); |
|
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
133 if (err) |
|
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
134 return err; |
| 6 | 135 s->s_top->s_state = newstate; |
| 136 return s_push(s, d, CHILD(n, NCH(n)-1)); | |
| 137 } | |
| 138 | |
| 139 | |
| 140 /* PARSER PROPER */ | |
| 141 | |
| 142 static int | |
| 13659 | 143 classify(grammar *g, int type, char *str) |
| 6 | 144 { |
| 145 register int n = g->g_ll.ll_nlabels; | |
| 146 | |
| 147 if (type == NAME) { | |
| 148 register char *s = str; | |
| 149 register label *l = g->g_ll.ll_label; | |
| 150 register int i; | |
| 151 for (i = n; i > 0; i--, l++) { | |
| 152 if (l->lb_type == NAME && l->lb_str != NULL && | |
| 153 l->lb_str[0] == s[0] && | |
| 154 strcmp(l->lb_str, s) == 0) { | |
| 155 D(printf("It's a keyword\n")); | |
| 156 return n - i; | |
| 157 } | |
| 158 } | |
| 159 } | |
| 160 | |
| 161 { | |
| 162 register label *l = g->g_ll.ll_label; | |
| 163 register int i; | |
| 164 for (i = n; i > 0; i--, l++) { | |
| 165 if (l->lb_type == type && l->lb_str == NULL) { | |
| 166 D(printf("It's a token we know\n")); | |
| 167 return n - i; | |
| 168 } | |
| 169 } | |
| 170 } | |
| 171 | |
| 172 D(printf("Illegal token\n")); | |
| 173 return -1; | |
| 174 } | |
| 175 | |
| 176 int | |
| 13659 | 177 PyParser_AddToken(register parser_state *ps, register int type, char *str, |
| 178 int lineno, int *expected_ret) | |
| 6 | 179 { |
| 180 register int ilabel; | |
|
12970
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
181 int err; |
| 6 | 182 |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
183 D(printf("Token %s/'%s' ... ", _PyParser_TokenNames[type], str)); |
| 6 | 184 |
| 185 /* Find out which label this token is */ | |
| 186 ilabel = classify(ps->p_grammar, type, str); | |
| 187 if (ilabel < 0) | |
| 188 return E_SYNTAX; | |
| 189 | |
| 190 /* Loop until the token is shifted or an error occurred */ | |
| 191 for (;;) { | |
| 192 /* Fetch the current dfa and state */ | |
| 193 register dfa *d = ps->p_stack.s_top->s_dfa; | |
| 194 register state *s = &d->d_state[ps->p_stack.s_top->s_state]; | |
| 195 | |
| 196 D(printf(" DFA '%s', state %d:", | |
| 197 d->d_name, ps->p_stack.s_top->s_state)); | |
| 198 | |
| 199 /* Check accelerator */ | |
| 200 if (s->s_lower <= ilabel && ilabel < s->s_upper) { | |
| 201 register int x = s->s_accel[ilabel - s->s_lower]; | |
| 202 if (x != -1) { | |
| 203 if (x & (1<<7)) { | |
| 204 /* Push non-terminal */ | |
| 205 int nt = (x >> 8) + NT_OFFSET; | |
| 206 int arrow = x & ((1<<7)-1); | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
207 dfa *d1 = PyGrammar_FindDFA( |
|
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
208 ps->p_grammar, nt); |
|
12970
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
209 if ((err = push(&ps->p_stack, nt, d1, |
|
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
210 arrow, lineno)) > 0) { |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
211 D(printf(" MemError: push\n")); |
|
12970
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
212 return err; |
| 6 | 213 } |
| 214 D(printf(" Push ...\n")); | |
| 215 continue; | |
| 216 } | |
| 217 | |
| 218 /* Shift the token */ | |
|
12970
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
219 if ((err = shift(&ps->p_stack, type, str, |
|
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
220 x, lineno)) > 0) { |
| 6 | 221 D(printf(" MemError: shift.\n")); |
|
12970
63436719d12e
Add new parser error code, E_OVERFLOW. This error is returned when
Jeremy Hylton <jeremy@alum.mit.edu>
parents:
5379
diff
changeset
|
222 return err; |
| 6 | 223 } |
| 224 D(printf(" Shift.\n")); | |
| 225 /* Pop while we are in an accept-only state */ | |
| 226 while (s = &d->d_state | |
| 227 [ps->p_stack.s_top->s_state], | |
| 228 s->s_accept && s->s_narcs == 1) { | |
| 229 D(printf(" Direct pop.\n")); | |
| 230 s_pop(&ps->p_stack); | |
| 231 if (s_empty(&ps->p_stack)) { | |
| 232 D(printf(" ACCEPT.\n")); | |
| 233 return E_DONE; | |
| 234 } | |
| 235 d = ps->p_stack.s_top->s_dfa; | |
| 236 } | |
| 237 return E_OK; | |
| 238 } | |
| 239 } | |
| 240 | |
| 241 if (s->s_accept) { | |
| 242 /* Pop this dfa and try again */ | |
| 243 s_pop(&ps->p_stack); | |
| 244 D(printf(" Pop ...\n")); | |
| 245 if (s_empty(&ps->p_stack)) { | |
| 246 D(printf(" Error: bottom of stack.\n")); | |
| 247 return E_SYNTAX; | |
| 248 } | |
| 249 continue; | |
| 250 } | |
| 251 | |
| 252 /* Stuck, report syntax error */ | |
| 253 D(printf(" Error.\n")); | |
|
13539
feab677269e0
Create two new exceptions: IndentationError and TabError. These are
Fred Drake <fdrake@acm.org>
parents:
13447
diff
changeset
|
254 if (expected_ret) { |
|
feab677269e0
Create two new exceptions: IndentationError and TabError. These are
Fred Drake <fdrake@acm.org>
parents:
13447
diff
changeset
|
255 if (s->s_lower == s->s_upper - 1) { |
|
feab677269e0
Create two new exceptions: IndentationError and TabError. These are
Fred Drake <fdrake@acm.org>
parents:
13447
diff
changeset
|
256 /* Only one possible expected token */ |
|
feab677269e0
Create two new exceptions: IndentationError and TabError. These are
Fred Drake <fdrake@acm.org>
parents:
13447
diff
changeset
|
257 *expected_ret = ps->p_grammar-> |
|
feab677269e0
Create two new exceptions: IndentationError and TabError. These are
Fred Drake <fdrake@acm.org>
parents:
13447
diff
changeset
|
258 g_ll.ll_label[s->s_lower].lb_type; |
|
feab677269e0
Create two new exceptions: IndentationError and TabError. These are
Fred Drake <fdrake@acm.org>
parents:
13447
diff
changeset
|
259 } |
|
feab677269e0
Create two new exceptions: IndentationError and TabError. These are
Fred Drake <fdrake@acm.org>
parents:
13447
diff
changeset
|
260 else |
|
feab677269e0
Create two new exceptions: IndentationError and TabError. These are
Fred Drake <fdrake@acm.org>
parents:
13447
diff
changeset
|
261 *expected_ret = -1; |
|
feab677269e0
Create two new exceptions: IndentationError and TabError. These are
Fred Drake <fdrake@acm.org>
parents:
13447
diff
changeset
|
262 } |
| 6 | 263 return E_SYNTAX; |
| 264 } | |
| 265 } | |
| 266 | |
| 267 | |
|
4839
4567e158d20c
Rename DEBUG macro to Py_DEBUG
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
268 #ifdef Py_DEBUG |
| 6 | 269 |
| 270 /* DEBUG OUTPUT */ | |
| 271 | |
| 272 void | |
| 13659 | 273 dumptree(grammar *g, node *n) |
| 6 | 274 { |
| 275 int i; | |
| 276 | |
| 277 if (n == NULL) | |
| 278 printf("NIL"); | |
| 279 else { | |
| 280 label l; | |
| 281 l.lb_type = TYPE(n); | |
|
1027
513940eb4d7b
Correct debug printing code
Guido van Rossum <guido@python.org>
parents:
795
diff
changeset
|
282 l.lb_str = STR(n); |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
283 printf("%s", PyGrammar_LabelRepr(&l)); |
| 6 | 284 if (ISNONTERMINAL(TYPE(n))) { |
| 285 printf("("); | |
| 286 for (i = 0; i < NCH(n); i++) { | |
| 287 if (i > 0) | |
| 288 printf(","); | |
| 289 dumptree(g, CHILD(n, i)); | |
| 290 } | |
| 291 printf(")"); | |
| 292 } | |
| 293 } | |
| 294 } | |
| 295 | |
| 296 void | |
| 13659 | 297 showtree(grammar *g, node *n) |
| 6 | 298 { |
| 299 int i; | |
| 300 | |
| 301 if (n == NULL) | |
| 302 return; | |
| 303 if (ISNONTERMINAL(TYPE(n))) { | |
| 304 for (i = 0; i < NCH(n); i++) | |
| 305 showtree(g, CHILD(n, i)); | |
| 306 } | |
| 307 else if (ISTERMINAL(TYPE(n))) { | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
308 printf("%s", _PyParser_TokenNames[TYPE(n)]); |
| 6 | 309 if (TYPE(n) == NUMBER || TYPE(n) == NAME) |
| 310 printf("(%s)", STR(n)); | |
| 311 printf(" "); | |
| 312 } | |
| 313 else | |
| 314 printf("? "); | |
| 315 } | |
| 316 | |
| 317 void | |
| 13659 | 318 printtree(parser_state *ps) |
| 6 | 319 { |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
320 if (Py_DebugFlag) { |
| 6 | 321 printf("Parse tree:\n"); |
| 322 dumptree(ps->p_grammar, ps->p_tree); | |
| 323 printf("\n"); | |
| 324 printf("Tokens:\n"); | |
| 325 showtree(ps->p_grammar, ps->p_tree); | |
| 326 printf("\n"); | |
| 327 } | |
| 328 printf("Listing:\n"); | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
329 PyNode_ListTree(ps->p_tree); |
| 6 | 330 printf("\n"); |
| 331 } | |
| 332 | |
|
4839
4567e158d20c
Rename DEBUG macro to Py_DEBUG
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
333 #endif /* Py_DEBUG */ |
| 6 | 334 |
| 335 /* | |
| 336 | |
| 337 Description | |
| 338 ----------- | |
| 339 | |
| 340 The parser's interface is different than usual: the function addtoken() | |
| 341 must be called for each token in the input. This makes it possible to | |
| 342 turn it into an incremental parsing system later. The parsing system | |
| 343 constructs a parse tree as it goes. | |
| 344 | |
| 345 A parsing rule is represented as a Deterministic Finite-state Automaton | |
| 346 (DFA). A node in a DFA represents a state of the parser; an arc represents | |
| 347 a transition. Transitions are either labeled with terminal symbols or | |
| 348 with non-terminals. When the parser decides to follow an arc labeled | |
| 349 with a non-terminal, it is invoked recursively with the DFA representing | |
| 350 the parsing rule for that as its initial state; when that DFA accepts, | |
| 351 the parser that invoked it continues. The parse tree constructed by the | |
| 352 recursively called parser is inserted as a child in the current parse tree. | |
| 353 | |
| 354 The DFA's can be constructed automatically from a more conventional | |
| 355 language description. An extended LL(1) grammar (ELL(1)) is suitable. | |
| 356 Certain restrictions make the parser's life easier: rules that can produce | |
| 357 the empty string should be outlawed (there are other ways to put loops | |
| 358 or optional parts in the language). To avoid the need to construct | |
| 359 FIRST sets, we can require that all but the last alternative of a rule | |
| 360 (really: arc going out of a DFA's state) must begin with a terminal | |
| 361 symbol. | |
| 362 | |
| 363 As an example, consider this grammar: | |
| 364 | |
| 365 expr: term (OP term)* | |
| 366 term: CONSTANT | '(' expr ')' | |
| 367 | |
| 368 The DFA corresponding to the rule for expr is: | |
| 369 | |
| 370 ------->.---term-->.-------> | |
| 371 ^ | | |
| 372 | | | |
| 373 \----OP----/ | |
| 374 | |
| 375 The parse tree generated for the input a+b is: | |
| 376 | |
| 377 (expr: (term: (NAME: a)), (OP: +), (term: (NAME: b))) | |
| 378 | |
| 379 */ |