← Back to branch summary

~malept/ubuntu/lucid/python2.6/dev-dependency-fix

« back to all changes in this revision

Viewing changes to Parser/parser.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2009-02-13 12:51:00 UTC
  • Revision ID: james.westby@ubuntu.com-20090213125100-uufgcb9yeqzujpqw
Tags: upstream-2.6.1
Import upstream version 2.6.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
Parser/parser.c
 
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
s_reset(stack *s)
 
31
{
 
32
        s->s_top = &s->s_base[MAXSTACK];
 
33
}
 
34
 
 
35
#define s_empty(s) ((s)->s_top == &(s)->s_base[MAXSTACK])
 
36
 
 
37
static int
 
38
s_push(register stack *s, dfa *d, node *parent)
 
39
{
 
40
        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;
 
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
PyParser_New(grammar *g, int start)
 
73
{
 
74
        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;
 
82
#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
 
83
        ps->p_flags = 0;
 
84
#endif
 
85
        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;
 
93
}
 
94
 
 
95
void
 
96
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
        PyNode_Free(ps->p_tree);
 
101
        PyMem_FREE(ps);
 
102
}
 
103
 
 
104
 
 
105
/* PARSER STACK OPERATIONS */
 
106
 
 
107
static int
 
108
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
        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;
 
117
}
 
118
 
 
119
static int
 
120
push(register stack *s, int type, dfa *d, int newstate, int lineno, int col_offset)
 
121
{
 
122
        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));
 
131
}
 
132
 
 
133
 
 
134
/* PARSER PROPER */
 
135
 
 
136
static int
 
137
classify(parser_state *ps, int type, char *str)
 
138
{
 
139
        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;
 
151
#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
 
152
                        if (ps->p_flags & CO_FUTURE_PRINT_FUNCTION &&
 
153
                            s[0] == 'p' && strcmp(s, "print") == 0) { 
 
154
                                break; /* no longer a keyword */
 
155
                        }
 
156
#endif
 
157
                        D(printf("It's a keyword\n"));
 
158
                        return n - i;
 
159
                }
 
160
        }
 
161
        
 
162
        {
 
163
                register label *l = g->g_ll.ll_label;
 
164
                register int i;
 
165
                for (i = n; i > 0; i--, l++) {
 
166
                        if (l->lb_type == type && l->lb_str == NULL) {
 
167
                                D(printf("It's a token we know\n"));
 
168
                                return n - i;
 
169
                        }
 
170
                }
 
171
        }
 
172
        
 
173
        D(printf("Illegal token\n"));
 
174
        return -1;
 
175
}
 
176
 
 
177
#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
 
178
static void
 
179
future_hack(parser_state *ps)
 
180
{
 
181
        node *n = ps->p_stack.s_top->s_parent;
 
182
        node *ch, *cch;
 
183
        int i;
 
184
 
 
185
        /* from __future__ import ..., must have at least 4 children */
 
186
        n = CHILD(n, 0);
 
187
        if (NCH(n) < 4)
 
188
                return;
 
189
        ch = CHILD(n, 0);
 
190
        if (STR(ch) == NULL || strcmp(STR(ch), "from") != 0)
 
191
                return;
 
192
        ch = CHILD(n, 1);
 
193
        if (NCH(ch) == 1 && STR(CHILD(ch, 0)) &&
 
194
            strcmp(STR(CHILD(ch, 0)), "__future__") != 0)
 
195
                return;
 
196
        ch = CHILD(n, 3);
 
197
        /* ch can be a star, a parenthesis or import_as_names */
 
198
        if (TYPE(ch) == STAR)
 
199
                return;
 
200
        if (TYPE(ch) == LPAR)
 
201
                ch = CHILD(n, 4);
 
202
        
 
203
        for (i = 0; i < NCH(ch); i += 2) {
 
204
                cch = CHILD(ch, i);
 
205
                if (NCH(cch) >= 1 && TYPE(CHILD(cch, 0)) == NAME) {
 
206
                        char *str_ch = STR(CHILD(cch, 0));
 
207
                        if (strcmp(str_ch, FUTURE_WITH_STATEMENT) == 0) {
 
208
                                ps->p_flags |= CO_FUTURE_WITH_STATEMENT;
 
209
                        } else if (strcmp(str_ch, FUTURE_PRINT_FUNCTION) == 0) {
 
210
                                ps->p_flags |= CO_FUTURE_PRINT_FUNCTION;
 
211
                        } else if (strcmp(str_ch, FUTURE_UNICODE_LITERALS) == 0) {
 
212
                                ps->p_flags |= CO_FUTURE_UNICODE_LITERALS;
 
213
                        }
 
214
                }
 
215
        }
 
216
}
 
