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