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