217
#endif /* future keyword */
 
218
 
 
219
int
 
220
PyParser_AddToken(register parser_state *ps, register int type, char *str,
 
221
                  int lineno, int col_offset, int *expected_ret)
 
222
{
 
223
        register int ilabel;
 
224
        int err;
 
225
        
 
226
        D(printf("Token %s/'%s' ... ", _PyParser_TokenNames[type], str));
 
227
        
 
228
        /* Find out which label this token is */
 
229
        ilabel = classify(ps, type, str);
 
230
        if (ilabel < 0)
 
231
                return E_SYNTAX;
 
232
        
 
233
        /* Loop until the token is shifted or an error occurred */
 
234
        for (;;) {
 
235
                /* Fetch the current dfa and state */
 
236
                register dfa *d = ps->p_stack.s_top->s_dfa;
 
237
                register state *s = &d->d_state[ps->p_stack.s_top->s_state];
 
238
                
 
239
                D(printf(" DFA '%s', state %d:",
 
240
                        d->d_name, ps->p_stack.s_top->s_state));
 
241
                
 
242
                /* Check accelerator */
 
243
                if (s->s_lower <= ilabel && ilabel < s->s_upper) {
 
244
                        register int x = s->s_accel[ilabel - s->s_lower];
 
245
                        if (x != -1) {
 
246
                                if (x & (1<<7)) {
 
247
                                        /* Push non-terminal */
 
248
                                        int nt = (x >> 8) + NT_OFFSET;
 
249
                                        int arrow = x & ((1<<7)-1);
 
250
                                        dfa *d1 = PyGrammar_FindDFA(
 
251
                                                ps->p_grammar, nt);
 
252
                                        if ((err = push(&ps->p_stack, nt, d1,
 
253
                                                arrow, lineno, col_offset)) > 0) {
 
254
                                                D(printf(" MemError: push\n"));
 
255
                                                return err;
 
256
                                        }
 
257
                                        D(printf(" Push ...\n"));
 
258
                                        continue;
 
259
                                }
 
260
                                
 
261
                                /* Shift the token */
 
262
                                if ((err = shift(&ps->p_stack, type, str,
 
263
                                                x, lineno, col_offset)) > 0) {
 
264
                                        D(printf(" MemError: shift.\n"));
 
265
                                        return err;
 
266
                                }
 
267
                                D(printf(" Shift.\n"));
 
268
                                /* Pop while we are in an accept-only state */
 
269
                                while (s = &d->d_state
 
270
                                                [ps->p_stack.s_top->s_state],
 
271
                                        s->s_accept && s->s_narcs == 1) {
 
272
                                        D(printf("  DFA '%s', state %d: "
 
273
                                                 "Direct pop.\n",
 
274
                                                 d->d_name,
 
275
                                                 ps->p_stack.s_top->s_state));
 
276
#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
 
277
                                        if (d->d_name[0] == 'i' &&
 
278
                                            strcmp(d->d_name,
 
279
                                                   "import_stmt") == 0)
 
280
                                                future_hack(ps);
 
281
#endif
 
282
                                        s_pop(&ps->p_stack);
 
283
                                        if (s_empty(&ps->p_stack)) {
 
284
                                                D(printf("  ACCEPT.\n"));
 
285
                                                return E_DONE;
 
286
                                        }
 
287
                                        d = ps->p_stack.s_top->s_dfa;
 
288
                                }
 
289
                                return E_OK;
 
290
                        }
 
291
                }
 
292
                
 
293
                if (s->s_accept) {
 
294
#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
 
295
                        if (d->d_name[0] == 'i' &&
 
296
                            strcmp(d->d_name, "import_stmt") == 0)
 
297
                                future_hack(ps);
 
298
#endif
 
299
                        /* Pop this dfa and try again */
 
300
                        s_pop(&ps->p_stack);
 
301
                        D(printf(" Pop ...\n"));
 
302
                        if (s_empty(&ps->p_stack)) {
 
303
                                D(printf(" Error: bottom of stack.\n"));
 
304
                                return E_SYNTAX;
 
305
                        }
 
306
                        continue;
 
307
                }
 
308
                
 
309
                /* Stuck, report syntax error */
 
310
                D(printf(" Error.\n"));
 
311
                if (expected_ret) {
 
312
                        if (s->s_lower == s->s_upper - 1) {
 
313
                                /* Only one possible expected token */
 
314
                                *expected_ret = ps->p_grammar->
 
315
                                    g_ll.ll_label[s->s_lower].lb_type;
 
316
                        }
 
317
                        else 
 
318
                                *expected_ret = -1;
 
319
                }
 
320
                return E_SYNTAX;
 
321
        }
 
322
}
 
