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