1 static char sccsid[] = "@(#)parse.c 4.1 (Berkeley) 10/21/82"; 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 */ 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___ Input_____ Stack_____ Note____ 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 */ 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 /* 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___ TOS___ New___ TOS___ 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 320 HISTORY: 321 initial coding November 1976 D A Willcox of CAC 322 323 */ 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 } 407