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 | } |