Line data Source code
1 :
2 : /* Parser implementation */
3 :
4 : /* For a description, see the comments at end of this file */
5 :
6 : /* XXX To do: error recovery */
7 :
8 : #include "Python.h"
9 : #include "pgenheaders.h"
10 : #include "token.h"
11 : #include "grammar.h"
12 : #include "node.h"
13 : #include "parser.h"
14 : #include "errcode.h"
15 :
16 :
17 : #ifdef Py_DEBUG
18 : extern int Py_DebugFlag;
19 : #define D(x) if (!Py_DebugFlag); else x
20 : #else
21 : #define D(x)
22 : #endif
23 :
24 :
25 : /* STACK DATA TYPE */
26 :
27 : static void s_reset(stack *);
28 :
29 : static void
30 3 : s_reset(stack *s)
31 : {
32 3 : s->s_top = &s->s_base[MAXSTACK];
33 3 : }
34 :
35 : #define s_empty(s) ((s)->s_top == &(s)->s_base[MAXSTACK])
36 :
37 : static int
38 7424 : s_push(register stack *s, dfa *d, node *parent)
39 : {
40 : register stackentry *top;
41 7424 : if (s->s_top == s->s_base) {
42 0 : fprintf(stderr, "s_push: parser stack overflow\n");
43 0 : return E_NOMEM;
44 : }
45 7424 : top = --s->s_top;
46 7424 : top->s_dfa = d;
47 7424 : top->s_parent = parent;
48 7424 : top->s_state = 0;
49 7424 : return 0;
50 : }
51 :
52 : #ifdef Py_DEBUG
53 :
54 : static void
55 : s_pop(register stack *s)
56 : {
57 : if (s_empty(s))
58 : Py_FatalError("s_pop: parser stack underflow -- FATAL");
59 : s->s_top++;
60 : }
61 :
62 : #else /* !Py_DEBUG */
63 :
64 : #define s_pop(s) (s)->s_top++
65 :
66 : #endif
67 :
68 :
69 : /* PARSER CREATION */
70 :
71 : parser_state *
72 3 : PyParser_New(grammar *g, int start)
73 : {
74 : parser_state *ps;
75 :
76 3 : if (!g->g_accel)
77 1 : PyGrammar_AddAccelerators(g);
78 3 : ps = (parser_state *)PyMem_MALLOC(sizeof(parser_state));
79 3 : if (ps == NULL)
80 0 : return NULL;
81 3 : ps->p_grammar = g;
82 : #ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
83 3 : ps->p_flags = 0;
84 : #endif
85 3 : ps->p_tree = PyNode_New(start);
86 3 : if (ps->p_tree == NULL) {
87 0 : PyMem_FREE(ps);
88 0 : return NULL;
89 : }
90 3 : s_reset(&ps->p_stack);
91 3 : (void) s_push(&ps->p_stack, PyGrammar_FindDFA(g, start), ps->p_tree);
92 3 : return ps;
93 : }
94 :
95 : void
96 3 : PyParser_Delete(parser_state *ps)
97 : {
98 : /* NB If you want to save the parse tree,
99 : you must set p_tree to NULL before calling delparser! */
100 3 : PyNode_Free(ps->p_tree);
101 3 : PyMem_FREE(ps);
102 3 : }
103 :
104 :
105 : /* PARSER STACK OPERATIONS */
106 :
107 : static int
108 1823 : shift(register stack *s, int type, char *str, int newstate, int lineno, int col_offset)
109 : {
110 : int err;
111 : assert(!s_empty(s));
112 1823 : err = PyNode_AddChild(s->s_top->s_parent, type, str, lineno, col_offset);
113 1823 : if (err)
114 0 : return err;
115 1823 : s->s_top->s_state = newstate;
116 1823 : return 0;
117 : }
118 :
119 : static int
120 7421 : push(register stack *s, int type, dfa *d, int newstate, int lineno, int col_offset)
121 : {
122 : int err;
123 : register node *n;
124 7421 : n = s->s_top->s_parent;
125 : assert(!s_empty(s));
126 7421 : err = PyNode_AddChild(n, type, (char *)NULL, lineno, col_offset);
127 7421 : if (err)
128 0 : return err;
129 7421 : s->s_top->s_state = newstate;
130 7421 : return s_push(s, d, CHILD(n, NCH(n)-1));
131 : }
132 :
133 :
134 : /* PARSER PROPER */
135 :
136 : static int
137 1823 : classify(parser_state *ps, int type, char *str)
138 : {
139 1823 : grammar *g = ps->p_grammar;
140 1823 : register int n = g->g_ll.ll_nlabels;
141 :
142 1823 : if (type == NAME) {
143 701 : register char *s = str;
144 701 : register label *l = g->g_ll.ll_label;
145 : register int i;
146 211652 : for (i = n; i > 0; i--, l++) {
147 125227 : if (l->lb_type != NAME || l->lb_str == NULL ||
148 20837 : l->lb_str[0] != s[0] ||
149 880 : strcmp(l->lb_str, s) != 0)
150 105125 : continue;
151 : #ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
152 : #if 0
153 : /* Leaving this in as an example */
154 : if (!(ps->p_flags & CO_FUTURE_WITH_STATEMENT)) {
155 : if (s[0] == 'w' && strcmp(s, "with") == 0)
156 : break; /* not a keyword yet */
157 : else if (s[0] == 'a' && strcmp(s, "as") == 0)
158 : break; /* not a keyword yet */
159 : }
160 : #endif
161 : #endif
162 : D(printf("It's a keyword\n"));
163 145 : return n - i;
164 : }
165 : }
166 :
167 : {
168 1678 : register label *l = g->g_ll.ll_label;
169 : register int i;
170 74150 : for (i = n; i > 0; i--, l++) {
171 74150 : if (l->lb_type == type && l->lb_str == NULL) {
172 : D(printf("It's a token we know\n"));
173 1678 : return n - i;
174 : }
175 : }
176 : }
177 :
178 : D(printf("Illegal token\n"));
179 0 : return -1;
180 : }
181 :
182 : #ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
183 : #if 0
184 : /* Leaving this in as an example */
185 : static void
186 : future_hack(parser_state *ps)
187 : {
188 : node *n = ps->p_stack.s_top->s_parent;
189 : node *ch, *cch;
190 : int i;
191 :
192 : /* from __future__ import ..., must have at least 4 children */
193 : n = CHILD(n, 0);
194 : if (NCH(n) < 4)
195 : return;
196 : ch = CHILD(n, 0);
197 : if (STR(ch) == NULL || strcmp(STR(ch), "from") != 0)
198 : return;
199 : ch = CHILD(n, 1);
200 : if (NCH(ch) == 1 && STR(CHILD(ch, 0)) &&
201 : strcmp(STR(CHILD(ch, 0)), "__future__") != 0)
202 : return;
203 : ch = CHILD(n, 3);
204 : /* ch can be a star, a parenthesis or import_as_names */
205 : if (TYPE(ch) == STAR)
206 : return;
207 : if (TYPE(ch) == LPAR)
208 : ch = CHILD(n, 4);
209 :
210 : for (i = 0; i < NCH(ch); i += 2) {
211 : cch = CHILD(ch, i);
212 : if (NCH(cch) >= 1 && TYPE(CHILD(cch, 0)) == NAME) {
213 : char *str_ch = STR(CHILD(cch, 0));
214 : if (strcmp(str_ch, FUTURE_WITH_STATEMENT) == 0) {
215 : ps->p_flags |= CO_FUTURE_WITH_STATEMENT;
216 : } else if (strcmp(str_ch, FUTURE_PRINT_FUNCTION) == 0) {
217 : ps->p_flags |= CO_FUTURE_PRINT_FUNCTION;
218 : } else if (strcmp(str_ch, FUTURE_UNICODE_LITERALS) == 0) {
219 : ps->p_flags |= CO_FUTURE_UNICODE_LITERALS;
220 : }
221 : }
222 : }
223 : }
224 : #endif
225 : #endif /* future keyword */
226 :
227 : int
228 1823 : PyParser_AddToken(register parser_state *ps, register int type, char *str,
229 : int lineno, int col_offset, int *expected_ret)
230 : {
231 : register int ilabel;
232 : int err;
233 :
234 : D(printf("Token %s/'%s' ... ", _PyParser_TokenNames[type], str));
235 :
236 : /* Find out which label this token is */
237 1823 : ilabel = classify(ps, type, str);
238 1823 : if (ilabel < 0)
239 0 : return E_SYNTAX;
240 :
241 : /* Loop until the token is shifted or an error occurred */
242 : for (;;) {
243 : /* Fetch the current dfa and state */
244 15618 : register dfa *d = ps->p_stack.s_top->s_dfa;
245 15618 : register state *s = &d->d_state[ps->p_stack.s_top->s_state];
246 :
247 : D(printf(" DFA '%s', state %d:",
248 : d->d_name, ps->p_stack.s_top->s_state));
249 :
250 : /* Check accelerator */
251 15618 : if (s->s_lower <= ilabel && ilabel < s->s_upper) {
252 9642 : register int x = s->s_accel[ilabel - s->s_lower];
253 9642 : if (x != -1) {
254 9244 : if (x & (1<<7)) {
255 : /* Push non-terminal */
256 7421 : int nt = (x >> 8) + NT_OFFSET;
257 7421 : int arrow = x & ((1<<7)-1);
258 7421 : dfa *d1 = PyGrammar_FindDFA(
259 : ps->p_grammar, nt);
260 7421 : if ((err = push(&ps->p_stack, nt, d1,
261 : arrow, lineno, col_offset)) > 0) {
262 : D(printf(" MemError: push\n"));
263 0 : return err;
264 : }
265 : D(printf(" Push ...\n"));
266 7421 : continue;
267 : }
268 :
269 : /* Shift the token */
270 1823 : if ((err = shift(&ps->p_stack, type, str,
271 : x, lineno, col_offset)) > 0) {
272 : D(printf(" MemError: shift.\n"));
273 0 : return err;
274 : }
275 : D(printf(" Shift.\n"));
276 : /* Pop while we are in an accept-only state */
277 13303 : while (s = &d->d_state
278 5740 : [ps->p_stack.s_top->s_state],
279 2870 : s->s_accept && s->s_narcs == 1) {
280 : D(printf(" DFA '%s', state %d: "
281 : "Direct pop.\n",
282 : d->d_name,
283 : ps->p_stack.s_top->s_state));
284 : #ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
285 : #if 0
286 : if (d->d_name[0] == 'i' &&
287 : strcmp(d->d_name,
288 : "import_stmt") == 0)
289 : future_hack(ps);
290 : #endif
291 : #endif
292 1050 : s_pop(&ps->p_stack);
293 1050 : if (s_empty(&ps->p_stack)) {
294 : D(printf(" ACCEPT.\n"));
295 3 : return E_DONE;
296 : }
297 1047 : d = ps->p_stack.s_top->s_dfa;
298 : }
299 1820 : return E_OK;
300 : }
301 : }
302 :
303 6374 : if (s->s_accept) {
304 : #ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
305 : #if 0
306 : if (d->d_name[0] == 'i' &&
307 : strcmp(d->d_name, "import_stmt") == 0)
308 : future_hack(ps);
309 : #endif
310 : #endif
311 : /* Pop this dfa and try again */
312 6374 : s_pop(&ps->p_stack);
313 : D(printf(" Pop ...\n"));
314 6374 : if (s_empty(&ps->p_stack)) {
315 : D(printf(" Error: bottom of stack.\n"));
316 0 : return E_SYNTAX;
317 : }
318 6374 : continue;
319 : }
320 :
321 : /* Stuck, report syntax error */
322 : D(printf(" Error.\n"));
323 0 : if (expected_ret) {
324 0 : if (s->s_lower == s->s_upper - 1) {
325 : /* Only one possible expected token */
326 0 : *expected_ret = ps->p_grammar->
327 0 : g_ll.ll_label[s->s_lower].lb_type;
328 : }
329 : else
330 0 : *expected_ret = -1;
331 : }
332 0 : return E_SYNTAX;
333 13795 : }
334 : }
335 :
336 :
337 : #ifdef Py_DEBUG
338 :
339 : /* DEBUG OUTPUT */
340 :
341 : void
342 : dumptree(grammar *g, node *n)
343 : {
344 : int i;
345 :
346 : if (n == NULL)
347 : printf("NIL");
348 : else {
349 : label l;
350 : l.lb_type = TYPE(n);
351 : l.lb_str = STR(n);
352 : printf("%s", PyGrammar_LabelRepr(&l));
353 : if (ISNONTERMINAL(TYPE(n))) {
354 : printf("(");
355 : for (i = 0; i < NCH(n); i++) {
356 : if (i > 0)
357 : printf(",");
358 : dumptree(g, CHILD(n, i));
359 : }
360 : printf(")");
361 : }
362 : }
363 : }
364 :
365 : void
366 : showtree(grammar *g, node *n)
367 : {
368 : int i;
369 :
370 : if (n == NULL)
371 : return;
372 : if (ISNONTERMINAL(TYPE(n))) {
373 : for (i = 0; i < NCH(n); i++)
374 : showtree(g, CHILD(n, i));
375 : }
376 : else if (ISTERMINAL(TYPE(n))) {
377 : printf("%s", _PyParser_TokenNames[TYPE(n)]);
378 : if (TYPE(n) == NUMBER || TYPE(n) == NAME)
379 : printf("(%s)", STR(n));
380 : printf(" ");
381 : }
382 : else
383 : printf("? ");
384 : }
385 :
386 : void
387 : printtree(parser_state *ps)
388 : {
389 : if (Py_DebugFlag) {
390 : printf("Parse tree:\n");
391 : dumptree(ps->p_grammar, ps->p_tree);
392 : printf("\n");
393 : printf("Tokens:\n");
394 : showtree(ps->p_grammar, ps->p_tree);
395 : printf("\n");
396 : }
397 : printf("Listing:\n");
398 : PyNode_ListTree(ps->p_tree);
399 : printf("\n");
400 : }
401 :
402 : #endif /* Py_DEBUG */
403 :
404 : /*
405 :
406 : Description
407 : -----------
408 :
409 : The parser's interface is different than usual: the function addtoken()
410 : must be called for each token in the input. This makes it possible to
411 : turn it into an incremental parsing system later. The parsing system
412 : constructs a parse tree as it goes.
413 :
414 : A parsing rule is represented as a Deterministic Finite-state Automaton
415 : (DFA). A node in a DFA represents a state of the parser; an arc represents
416 : a transition. Transitions are either labeled with terminal symbols or
417 : with non-terminals. When the parser decides to follow an arc labeled
418 : with a non-terminal, it is invoked recursively with the DFA representing
419 : the parsing rule for that as its initial state; when that DFA accepts,
420 : the parser that invoked it continues. The parse tree constructed by the
421 : recursively called parser is inserted as a child in the current parse tree.
422 :
423 : The DFA's can be constructed automatically from a more conventional
424 : language description. An extended LL(1) grammar (ELL(1)) is suitable.
425 : Certain restrictions make the parser's life easier: rules that can produce
426 : the empty string should be outlawed (there are other ways to put loops
427 : or optional parts in the language). To avoid the need to construct
428 : FIRST sets, we can require that all but the last alternative of a rule
429 : (really: arc going out of a DFA's state) must begin with a terminal
430 : symbol.
431 :
432 : As an example, consider this grammar:
433 :
434 : expr: term (OP term)*
435 : term: CONSTANT | '(' expr ')'
436 :
437 : The DFA corresponding to the rule for expr is:
438 :
439 : ------->.---term-->.------->
440 : ^ |
441 : | |
442 : \----OP----/
443 :
444 : The parse tree generated for the input a+b is:
445 :
446 : (expr: (term: (NAME: a)), (OP: +), (term: (NAME: b)))
447 :
448 : */
|
