Python code coverage for Parser/parser.c

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