AppPkg/Applications/Python/Python-2.7.10/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 */