[unix-history] / usr / src / usr.bin / indent / parse.c

static char sccsid[] = "@(#)parse.c	4.1	(Berkeley)	%G%";

/*

			  Copyright (C) 1976
				by the
			  Board of Trustees
				of the
			University of Illinois

			 All rights reserved


FILE NAME:
	parse.c

PURPOSE:
	Contains the routines which keep track of the parse stack.

GLOBALS:
	p_stack =	The parse stack, set by both routines
	il =		Stack of indentation levels, set by parse
	cstk =		Stack of case statement indentation levels, set by parse
	tos =		Pointer to top of stack, set by both routines.

FUNCTIONS:
	parse
	reduce
*/\f
/*

			  Copyright (C) 1976
				by the
			  Board of Trustees
				of the
			University of Illinois

			 All rights reserved


NAME:
	parse

FUNCTION:
	Parse is given one input which is a "maxi token" just scanned from
	input.  Maxi tokens are signifigant constructs such as else, {, do,
	if (...), etc.  Parse works with reduce to maintain a parse stack
	of these constructs.  Parse is responsible for the "shift" portion
	of the parse algorithm, and reduce handles the "reduce" portion.

ALGORITHM:
	1) If there is "ifstmt" on the stack and input is anything other than
	   an else, then change the top of stack (TOS) to <stmt>.  Do a reduce.
	2) Use a switch statement to implement the following shift operations:

	   TOS\b\b\b___		Input\b\b\b\b\b_____		Stack\b\b\b\b\b_____		Note\b\b\b\b____
	decl		decl		nothing
	anything else	decl		decl
	"dostmt"	while (..)			Change TOS to <stmt>
	anything else	while (..)	while
	"ifstmt"	else				Change TOS to "ifelse"
	{ <stmtl>	}				Change { <stmtl> 
								to <stmtl>
			switch (..)	switch
			do		do
			for(..)		for
			;		<stmt>
			{		{ <stmt>

PARAMETERS:
	tk	An integer code for the maxi token scanned

RETURNS:
	Nothing

GLOBALS:
	break_comma =	Set to true when in a declaration but not initialization
	btype_2
	case_ind =
	cstk =
	i_l_follow =
	il =		Stack of indentation levels
	ind_level =
	p_stack =	Stack of token codes
	search_brace =	Set to true if we must look for possibility of moving a
			brace
	tos =		Pointer to top of p_stack, il, and cstk

CALLS:
	printf (lib)
	reduce

CALLED BY:
	main

HISTORY:
	initial coding 	November 1976	D A Willcox of CAC

*/\f

#include "./indent_globs.h";
#include "./indent_codes.h";


int     p_stack[50] = stmt;
 /* this is the parser's stack */
int     il[50];    /* this stack stores indentation levels */
int     cstk[50];  /* used to store case stmt indentation levels */
int     tos = 0;   /* pointer to top of stack */


