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 */