xref: /csrg-svn/usr.bin/indent/parse.c (revision 8805)
1*8805Smckusick static char sccsid[] = "@(#)parse.c	4.1	(Berkeley)	10/21/82";
2*8805Smckusick 
3*8805Smckusick /*
4*8805Smckusick 
5*8805Smckusick 			  Copyright (C) 1976
6*8805Smckusick 				by the
7*8805Smckusick 			  Board of Trustees
8*8805Smckusick 				of the
9*8805Smckusick 			University of Illinois
10*8805Smckusick 
11*8805Smckusick 			 All rights reserved
12*8805Smckusick 
13*8805Smckusick 
14*8805Smckusick FILE NAME:
15*8805Smckusick 	parse.c
16*8805Smckusick 
17*8805Smckusick PURPOSE:
18*8805Smckusick 	Contains the routines which keep track of the parse stack.
19*8805Smckusick 
20*8805Smckusick GLOBALS:
21*8805Smckusick 	p_stack =	The parse stack, set by both routines
22*8805Smckusick 	il =		Stack of indentation levels, set by parse
23*8805Smckusick 	cstk =		Stack of case statement indentation levels, set by parse
24*8805Smckusick 	tos =		Pointer to top of stack, set by both routines.
25*8805Smckusick 
26*8805Smckusick FUNCTIONS:
27*8805Smckusick 	parse
28*8805Smckusick 	reduce
29*8805Smckusick */
30*8805Smckusick /*
31*8805Smckusick 
32*8805Smckusick 			  Copyright (C) 1976
33*8805Smckusick 				by the
34*8805Smckusick 			  Board of Trustees
35*8805Smckusick 				of the
36*8805Smckusick 			University of Illinois
37*8805Smckusick 
38*8805Smckusick 			 All rights reserved
39*8805Smckusick 
40*8805Smckusick 
41*8805Smckusick NAME:
42*8805Smckusick 	parse
43*8805Smckusick 
44*8805Smckusick FUNCTION:
45*8805Smckusick 	Parse is given one input which is a "maxi token" just scanned from
46*8805Smckusick 	input.  Maxi tokens are signifigant constructs such as else, {, do,
47*8805Smckusick 	if (...), etc.  Parse works with reduce to maintain a parse stack
48*8805Smckusick 	of these constructs.  Parse is responsible for the "shift" portion
49*8805Smckusick 	of the parse algorithm, and reduce handles the "reduce" portion.
50*8805Smckusick 
51*8805Smckusick ALGORITHM:
52*8805Smckusick 	1) If there is "ifstmt" on the stack and input is anything other than
53*8805Smckusick 	   an else, then change the top of stack (TOS) to <stmt>.  Do a reduce.
54*8805Smckusick 	2) Use a switch statement to implement the following shift operations:
55*8805Smckusick 
56*8805Smckusick 	   TOS___		Input_____		Stack_____		Note____
57*8805Smckusick 	decl		decl		nothing
58*8805Smckusick 	anything else	decl		decl
59*8805Smckusick 	"dostmt"	while (..)			Change TOS to <stmt>
60*8805Smckusick 	anything else	while (..)	while
61*8805Smckusick 	"ifstmt"	else				Change TOS to "ifelse"
62*8805Smckusick 	{ <stmtl>	}				Change { <stmtl>
63*8805Smckusick 								to <stmtl>
64*8805Smckusick 			switch (..)	switch
65*8805Smckusick 			do		do
66*8805Smckusick 			for(..)		for
67*8805Smckusick 			;		<stmt>
68*8805Smckusick 			{		{ <stmt>
69*8805Smckusick 
70*8805Smckusick PARAMETERS:
71*8805Smckusick 	tk	An integer code for the maxi token scanned
72*8805Smckusick 
73*8805Smckusick RETURNS:
74*8805Smckusick 	Nothing
75*8805Smckusick 
76*8805Smckusick GLOBALS:
77*8805Smckusick 	break_comma =	Set to true when in a declaration but not initialization
78*8805Smckusick 	btype_2
79*8805Smckusick 	case_ind =
80*8805Smckusick 	cstk =
81*8805Smckusick 	i_l_follow =
82*8805Smckusick 	il =		Stack of indentation levels
83*8805Smckusick 	ind_level =
84*8805Smckusick 	p_stack =	Stack of token codes
85*8805Smckusick 	search_brace =	Set to true if we must look for possibility of moving a
86*8805Smckusick 			brace
87*8805Smckusick 	tos =		Pointer to top of p_stack, il, and cstk
88*8805Smckusick 
89*8805Smckusick CALLS:
90*8805Smckusick 	printf (lib)
91*8805Smckusick 	reduce
92*8805Smckusick 
93*8805Smckusick CALLED BY:
94*8805Smckusick 	main
95*8805Smckusick 
96*8805Smckusick HISTORY:
97*8805Smckusick 	initial coding 	November 1976	D A Willcox of CAC
98*8805Smckusick 
99*8805Smckusick */
100*8805Smckusick 
101*8805Smckusick #include "./indent_globs.h";
102*8805Smckusick #include "./indent_codes.h";
103*8805Smckusick 
104*8805Smckusick 
105*8805Smckusick int     p_stack[50] = stmt;
106*8805Smckusick  /* this is the parser's stack */
107*8805Smckusick int     il[50];    /* this stack stores indentation levels */
108*8805Smckusick int     cstk[50];  /* used to store case stmt indentation levels */
109*8805Smckusick int     tos = 0;   /* pointer to top of stack */
110*8805Smckusick 
111*8805Smckusick 
112*8805Smckusick parse (tk)
113*8805Smckusick int     tk;	   /* the code for the construct scanned */
114*8805Smckusick {
115*8805Smckusick     int     i;
116*8805Smckusick 
117*8805Smckusick #ifdef debug
118*8805Smckusick     printf ("%2d - %s\n", tk, token);
119*8805Smckusick #endif
120*8805Smckusick     while (p_stack[tos] == ifhead && tk != elselit) {
121*8805Smckusick     /* true if we have an if without an else */
122*8805Smckusick 	p_stack[tos] = stmt;   /* apply the if(..) stmt ::= stmt reduction */
123*8805Smckusick 	reduce ();	       /* see if this allows any reduction */
124*8805Smckusick     }
125*8805Smckusick 
126*8805Smckusick 
127*8805Smckusick     switch (tk) {	       /* go on and figure out what to do with the
128*8805Smckusick 			          input */
129*8805Smckusick 
130*8805Smckusick 	case decl: 	       /* scanned a declaration word */
131*8805Smckusick 	    search_brace = btype_2;
132*8805Smckusick 	/* indicate that following brace should be on same line */
133*8805Smckusick 	    if (p_stack[tos] != decl) {
134*8805Smckusick 	    /* only put one declaration onto stack */
135*8805Smckusick 		break_comma = true;
136*8805Smckusick 	    /* while in declaration, newline should be forced after comma */
137*8805Smckusick 		p_stack[++tos] = decl;
138*8805Smckusick 		il[tos] = i_l_follow;
139*8805Smckusick 
140*8805Smckusick 		if (ljust_decl) {
141*8805Smckusick 		/* only do if we want left justified declarations */
142*8805Smckusick 		    ind_level = 0;
143*8805Smckusick 		    for (i = tos - 1; i > 0; --i)
144*8805Smckusick 			if (p_stack[i] == decl)
145*8805Smckusick 			    ++ind_level;
146*8805Smckusick 		/* indentation is number of declaration levels deep we are */
147*8805Smckusick 		    i_l_follow = ind_level;
148*8805Smckusick 		}
149*8805Smckusick 	    }
150*8805Smckusick 	    break;
151*8805Smckusick 
152*8805Smckusick 	case ifstmt: 	       /* scanned if (...) */
153*8805Smckusick 	case dolit: 	       /* 'do' */
154*8805Smckusick 	case forstmt: 	       /* for (...) */
155*8805Smckusick 	    p_stack[++tos] = tk;
156*8805Smckusick 	    il[tos] = ind_level = i_l_follow;
157*8805Smckusick 	    ++i_l_follow;      /* subsequent statements should be indented 1 */
158*8805Smckusick 	    search_brace = btype_2;
159*8805Smckusick 	    break;
160*8805Smckusick 
161*8805Smckusick 	case lbrace: 	       /* scanned { */
162*8805Smckusick 	    break_comma = false;
163*8805Smckusick 	/* don't break comma in an initial list */
164*8805Smckusick 	    if (p_stack[tos] == stmt || p_stack[tos] == decl
165*8805Smckusick 				     || p_stack[tos] == stmtl)
166*8805Smckusick 		++i_l_follow;  /* it is a random, isolated stmt group or a
167*8805Smckusick 			          declaration */
168*8805Smckusick 	    else {
169*8805Smckusick 		if (s_code == e_code) {
170*8805Smckusick 		/* only do this if there is nothing on the line */
171*8805Smckusick 		    --ind_level;
172*8805Smckusick 		/* it is a group as part of a while, for, etc. */
173*8805Smckusick 		    if (p_stack[tos] == swstmt)
174*8805Smckusick 			--ind_level;
175*8805Smckusick 		/* for a switch, brace should be two levels out from the code
176*8805Smckusick 		*/
177*8805Smckusick 		}
178*8805Smckusick 	    }
179*8805Smckusick 
180*8805Smckusick 	    p_stack[++tos] = lbrace;
181*8805Smckusick 	    il[tos] = ind_level;
182*8805Smckusick 	    p_stack[++tos] = stmt;
183*8805Smckusick 	/* allow null stmt between braces */
184*8805Smckusick 	    il[tos] = i_l_follow;
185*8805Smckusick 	    break;
186*8805Smckusick 
187*8805Smckusick 	case whilestmt:        /* scanned while (...) */
188*8805Smckusick 	    if (p_stack[tos] == dohead) {
189*8805Smckusick 	    /* it is matched with do stmt */
190*8805Smckusick 		ind_level = i_l_follow = il[tos];
191*8805Smckusick 		p_stack[++tos] = whilestmt;
192*8805Smckusick 		il[tos] = ind_level = i_l_follow;
193*8805Smckusick 	    }
194*8805Smckusick 	    else {	       /* it is a while loop */
195*8805Smckusick 		p_stack[++tos] = whilestmt;
196*8805Smckusick 		il[tos] = i_l_follow;
197*8805Smckusick 		++i_l_follow;
198*8805Smckusick 		search_brace = btype_2;
199*8805Smckusick 	    }
200*8805Smckusick 
201*8805Smckusick 	    break;
202*8805Smckusick 
203*8805Smckusick 	case elselit: 	       /* scanned an else */
204*8805Smckusick 
205*8805Smckusick 	    if (p_stack[tos] != ifhead) {
206*8805Smckusick 		printf ("%d: Unmatched else\n", line_no);
207*8805Smckusick 	    }
208*8805Smckusick 	    else {
209*8805Smckusick 		ind_level = il[tos];
210*8805Smckusick 	    /* indentation for else should be same as for if */
211*8805Smckusick 		i_l_follow = ind_level + 1;
212*8805Smckusick 	    /* everything following should be in 1 level */
213*8805Smckusick 		p_stack[tos] = elsehead;
214*8805Smckusick 	    /* remember if with else */
215*8805Smckusick 		search_brace = btype_2;
216*8805Smckusick 	    }
217*8805Smckusick 
218*8805Smckusick 	    break;
219*8805Smckusick 
220*8805Smckusick 	case rbrace: 	       /* scanned a } */
221*8805Smckusick 	/* stack should have <lbrace> <stmt> or <lbrace> <stmtl> */
222*8805Smckusick 	    if (p_stack[tos - 1] == lbrace) {
223*8805Smckusick 		ind_level = i_l_follow = il[--tos];
224*8805Smckusick 		p_stack[tos] = stmt;
225*8805Smckusick 	    }
226*8805Smckusick 	    else {
227*8805Smckusick 		printf ("%d: Stmt nesting error\n", line_no);
228*8805Smckusick 	    }
229*8805Smckusick 
230*8805Smckusick 	    break;
231*8805Smckusick 
232*8805Smckusick 	case swstmt: 	       /* had switch (...) */
233*8805Smckusick 	    p_stack[++tos] = swstmt;
234*8805Smckusick 	    cstk[tos] = case_ind;
235*8805Smckusick 	/* save current case indent level */
236*8805Smckusick 	    il[tos] = i_l_follow;
237*8805Smckusick 	    case_ind = i_l_follow + 1;
238*8805Smckusick 	/* cases should be one level down from switch */
239*8805Smckusick 	    i_l_follow + = 2;  /* statements should be two levels in */
240*8805Smckusick 	    search_brace = btype_2;
241*8805Smckusick 	    break;
242*8805Smckusick 
243*8805Smckusick 	case semicolon:        /* this indicates a simple stmt */
244*8805Smckusick 	    break_comma = false;
245*8805Smckusick 	/* turn off flag to break after commas in a declaration */
246*8805Smckusick 	    p_stack[++tos] = stmt;
247*8805Smckusick 	    il[tos] = ind_level;
248*8805Smckusick 	    break;
249*8805Smckusick 
250*8805Smckusick 	default: 	       /* this is an error */
251*8805Smckusick 	    printf ("%d: Unknown code to parser - %d\n", line_no, tk);
252*8805Smckusick 	    return;
253*8805Smckusick 
254*8805Smckusick 
255*8805Smckusick     }			       /* end of switch */
256*8805Smckusick 
257*8805Smckusick     reduce ();		       /* see if any reduction can be done */
258*8805Smckusick #ifdef debug
259*8805Smckusick     for (i = 1; i <= tos; ++i)
260*8805Smckusick 	printf ("(%d %d)", p_stack[i], il[i]);
261*8805Smckusick     printf ("\n");
262*8805Smckusick #endif
263*8805Smckusick     return;
264*8805Smckusick }
265*8805Smckusick /*
266*8805Smckusick 
267*8805Smckusick 			  Copyright (C) 1976
268*8805Smckusick 				by the
269*8805Smckusick 			  Board of Trustees
270*8805Smckusick 				of the
271*8805Smckusick 			University of Illinois
272*8805Smckusick 
273*8805Smckusick 			 All rights reserved
274*8805Smckusick 
275*8805Smckusick 
276*8805Smckusick NAME:
277*8805Smckusick 	reduce
278*8805Smckusick 
279*8805Smckusick FUNCTION:
280*8805Smckusick 	Implements the reduce part of the parsing algorithm
281*8805Smckusick 
282*8805Smckusick ALGORITHM:
283*8805Smckusick 	The following reductions are done.  Reductions are repeated until no
284*8805Smckusick 	more are possible.
285*8805Smckusick 
286*8805Smckusick 	Old___ TOS___		New___ TOS___
287*8805Smckusick 	<stmt> <stmt>	<stmtl>
288*8805Smckusick 	<stmtl> <stmt>	<stmtl>
289*8805Smckusick 	do <stmt>	"dostmt"
290*8805Smckusick 	if <stmt>	"ifstmt"
291*8805Smckusick 	switch <stmt>	<stmt>
292*8805Smckusick 	decl <stmt>	<stmt>
293*8805Smckusick 	"ifelse" <stmt>	<stmt>
294*8805Smckusick 	for <stmt>	<stmt>
295*8805Smckusick 	while <stmt>	<stmt>
296*8805Smckusick 	"dostmt" while	<stmt>
297*8805Smckusick 
298*8805Smckusick 	On each reduction, i_l_follow (the indentation for the following line)
299*8805Smckusick 	is set to the indentation level associated with the old TOS.
300*8805Smckusick 
301*8805Smckusick PARAMETERS:
302*8805Smckusick 	None
303*8805Smckusick 
304*8805Smckusick RETURNS:
305*8805Smckusick 	Nothing
306*8805Smckusick 
307*8805Smckusick GLOBALS:
308*8805Smckusick 	cstk
309*8805Smckusick 	i_l_follow =
310*8805Smckusick 	il
311*8805Smckusick 	p_stack =
312*8805Smckusick 	tos =
313*8805Smckusick 
314*8805Smckusick CALLS:
315*8805Smckusick 	None
316*8805Smckusick 
317*8805Smckusick CALLED BY:
318*8805Smckusick 	parse
319*8805Smckusick 
320*8805Smckusick HISTORY:
321*8805Smckusick 	initial coding 	November 1976	D A Willcox of CAC
322*8805Smckusick 
323*8805Smckusick */
324*8805Smckusick /*----------------------------------------------*\
325*8805Smckusick |   REDUCTION PHASE
326*8805Smckusick \*----------------------------------------------*/
327*8805Smckusick reduce () {
328*8805Smckusick 
329*8805Smckusick     register int    i;
330*8805Smckusick  /* local looping variable */
331*8805Smckusick 
332*8805Smckusick     for (;;) {		       /* keep looping until there is nothing left to
333*8805Smckusick 			          reduce */
334*8805Smckusick 
335*8805Smckusick 	switch (p_stack[tos]) {
336*8805Smckusick 
337*8805Smckusick 	    case stmt:
338*8805Smckusick 		switch (p_stack[tos - 1]) {
339*8805Smckusick 
340*8805Smckusick 		    case stmt:
341*8805Smckusick 		    case stmtl:
342*8805Smckusick 		    /* stmtl stmt or stmt stmt */
343*8805Smckusick 			p_stack[--tos] = stmtl;
344*8805Smckusick 			break;
345*8805Smckusick 
346*8805Smckusick 		    case dolit:
347*8805Smckusick 		    /* <do> <stmt> */
348*8805Smckusick 			p_stack[--tos] = dohead;
349*8805Smckusick 			i_l_follow = il[tos];
350*8805Smckusick 			break;
351*8805Smckusick 
352*8805Smckusick 		    case ifstmt:
353*8805Smckusick 		    /* <if> <stmt> */
354*8805Smckusick 			p_stack[--tos] = ifhead;
355*8805Smckusick 			for (i = tos - 1;
356*8805Smckusick 				(
357*8805Smckusick 				    p_stack[i] != stmt
358*8805Smckusick 				    &&
359*8805Smckusick 				    p_stack[i] != stmtl
360*8805Smckusick 				    &&
361*8805Smckusick 				    p_stack[i] != lbrace
362*8805Smckusick 				);
363*8805Smckusick 				--i);
364*8805Smckusick 			i_l_follow = il[i];
365*8805Smckusick 		    /* for the time being, we will assume that there is no else
366*8805Smckusick 		       on this if, and set the indentation level accordingly.
367*8805Smckusick 		       If an else is scanned, it will be fixed up later */
368*8805Smckusick 			break;
369*8805Smckusick 
370*8805Smckusick 		    case swstmt:
371*8805Smckusick 		    /* <switch> <stmt> */
372*8805Smckusick 			case_ind = cstk[tos - 1];
373*8805Smckusick 
374*8805Smckusick 		    case decl: /* finish of a declaration */
375*8805Smckusick 		    case elsehead:
376*8805Smckusick 		    /* <<if> <stmt> else> <stmt> */
377*8805Smckusick 		    case forstmt:
378*8805Smckusick 		    /* <for> <stmt> */
379*8805Smckusick 		    case whilestmt:
380*8805Smckusick 		    /* <while> <stmt> */
381*8805Smckusick 			p_stack[--tos] = stmt;
382*8805Smckusick 			i_l_follow = il[tos];
383*8805Smckusick 			break;
384*8805Smckusick 
385*8805Smckusick 		    default:   /* <anything else> <stmt> */
386*8805Smckusick 			return;
387*8805Smckusick 
388*8805Smckusick 		}	       /* end of section for <stmt> on top of stack */
389*8805Smckusick 		break;
390*8805Smckusick 
391*8805Smckusick 	    case whilestmt:    /* while (...) on top */
392*8805Smckusick 		if (p_stack[tos - 1] == dohead) {
393*8805Smckusick 		/* it is termination of a do while */
394*8805Smckusick 		    p_stack[--tos] = stmt;
395*8805Smckusick 		    break;
396*8805Smckusick 		}
397*8805Smckusick 		else
398*8805Smckusick 		    return;
399*8805Smckusick 
400*8805Smckusick 	    default: 	       /* anything else on top */
401*8805Smckusick 		return;
402*8805Smckusick 
403*8805Smckusick 	}		       /* end of big switch */
404*8805Smckusick 
405*8805Smckusick     }			       /* end of reduction phase for (;;) */
406*8805Smckusick }
407