Mercurial > cpython-lru_cache-weakref
annotate Parser/parser.c @ 1590:ac2e5cc29949 legacy-trunk
Added tests for missing host to open_http and open_gopher
| author | Guido van Rossum <guido@python.org> |
|---|---|
| date | Mon, 18 Apr 1994 09:39:56 +0000 |
| parents | 1cabc2b6c970 |
| children | b724599401ff |
| rev | line source |
|---|---|
| 145 | 1 /*********************************************************** |
|
1257
1cabc2b6c970
* Changed all copyright messages to include 1993.
Guido van Rossum <guido@python.org>
parents:
1027
diff
changeset
|
2 Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum, |
|
1cabc2b6c970
* Changed all copyright messages to include 1993.
Guido van Rossum <guido@python.org>
parents:
1027
diff
changeset
|
3 Amsterdam, The Netherlands. |
| 145 | 4 |
| 5 All Rights Reserved | |
| 6 | |
| 7 Permission to use, copy, modify, and distribute this software and its | |
| 8 documentation for any purpose and without fee is hereby granted, | |
| 9 provided that the above copyright notice appear in all copies and that | |
| 10 both that copyright notice and this permission notice appear in | |
| 11 supporting documentation, and that the names of Stichting Mathematisch | |
| 12 Centrum or CWI not be used in advertising or publicity pertaining to | |
| 13 distribution of the software without specific, written prior permission. | |
| 14 | |
| 15 STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO | |
| 16 THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND | |
| 17 FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE | |
| 18 FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | |
| 19 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | |
| 20 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT | |
| 21 OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |
| 22 | |
| 23 ******************************************************************/ | |
| 24 | |
| 6 | 25 /* Parser implementation */ |
| 26 | |
| 27 /* For a description, see the comments at end of this file */ | |
| 28 | |
| 29 /* XXX To do: error recovery */ | |
| 30 | |
| 86 | 31 #include "pgenheaders.h" |
| 6 | 32 #include "assert.h" |
| 33 #include "token.h" | |
| 34 #include "grammar.h" | |
| 35 #include "node.h" | |
| 36 #include "parser.h" | |
| 37 #include "errcode.h" | |
| 38 | |
| 39 | |
| 40 #ifdef DEBUG | |
| 86 | 41 extern int debugging; |
| 6 | 42 #define D(x) if (!debugging); else x |
| 43 #else | |
| 44 #define D(x) | |
| 45 #endif | |
| 46 | |
| 47 | |
| 48 /* STACK DATA TYPE */ | |
| 49 | |
| 50 static void s_reset PROTO((stack *)); | |
| 51 | |
| 52 static void | |
| 53 s_reset(s) | |
| 54 stack *s; | |
| 55 { | |
| 56 s->s_top = &s->s_base[MAXSTACK]; | |
| 57 } | |
| 58 | |
| 59 #define s_empty(s) ((s)->s_top == &(s)->s_base[MAXSTACK]) | |
| 60 | |
| 61 static int s_push PROTO((stack *, dfa *, node *)); | |
| 62 | |
| 63 static int | |
| 64 s_push(s, d, parent) | |
| 65 register stack *s; | |
| 66 dfa *d; | |
| 67 node *parent; | |
| 68 { | |
| 69 register stackentry *top; | |
| 70 if (s->s_top == s->s_base) { | |
| 71 fprintf(stderr, "s_push: parser stack overflow\n"); | |
| 72 return -1; | |
| 73 } | |
| 74 top = --s->s_top; | |
| 75 top->s_dfa = d; | |
| 76 top->s_parent = parent; | |
| 77 top->s_state = 0; | |
| 78 return 0; | |
| 79 } | |
| 80 | |
| 81 #ifdef DEBUG | |
| 82 | |
| 83 static void s_pop PROTO((stack *)); | |
| 84 | |
| 85 static void | |
| 86 s_pop(s) | |
| 87 register stack *s; | |
| 88 { | |
| 89 if (s_empty(s)) { | |
| 90 fprintf(stderr, "s_pop: parser stack underflow -- FATAL\n"); | |
| 91 abort(); | |
| 92 } | |
| 93 s->s_top++; | |
| 94 } | |
| 95 | |
| 96 #else /* !DEBUG */ | |
| 97 | |
| 98 #define s_pop(s) (s)->s_top++ | |
| 99 | |
| 100 #endif | |
| 101 | |
| 102 | |
| 103 /* PARSER CREATION */ | |
| 104 | |
| 105 parser_state * | |
| 106 newparser(g, start) | |
| 107 grammar *g; | |
| 108 int start; | |
| 109 { | |
| 110 parser_state *ps; | |
| 111 | |
| 112 if (!g->g_accel) | |
| 113 addaccelerators(g); | |
| 114 ps = NEW(parser_state, 1); | |
| 115 if (ps == NULL) | |
| 116 return NULL; | |
| 117 ps->p_grammar = g; | |
| 86 | 118 ps->p_tree = newtree(start); |
| 6 | 119 if (ps->p_tree == NULL) { |
| 120 DEL(ps); | |
| 121 return NULL; | |
| 122 } | |
| 123 s_reset(&ps->p_stack); | |
| 124 (void) s_push(&ps->p_stack, finddfa(g, start), ps->p_tree); | |
| 125 return ps; | |
| 126 } | |
| 127 | |
| 128 void | |
| 129 delparser(ps) | |
| 130 parser_state *ps; | |
| 131 { | |
|
79
6c43e5476de6
Free parse tree when deleting parser.
Guido van Rossum <guido@python.org>
parents:
6
diff
changeset
|
132 /* 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
|
133 you must set p_tree to NULL before calling delparser! */ |
| 86 | 134 freetree(ps->p_tree); |
| 6 | 135 DEL(ps); |
| 136 } | |
| 137 | |
| 138 | |
| 139 /* PARSER STACK OPERATIONS */ | |
| 140 | |
| 86 | 141 static int shift PROTO((stack *, int, char *, int, int)); |
| 6 | 142 |
| 143 static int | |
| 86 | 144 shift(s, type, str, newstate, lineno) |
| 6 | 145 register stack *s; |
| 146 int type; | |
| 147 char *str; | |
| 148 int newstate; | |
| 86 | 149 int lineno; |
| 6 | 150 { |
| 151 assert(!s_empty(s)); | |
| 86 | 152 if (addchild(s->s_top->s_parent, type, str, lineno) == NULL) { |
| 6 | 153 fprintf(stderr, "shift: no mem in addchild\n"); |
| 154 return -1; | |
| 155 } | |
| 156 s->s_top->s_state = newstate; | |
| 157 return 0; | |
| 158 } | |
| 159 | |
| 86 | 160 static int push PROTO((stack *, int, dfa *, int, int)); |
| 6 | 161 |
| 162 static int | |
| 86 | 163 push(s, type, d, newstate, lineno) |
| 6 | 164 register stack *s; |
| 165 int type; | |
| 166 dfa *d; | |
| 167 int newstate; | |
| 86 | 168 int lineno; |
| 6 | 169 { |
| 170 register node *n; | |
| 171 n = s->s_top->s_parent; | |
| 172 assert(!s_empty(s)); | |
| 86 | 173 if (addchild(n, type, (char *)NULL, lineno) == NULL) { |
| 6 | 174 fprintf(stderr, "push: no mem in addchild\n"); |
| 175 return -1; | |
| 176 } | |
| 177 s->s_top->s_state = newstate; | |
| 178 return s_push(s, d, CHILD(n, NCH(n)-1)); | |
| 179 } | |
| 180 | |
| 181 | |
| 182 /* PARSER PROPER */ | |
| 183 | |
| 184 static int classify PROTO((grammar *, int, char *)); | |
| 185 | |
| 186 static int | |
| 187 classify(g, type, str) | |
| 188 grammar *g; | |
| 189 register int type; | |
| 190 char *str; | |
| 191 { | |
| 192 register int n = g->g_ll.ll_nlabels; | |
| 193 | |
| 194 if (type == NAME) { | |
| 195 register char *s = str; | |
| 196 register label *l = g->g_ll.ll_label; | |
| 197 register int i; | |
| 198 for (i = n; i > 0; i--, l++) { | |
| 199 if (l->lb_type == NAME && l->lb_str != NULL && | |
| 200 l->lb_str[0] == s[0] && | |
| 201 strcmp(l->lb_str, s) == 0) { | |
| 202 D(printf("It's a keyword\n")); | |
| 203 return n - i; | |
| 204 } | |
| 205 } | |
| 206 } | |
| 207 | |
| 208 { | |
| 209 register label *l = g->g_ll.ll_label; | |
| 210 register int i; | |
| 211 for (i = n; i > 0; i--, l++) { | |
| 212 if (l->lb_type == type && l->lb_str == NULL) { | |
| 213 D(printf("It's a token we know\n")); | |
| 214 return n - i; | |
| 215 } | |
| 216 } | |
| 217 } | |
| 218 | |
| 219 D(printf("Illegal token\n")); | |
| 220 return -1; | |
| 221 } | |
| 222 | |
| 223 int | |
| 86 | 224 addtoken(ps, type, str, lineno) |
| 6 | 225 register parser_state *ps; |
| 226 register int type; | |
| 227 char *str; | |
| 86 | 228 int lineno; |
| 6 | 229 { |
| 230 register int ilabel; | |
| 231 | |
| 232 D(printf("Token %s/'%s' ... ", tok_name[type], str)); | |
| 233 | |
| 234 /* Find out which label this token is */ | |
| 235 ilabel = classify(ps->p_grammar, type, str); | |
| 236 if (ilabel < 0) | |
| 237 return E_SYNTAX; | |
| 238 | |
| 239 /* Loop until the token is shifted or an error occurred */ | |
| 240 for (;;) { | |
| 241 /* Fetch the current dfa and state */ | |
| 242 register dfa *d = ps->p_stack.s_top->s_dfa; | |
| 243 register state *s = &d->d_state[ps->p_stack.s_top->s_state]; | |
| 244 | |
| 245 D(printf(" DFA '%s', state %d:", | |
| 246 d->d_name, ps->p_stack.s_top->s_state)); | |
| 247 | |
| 248 /* Check accelerator */ | |
| 249 if (s->s_lower <= ilabel && ilabel < s->s_upper) { | |
| 250 register int x = s->s_accel[ilabel - s->s_lower]; | |
| 251 if (x != -1) { | |
| 252 if (x & (1<<7)) { | |
| 253 /* Push non-terminal */ | |
| 254 int nt = (x >> 8) + NT_OFFSET; | |
| 255 int arrow = x & ((1<<7)-1); | |
| 256 dfa *d1 = finddfa(ps->p_grammar, nt); | |
| 86 | 257 if (push(&ps->p_stack, nt, d1, |
| 258 arrow, lineno) < 0) { | |
| 6 | 259 D(printf(" MemError: push.\n")); |
| 260 return E_NOMEM; | |
| 261 } | |
| 262 D(printf(" Push ...\n")); | |
| 263 continue; | |
| 264 } | |
| 265 | |
| 266 /* Shift the token */ | |
| 86 | 267 if (shift(&ps->p_stack, type, str, |
| 268 x, lineno) < 0) { | |
| 6 | 269 D(printf(" MemError: shift.\n")); |
| 270 return E_NOMEM; | |
| 271 } | |
| 272 D(printf(" Shift.\n")); | |
| 273 /* Pop while we are in an accept-only state */ | |
| 274 while (s = &d->d_state | |
| 275 [ps->p_stack.s_top->s_state], | |
| 276 s->s_accept && s->s_narcs == 1) { | |
| 277 D(printf(" Direct pop.\n")); | |
| 278 s_pop(&ps->p_stack); | |
| 279 if (s_empty(&ps->p_stack)) { | |
| 280 D(printf(" ACCEPT.\n")); | |
| 281 return E_DONE; | |
| 282 } | |
| 283 d = ps->p_stack.s_top->s_dfa; | |
| 284 } | |
| 285 return E_OK; | |
| 286 } | |
| 287 } | |
| 288 | |
| 289 if (s->s_accept) { | |
| 290 /* Pop this dfa and try again */ | |
| 291 s_pop(&ps->p_stack); | |
| 292 D(printf(" Pop ...\n")); | |
| 293 if (s_empty(&ps->p_stack)) { | |
| 294 D(printf(" Error: bottom of stack.\n")); | |
| 295 return E_SYNTAX; | |
| 296 } | |
| 297 continue; | |
| 298 } | |
| 299 | |
| 300 /* Stuck, report syntax error */ | |
| 301 D(printf(" Error.\n")); | |
| 302 return E_SYNTAX; | |
| 303 } | |
| 304 } | |
| 305 | |
| 306 | |
| 307 #ifdef DEBUG | |
| 308 | |
| 309 /* DEBUG OUTPUT */ | |
| 310 | |
| 311 void | |
| 312 dumptree(g, n) | |
| 313 grammar *g; | |
| 314 node *n; | |
| 315 { | |
| 316 int i; | |
| 317 | |
| 318 if (n == NULL) | |
| 319 printf("NIL"); | |
| 320 else { | |
| 321 label l; | |
| 322 l.lb_type = TYPE(n); | |
|
1027
513940eb4d7b
Correct debug printing code
Guido van Rossum <guido@python.org>
parents:
795
diff
changeset
|
323 l.lb_str = STR(n); |
| 6 | 324 printf("%s", labelrepr(&l)); |
| 325 if (ISNONTERMINAL(TYPE(n))) { | |
| 326 printf("("); | |
| 327 for (i = 0; i < NCH(n); i++) { | |
| 328 if (i > 0) | |
| 329 printf(","); | |
| 330 dumptree(g, CHILD(n, i)); | |
| 331 } | |
| 332 printf(")"); | |
| 333 } | |
| 334 } | |
| 335 } | |
| 336 | |
| 337 void | |
| 338 showtree(g, n) | |
| 339 grammar *g; | |
| 340 node *n; | |
| 341 { | |
| 342 int i; | |
| 343 | |
| 344 if (n == NULL) | |
| 345 return; | |
| 346 if (ISNONTERMINAL(TYPE(n))) { | |
| 347 for (i = 0; i < NCH(n); i++) | |
| 348 showtree(g, CHILD(n, i)); | |
| 349 } | |
| 350 else if (ISTERMINAL(TYPE(n))) { | |
| 351 printf("%s", tok_name[TYPE(n)]); | |
| 352 if (TYPE(n) == NUMBER || TYPE(n) == NAME) | |
| 353 printf("(%s)", STR(n)); | |
| 354 printf(" "); | |
| 355 } | |
| 356 else | |
| 357 printf("? "); | |
| 358 } | |
| 359 | |
| 360 void | |
| 361 printtree(ps) | |
| 362 parser_state *ps; | |
| 363 { | |
| 364 if (debugging) { | |
| 365 printf("Parse tree:\n"); | |
| 366 dumptree(ps->p_grammar, ps->p_tree); | |
| 367 printf("\n"); | |
| 368 printf("Tokens:\n"); | |
| 369 showtree(ps->p_grammar, ps->p_tree); | |
| 370 printf("\n"); | |
| 371 } | |
| 372 printf("Listing:\n"); | |
| 373 listtree(ps->p_tree); | |
| 374 printf("\n"); | |
| 375 } | |
| 376 | |
| 377 #endif /* DEBUG */ | |
| 378 | |
| 379 /* | |
| 380 | |
| 381 Description | |
| 382 ----------- | |
| 383 | |
| 384 The parser's interface is different than usual: the function addtoken() | |
| 385 must be called for each token in the input. This makes it possible to | |
| 386 turn it into an incremental parsing system later. The parsing system | |
| 387 constructs a parse tree as it goes. | |
| 388 | |
| 389 A parsing rule is represented as a Deterministic Finite-state Automaton | |
| 390 (DFA). A node in a DFA represents a state of the parser; an arc represents | |
| 391 a transition. Transitions are either labeled with terminal symbols or | |
| 392 with non-terminals. When the parser decides to follow an arc labeled | |
| 393 with a non-terminal, it is invoked recursively with the DFA representing | |
| 394 the parsing rule for that as its initial state; when that DFA accepts, | |
| 395 the parser that invoked it continues. The parse tree constructed by the | |
| 396 recursively called parser is inserted as a child in the current parse tree. | |
| 397 | |
| 398 The DFA's can be constructed automatically from a more conventional | |
| 399 language description. An extended LL(1) grammar (ELL(1)) is suitable. | |
| 400 Certain restrictions make the parser's life easier: rules that can produce | |
| 401 the empty string should be outlawed (there are other ways to put loops | |
| 402 or optional parts in the language). To avoid the need to construct | |
| 403 FIRST sets, we can require that all but the last alternative of a rule | |
| 404 (really: arc going out of a DFA's state) must begin with a terminal | |
| 405 symbol. | |
| 406 | |
| 407 As an example, consider this grammar: | |
| 408 | |
| 409 expr: term (OP term)* | |
| 410 term: CONSTANT | '(' expr ')' | |
| 411 | |
| 412 The DFA corresponding to the rule for expr is: | |
| 413 | |
| 414 ------->.---term-->.-------> | |
| 415 ^ | | |
| 416 | | | |
| 417 \----OP----/ | |
| 418 | |
| 419 The parse tree generated for the input a+b is: | |
| 420 | |
| 421 (expr: (term: (NAME: a)), (OP: +), (term: (NAME: b))) | |
| 422 | |
| 423 */ |