parse (tk)
int     tk;	   /* the code for the construct scanned */
{
    int     i;

#ifdef debug
    printf ("%2d - %s\n", tk, token);
#endif
    while (p_stack[tos] == ifhead && tk != elselit) {
    /* true if we have an if without an else */
	p_stack[tos] = stmt;   /* apply the if(..) stmt ::= stmt reduction */
	reduce ();	       /* see if this allows any reduction */
    }


    switch (tk) {	       /* go on and figure out what to do with the
			          input */

	case decl: 	       /* scanned a declaration word */
	    search_brace = btype_2;
	/* indicate that following brace should be on same line */
	    if (p_stack[tos] != decl) {
	    /* only put one declaration onto stack */
		break_comma = true;
	    /* while in declaration, newline should be forced after comma */
		p_stack[++tos] = decl;
		il[tos] = i_l_follow;

		if (ljust_decl) {
		/* only do if we want left justified declarations */
		    ind_level = 0;
		    for (i = tos - 1; i > 0; --i)
			if (p_stack[i] == decl)
			    ++ind_level;
		/* indentation is number of declaration levels deep we are */
		    i_l_follow = ind_level;
		}
	    }
	    break;

	case ifstmt: 	       /* scanned if (...) */
	case dolit: 	       /* 'do' */
	case forstmt: 	       /* for (...) */
	    p_stack[++tos] = tk;
	    il[tos] = ind_level = i_l_follow;
	    ++i_l_follow;      /* subsequent statements should be indented 1 */
	    search_brace = btype_2;
	    break;

	case lbrace: 	       /* scanned { */
	    break_comma = false;
	/* don't break comma in an initial list */
	    if (p_stack[tos] == stmt || p_stack[tos] == decl
				     || p_stack[tos] == stmtl)
		++i_l_follow;  /* it is a random, isolated stmt group or a
			          declaration */
	    else {
		if (s_code == e_code) {
		/* only do this if there is nothing on the line */
		    --ind_level;
		/* it is a group as part of a while, for, etc. */
		    if (p_stack[tos] == swstmt)
			--ind_level;
		/* for a switch, brace should be two levels out from the code 
		*/
		}
	    }

	    p_stack[++tos] = lbrace;
	    il[tos] = ind_level;
	    p_stack[++tos] = stmt;
	/* allow null stmt between braces */
	    il[tos] = i_l_follow;
	    break;

	case whilestmt:        /* scanned while (...) */
	    if (p_stack[tos] == dohead) {
	    /* it is matched with do stmt */
		ind_level = i_l_follow = il[tos];
		p_stack[++tos] = whilestmt;
		il[tos] = ind_level = i_l_follow;
	    }
	    else {	       /* it is a while loop */
		p_stack[++tos] = whilestmt;
		il[tos] = i_l_follow;
		++i_l_follow;
		search_brace = btype_2;
	    }

	    break;

	case elselit: 	       /* scanned an else */

	    if (p_stack[tos] != ifhead) {
		printf ("%d: Unmatched else\n", line_no);
	    }
	    else {
		ind_level = il[tos];
	    /* indentation for else should be same as for if */
		i_l_follow = ind_level + 1;
	    /* everything following should be in 1 level */
		p_stack[tos] = elsehead;
	    /* remember if with else */
		search_brace = btype_2;
	    }

	    break;

	case rbrace: 	       /* scanned a } */
	/* stack should have <lbrace> <stmt> or <lbrace> <stmtl> */
	    if (p_stack[tos - 1] == lbrace) {
		ind_level = i_l_follow = il[--tos];
		p_stack[tos] = stmt;
	    }
	    else {
		printf ("%d: Stmt nesting error\n", line_no);
	    }

	    break;

	case swstmt: 	       /* had switch (...) */
	    p_stack[++tos] = swstmt;
	    cstk[tos] = case_ind;
	/* save current case indent level */
	    il[tos] = i_l_follow;
	    case_ind = i_l_follow + 1;
	/* cases should be one level down from switch */
	    i_l_follow + = 2;  /* statements should be two levels in */
	    search_brace = btype_2;
	    break;

	case semicolon:        /* this indicates a simple stmt */
	    break_comma = false;
	/* turn off flag to break after commas in a declaration */
	    p_stack[++tos] = stmt;
	    il[tos] = ind_level;
	    break;

	default: 	       /* this is an error */
	    printf ("%d: Unknown code to parser - %d\n", line_no, tk);
	    return;


    }			       /* end of switch */

    reduce ();		       /* see if any reduction can be done */
#ifdef debug
    for (i = 1; i <= tos; ++i)
	printf ("(%d %d)", p_stack[i], il[i]);
    printf ("\n");
#endif
    return;
}
\f/*

			  Copyright (C) 1976
				by the
			  Board of Trustees
				of the
			University of Illinois

			 All rights reserved


NAME:
	reduce

FUNCTION:
	Implements the reduce part of the parsing algorithm

ALGORITHM:
	The following reductions are done.  Reductions are repeated until no
	more are possible.

	Old\b\b\b___ TOS\b\b\b___		New\b\b\b___ TOS\b\b\b___
	<stmt> <stmt>	<stmtl>
	<stmtl> <stmt>	<stmtl>
	do <stmt>	"dostmt"
	if <stmt>	"ifstmt"
	switch <stmt>	<stmt>
	decl <stmt>	<stmt>
	"ifelse" <stmt>	<stmt>
	for <stmt>	<stmt>
	while <stmt>	<stmt>
	"dostmt" while	<stmt>

	On each reduction, i_l_follow (the indentation for the following line)
	is set to the indentation level associated with the old TOS.

PARAMETERS:
	None

RETURNS:
	Nothing

GLOBALS:
	cstk
	i_l_follow =
	il
	p_stack =
	tos =

CALLS:
	None

CALLED BY:
	parse
\1c
HISTORY:
	initial coding 	November 1976	D A Willcox of CAC

*/\f
/*----------------------------------------------*\
|   REDUCTION PHASE
\*----------------------------------------------*/
reduce () {

    register int    i;
 /* local looping variable */

    for (;;) {		       /* keep looping until there is nothing left to
			          reduce */

	switch (p_stack[tos]) {

	    case stmt: 
		switch (p_stack[tos - 1]) {

		    case stmt: 
		    case stmtl: 
		    /* stmtl stmt or stmt stmt */
			p_stack[--tos] = stmtl;
			break;

		    case dolit: 
		    /* <do> <stmt> */
			p_stack[--tos] = dohead;
			i_l_follow = il[tos];
			break;

		    case ifstmt: 
		    /* <if> <stmt> */
			p_stack[--tos] = ifhead;
			for (i = tos - 1;
				(
				    p_stack[i] != stmt
				    &&
				    p_stack[i] != stmtl
				    &&
				    p_stack[i] != lbrace
				);
				--i);
			i_l_follow = il[i];
		    /* for the time being, we will assume that there is no else
		       on this if, and set the indentation level accordingly.
		       If an else is scanned, it will be fixed up later */
			break;

		    case swstmt: 
		    /* <switch> <stmt> */
			case_ind = cstk[tos - 1];

		    case decl: /* finish of a declaration */
		    case elsehead: 
		    /* <<if> <stmt> else> <stmt> */
		    case forstmt: 
		    /* <for> <stmt> */
		    case whilestmt: 
		    /* <while> <stmt> */
			p_stack[--tos] = stmt;
			i_l_follow = il[tos];
			break;

		    default:   /* <anything else> <stmt> */
			return;

		}	       /* end of section for <stmt> on top of stack */
		break;

	    case whilestmt:    /* while (...) on top */
		if (p_stack[tos - 1] == dohead) {
		/* it is termination of a do while */
		    p_stack[--tos] = stmt;
		    break;
		}
		else
		    return;

	    default: 	       /* anything else on top */
		return;

	}		       /* end of big switch */

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