323
 
 
324
 
 
325
#ifdef Py_DEBUG
 
326
 
 
327
/* DEBUG OUTPUT */
 
328
 
 
329
void
 
330
dumptree(grammar *g, node *n)
 
331
{
 
332
        int i;
 
333
        
 
334
        if (n == NULL)
 
335
                printf("NIL");
 
336
        else {
 
337
                label l;
 
338
                l.lb_type = TYPE(n);
 
339
                l.lb_str = STR(n);
 
340
                printf("%s", PyGrammar_LabelRepr(&l));
 
341
                if (ISNONTERMINAL(TYPE(n))) {
 
342
                        printf("(");
 
343
                        for (i = 0; i < NCH(n); i++) {
 
344
                                if (i > 0)
 
345
                                        printf(",");
 
346
                                dumptree(g, CHILD(n, i));
 
347
                        }
 
348
                        printf(")");
 
349
                }
 
350
        }
 
351
}
 
352
 
 
353
void
 
354
showtree(grammar *g, node *n)
 
355
{
 
356
        int i;
 
357
        
 
358
        if (n == NULL)
 
359
                return;
 
360
        if (ISNONTERMINAL(TYPE(n))) {
 
361
                for (i = 0; i < NCH(n); i++)
 
362
                        showtree(g, CHILD(n, i));
 
363
        }
 
364
        else if (ISTERMINAL(TYPE(n))) {
 
365
                printf("%s", _PyParser_TokenNames[TYPE(n)]);
 
366
                if (TYPE(n) == NUMBER || TYPE(n) == NAME)
 
367
                        printf("(%s)", STR(n));
 
368
                printf(" ");
 
369
        }
 
370
        else
 
371
                printf("? ");
 
372
}
 
373
 
 
374
void
 
375
printtree(parser_state *ps)
 
376
{
 
377
        if (Py_DebugFlag) {
 
378
                printf("Parse tree:\n");
 
379
                dumptree(ps->p_grammar, ps->p_tree);
 
380
                printf("\n");
 
381
                printf("Tokens:\n");
 
382
                showtree(ps->p_grammar, ps->p_tree);
 
383
                printf("\n");
 
384
        }
 
385
        printf("Listing:\n");
 
386
        PyNode_ListTree(ps->p_tree);
 
387
        printf("\n");
 
388
}
 
389
 
 
390
#endif /* Py_DEBUG */
 
391
 
 
392
/*
 
393
 
 
394
Description
 
395
-----------
 
396
 
 
397
The parser's interface is different than usual: the function addtoken()
 
398
must be called for each token in the input.  This makes it possible to
 
399
turn it into an incremental parsing system later.  The parsing system
 
400
constructs a parse tree as it goes.
 
401
 
 
402
A parsing rule is represented as a Deterministic Finite-state Automaton
 
403
(DFA).  A node in a DFA represents a state of the parser; an arc represents
 
404
a transition.  Transitions are either labeled with terminal symbols or
 
405
with non-terminals.  When the parser decides to follow an arc labeled
 
406
with a non-terminal, it is invoked recursively with the DFA representing
 
407
the parsing rule for that as its initial state; when that DFA accepts,
 
408
the parser that invoked it continues.  The parse tree constructed by the
 
409
recursively called parser is inserted as a child in the current parse tree.
 
410
 
 
411
The DFA's can be constructed automatically from a more conventional
 
412
language description.  An extended LL(1) grammar (ELL(1)) is suitable.
 
413
Certain restrictions make the parser's life easier: rules that can produce
 
414
the empty string should be outlawed (there are other ways to put loops
 
415
or optional parts in the language).  To avoid the need to construct
 
416
FIRST sets, we can require that all but the last alternative of a rule
 
417
(really: arc going out of a DFA's state) must begin with a terminal
 
418
symbol.
 
419
 
 
420
As an example, consider this grammar:
 
421
 
 
422
expr:   term (OP term)*
 
423
term:   CONSTANT | '(' expr ')'
 
424
 
 
425
The DFA corresponding to the rule for expr is:
 
426
 
 
427
------->.---term-->.------->
 
428
        ^          |
 
429
        |          |
 
430
        \----OP----/
 
431
 
 
432
The parse tree generated for the input a+b is:
 
433
 
 
434
(expr: (term: (NAME: a)), (OP: +), (term: (NAME: b)))
 
435
 
 
436
*/