blob: b505fe0ecd337ca40ef1afe3d88ad7da4576e390 [file] [log] [blame]
Guido van Rossumf70e43a1991-02-19 12:39:46 +00001
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002/* Parser implementation */
3
4/* For a description, see the comments at end of this file */
5
6/* XXX To do: error recovery */
7
Tim Peters1ca12962001-12-04 03:18:48 +00008#include "Python.h"
Guido van Rossum3f5da241990-12-20 15:06:42 +00009#include "pgenheaders.h"
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000010#include "token.h"
11#include "grammar.h"
12#include "node.h"
13#include "parser.h"
14#include "errcode.h"
15
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000016
Guido van Rossum408027e1996-12-30 16:17:54 +000017#ifdef Py_DEBUG
Guido van Rossum86bea461997-04-29 21:03:06 +000018extern int Py_DebugFlag;
19#define D(x) if (!Py_DebugFlag); else x
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000020#else
21#define D(x)
22#endif
23
24
25/* STACK DATA TYPE */
26
Tim Petersdbd9ba62000-07-09 03:09:57 +000027static void s_reset(stack *);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000028
29static void
Thomas Wouters23c9e002000-07-22 19:20:54 +000030s_reset(stack *s)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000031{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +000032 s->s_top = &s->s_base[MAXSTACK];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000033}
34
35#define s_empty(s) ((s)->s_top == &(s)->s_base[MAXSTACK])
36
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000037static int
Thomas Wouters23c9e002000-07-22 19:20:54 +000038s_push(register stack *s, dfa *d, node *parent)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000039{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +000040 register stackentry *top;
41 if (s->s_top == s->s_base) {
42 fprintf(stderr, "s_push: parser stack overflow\n");
43 return E_NOMEM;
44 }
45 top = --s->s_top;
46 top->s_dfa = d;
47 top->s_parent = parent;
48 top->s_state = 0;
49 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000050}
51
Guido van Rossum408027e1996-12-30 16:17:54 +000052#ifdef Py_DEBUG
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000053
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000054static void
Thomas Wouters23c9e002000-07-22 19:20:54 +000055s_pop(register stack *s)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000056{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +000057 if (s_empty(s))
58 Py_FatalError("s_pop: parser stack underflow -- FATAL");
59 s->s_top++;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000060}
61
Guido van Rossum408027e1996-12-30 16:17:54 +000062#else /* !Py_DEBUG */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000063
64#define s_pop(s) (s)->s_top++
65
66#endif
67
68
69/* PARSER CREATION */
70
71parser_state *
Thomas Wouters23c9e002000-07-22 19:20:54 +000072PyParser_New(grammar *g, int start)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000073{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +000074 parser_state *ps;
75
76 if (!g->g_accel)
77 PyGrammar_AddAccelerators(g);
78 ps = (parser_state *)PyMem_MALLOC(sizeof(parser_state));
79 if (ps == NULL)
80 return NULL;
81 ps->p_grammar = g;
Thomas Wouters34aa7ba2006-02-28 19:02:24 +000082#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +000083 ps->p_flags = 0;
Neil Schemenauerc155dd42002-03-22 23:38:11 +000084#endif
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +000085 ps->p_tree = PyNode_New(start);
86 if (ps->p_tree == NULL) {
87 PyMem_FREE(ps);
88 return NULL;
89 }
90 s_reset(&ps->p_stack);
91 (void) s_push(&ps->p_stack, PyGrammar_FindDFA(g, start), ps->p_tree);
92 return ps;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000093}
94
95void
Thomas Wouters23c9e002000-07-22 19:20:54 +000096PyParser_Delete(parser_state *ps)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000097{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +000098 /* NB If you want to save the parse tree,
99 you must set p_tree to NULL before calling delparser! */
100 PyNode_Free(ps->p_tree);
101 PyMem_FREE(ps);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000102}
103
104
105/* PARSER STACK OPERATIONS */
106
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000107static int
Martin v. Löwis49c5da12006-03-01 22:49:05 +0000108shift(register stack *s, int type, char *str, int newstate, int lineno, int col_offset)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000109{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000110 int err;
111 assert(!s_empty(s));
112 err = PyNode_AddChild(s->s_top->s_parent, type, str, lineno, col_offset);
113 if (err)
114 return err;
115 s->s_top->s_state = newstate;
116 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000117}
118
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000119static int
Martin v. Löwis49c5da12006-03-01 22:49:05 +0000120push(register stack *s, int type, dfa *d, int newstate, int lineno, int col_offset)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000121{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000122 int err;
123 register node *n;
124 n = s->s_top->s_parent;
125 assert(!s_empty(s));
126 err = PyNode_AddChild(n, type, (char *)NULL, lineno, col_offset);
127 if (err)
128 return err;
129 s->s_top->s_state = newstate;
130 return s_push(s, d, CHILD(n, NCH(n)-1));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000131}
132
133
134/* PARSER PROPER */
135
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000136static int
Guido van Rossumb09f7ed2001-07-15 21:08:29 +0000137classify(parser_state *ps, int type, char *str)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000138{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000139 grammar *g = ps->p_grammar;
140 register int n = g->g_ll.ll_nlabels;
141
142 if (type == NAME) {
143 register char *s = str;
144 register label *l = g->g_ll.ll_label;
145 register int i;
146 for (i = n; i > 0; i--, l++) {
147 if (l->lb_type != NAME || l->lb_str == NULL ||
148 l->lb_str[0] != s[0] ||
149 strcmp(l->lb_str, s) != 0)
150 continue;
Thomas Wouters34aa7ba2006-02-28 19:02:24 +0000151#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
Brett Cannone3944a52009-04-01 05:08:41 +0000152#if 0
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000153 /* 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 }
Thomas Wouters8ae12952006-02-28 22:42:15 +0000160#endif
Brett Cannone3944a52009-04-01 05:08:41 +0000161#endif
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000162 D(printf("It's a keyword\n"));
163 return n - i;
164 }
165 }
166
167 {
168 register label *l = g->g_ll.ll_label;
169 register int i;
170 for (i = n; i > 0; i--, l++) {
171 if (l->lb_type == type && l->lb_str == NULL) {
172 D(printf("It's a token we know\n"));
173 return n - i;
174 }
175 }
176 }
177
178 D(printf("Illegal token\n"));
179 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000180}
181
Thomas Wouters34aa7ba2006-02-28 19:02:24 +0000182#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
Brett Cannone3944a52009-04-01 05:08:41 +0000183#if 0
Guido van Rossum45aecf42006-03-15 04:58:47 +0000184/* Leaving this in as an example */
Guido van Rossumb09f7ed2001-07-15 21:08:29 +0000185static void
186future_hack(parser_state *ps)
187{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000188 node *n = ps->p_stack.s_top->s_parent;
189 node *ch, *cch;
190 int i;
Guido van Rossumb09f7ed2001-07-15 21:08:29 +0000191
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000192 /* 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 }
Guido van Rossumb09f7ed2001-07-15 21:08:29 +0000223}
Brett Cannone3944a52009-04-01 05:08:41 +0000224#endif
Neil Schemenauerc155dd42002-03-22 23:38:11 +0000225#endif /* future keyword */
Guido van Rossumb09f7ed2001-07-15 21:08:29 +0000226
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000227int
Thomas Wouters23c9e002000-07-22 19:20:54 +0000228PyParser_AddToken(register parser_state *ps, register int type, char *str,
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000229 int lineno, int col_offset, int *expected_ret)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000230{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000231 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 ilabel = classify(ps, type, str);
238 if (ilabel < 0)
239 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 register dfa *d = ps->p_stack.s_top->s_dfa;
245 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 if (s->s_lower <= ilabel && ilabel < s->s_upper) {
252 register int x = s->s_accel[ilabel - s->s_lower];
253 if (x != -1) {
254 if (x & (1<<7)) {
255 /* Push non-terminal */
256 int nt = (x >> 8) + NT_OFFSET;
257 int arrow = x & ((1<<7)-1);
258 dfa *d1 = PyGrammar_FindDFA(
259 ps->p_grammar, nt);
260 if ((err = push(&ps->p_stack, nt, d1,
261 arrow, lineno, col_offset)) > 0) {
262 D(printf(" MemError: push\n"));
263 return err;
264 }
265 D(printf(" Push ...\n"));
266 continue;
267 }
268
269 /* Shift the token */
270 if ((err = shift(&ps->p_stack, type, str,
271 x, lineno, col_offset)) > 0) {
272 D(printf(" MemError: shift.\n"));
273 return err;
274 }
275 D(printf(" Shift.\n"));
276 /* Pop while we are in an accept-only state */
277 while (s = &d->d_state
278 [ps->p_stack.s_top->s_state],
279 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));
Thomas Wouters34aa7ba2006-02-28 19:02:24 +0000284#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
Brett Cannone3944a52009-04-01 05:08:41 +0000285#if 0
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000286 if (d->d_name[0] == 'i' &&
287 strcmp(d->d_name,
288 "import_stmt") == 0)
289 future_hack(ps);
Neil Schemenauerc155dd42002-03-22 23:38:11 +0000290#endif
Brett Cannone3944a52009-04-01 05:08:41 +0000291#endif
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000292 s_pop(&ps->p_stack);
293 if (s_empty(&ps->p_stack)) {
294 D(printf(" ACCEPT.\n"));
295 return E_DONE;
296 }
297 d = ps->p_stack.s_top->s_dfa;
298 }
299 return E_OK;
300 }
301 }
302
303 if (s->s_accept) {
Thomas Wouters34aa7ba2006-02-28 19:02:24 +0000304#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
Brett Cannone3944a52009-04-01 05:08:41 +0000305#if 0
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000306 if (d->d_name[0] == 'i' &&
307 strcmp(d->d_name, "import_stmt") == 0)
308 future_hack(ps);
Neil Schemenauerc155dd42002-03-22 23:38:11 +0000309#endif
Brett Cannone3944a52009-04-01 05:08:41 +0000310#endif
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000311 /* Pop this dfa and try again */
312 s_pop(&ps->p_stack);
313 D(printf(" Pop ...\n"));
314 if (s_empty(&ps->p_stack)) {
315 D(printf(" Error: bottom of stack.\n"));
316 return E_SYNTAX;
317 }
318 continue;
319 }
320
321 /* Stuck, report syntax error */
322 D(printf(" Error.\n"));
323 if (expected_ret) {
324 if (s->s_lower == s->s_upper - 1) {
325 /* Only one possible expected token */
326 *expected_ret = ps->p_grammar->
327 g_ll.ll_label[s->s_lower].lb_type;
328 }
329 else
330 *expected_ret = -1;
331 }
332 return E_SYNTAX;
333 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000334}
335
336
Guido van Rossum408027e1996-12-30 16:17:54 +0000337#ifdef Py_DEBUG
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000338
339/* DEBUG OUTPUT */
340
341void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000342dumptree(grammar *g, node *n)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000343{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000344 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 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000363}
364
365void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000366showtree(grammar *g, node *n)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000367{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000368 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("? ");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000384}
385
386void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000387printtree(parser_state *ps)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000388{
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000389 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");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000400}
401
Guido van Rossum408027e1996-12-30 16:17:54 +0000402#endif /* Py_DEBUG */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000403
404/*
405
406Description
407-----------
408
409The parser's interface is different than usual: the function addtoken()
410must be called for each token in the input. This makes it possible to
411turn it into an incremental parsing system later. The parsing system
412constructs a parse tree as it goes.
413
414A 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
416a transition. Transitions are either labeled with terminal symbols or
417with non-terminals. When the parser decides to follow an arc labeled
418with a non-terminal, it is invoked recursively with the DFA representing
419the parsing rule for that as its initial state; when that DFA accepts,
420the parser that invoked it continues. The parse tree constructed by the
421recursively called parser is inserted as a child in the current parse tree.
422
423The DFA's can be constructed automatically from a more conventional
424language description. An extended LL(1) grammar (ELL(1)) is suitable.
425Certain restrictions make the parser's life easier: rules that can produce
426the empty string should be outlawed (there are other ways to put loops
427or optional parts in the language). To avoid the need to construct
428FIRST 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
430symbol.
431
432As an example, consider this grammar:
433
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000434expr: term (OP term)*
435term: CONSTANT | '(' expr ')'
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000436
437The DFA corresponding to the rule for expr is:
438
439------->.---term-->.------->
Antoine Pitrou7f14f0d2010-05-09 16:14:21 +0000440 ^ |
441 | |
442 \----OP----/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000443
444The parse tree generated for the input a+b is:
445
446(expr: (term: (NAME: a)), (OP: +), (term: (NAME: b)))
447
448*/