121971Sdist /* 221971Sdist * Copyright (c) 1980 Regents of the University of California. 321971Sdist * All rights reserved. The Berkeley software License Agreement 421971Sdist * specifies the terms and conditions for redistribution. 521971Sdist */ 68805Smckusick 721971Sdist #ifndef lint 8*33231Sbostic static char sccsid[] = "@(#)parse.c 5.4 (Berkeley) 01/02/88"; 921971Sdist #endif not lint 1021971Sdist 1124456Smckusick /*- 1224456Smckusick * 1324456Smckusick * Copyright (C) 1976 1424456Smckusick * by the 1524456Smckusick * Board of Trustees 1624456Smckusick * of the 1724456Smckusick * University of Illinois 1824456Smckusick * 1924456Smckusick * All rights reserved 2024456Smckusick * 2124456Smckusick * 2224456Smckusick * FILE NAME: 2324456Smckusick * parse.c 2424456Smckusick * 2524456Smckusick * PURPOSE: 2624456Smckusick * Contains the routines which keep track of the parse stack. 2724456Smckusick * 2824456Smckusick * GLOBALS: 2924456Smckusick * ps.p_stack = The parse stack, set by both routines 3024456Smckusick * ps.il = Stack of indentation levels, set by parse 3124456Smckusick * ps.cstk = Stack of case statement indentation levels, set by parse 3224456Smckusick * ps.tos = Pointer to top of stack, set by both routines. 3324456Smckusick * 3424456Smckusick * FUNCTIONS: 3524456Smckusick * parse 3624456Smckusick * reduce 3724456Smckusick */ 3824456Smckusick /*- 3924456Smckusick * Copyright (C) 1976 by the Board of Trustees of the University of Illinois 4024456Smckusick * 4124456Smckusick * All rights reserved 4224456Smckusick * 4324456Smckusick * 4424456Smckusick * NAME: parse 4524456Smckusick * 4624456Smckusick * FUNCTION: Parse is given one input which is a "maxi token" just scanned 4724456Smckusick * from input. Maxi tokens are signifigant constructs such as else, {, 4824456Smckusick * do, if (...), etc. Parse works with reduce to maintain a parse stack 4924456Smckusick * of these constructs. Parse is responsible for the "shift" portion of 5024456Smckusick * the parse algorithm, and reduce handles the "reduce" portion. 5124456Smckusick * 5224456Smckusick * HISTORY: initial coding November 1976 D A Willcox of CAC 5324456Smckusick * 5424456Smckusick */ 558805Smckusick 56*33231Sbostic #include "./indent_globs.h" 57*33231Sbostic #include "./indent_codes.h" 588805Smckusick 598805Smckusick 608805Smckusick 618805Smckusick 6224456Smckusick parse(tk) 6324456Smckusick int tk; /* the code for the construct scanned */ 648805Smckusick { 6524456Smckusick int i; 668805Smckusick 678805Smckusick #ifdef debug 6824456Smckusick printf("%2d - %s\n", tk, token); 698805Smckusick #endif 7024456Smckusick while (ps.p_stack[ps.tos] == ifhead && tk != elselit) { 7124456Smckusick /* true if we have an if without an else */ 7224456Smckusick ps.p_stack[ps.tos] = stmt; /* apply the if(..) stmt ::= stmt 7324456Smckusick * reduction */ 7424456Smckusick reduce(); /* see if this allows any reduction */ 758805Smckusick } 768805Smckusick 778805Smckusick 7824456Smckusick switch (tk) { /* go on and figure out what to do with 7924456Smckusick * the input */ 808805Smckusick 8124456Smckusick case decl: /* scanned a declaration word */ 8224456Smckusick ps.search_brace = btype_2; 8324456Smckusick /* indicate that following brace should be on same line */ 8424456Smckusick if (ps.p_stack[ps.tos] != decl) { /* only put one declaration onto 8524456Smckusick * stack */ 8624456Smckusick break_comma = true; /* while in declaration, newline 8724456Smckusick * should be forced after comma */ 8824456Smckusick ps.p_stack[++ps.tos] = decl; 8924456Smckusick ps.il[ps.tos] = ps.i_l_follow; 908805Smckusick 9124456Smckusick if (ps.ljust_decl) { /* only do if we want left 9224456Smckusick * justified declarations */ 9324456Smckusick ps.ind_level = 0; 9424456Smckusick for (i = ps.tos - 1; i > 0; --i) 9524456Smckusick if (ps.p_stack[i] == decl) 9624456Smckusick ++ps.ind_level; /* indentation is number 9724456Smckusick * of declaration levels 9824456Smckusick * deep we are */ 9924456Smckusick ps.i_l_follow = ps.ind_level; 1008805Smckusick } 1018805Smckusick } 1028805Smckusick break; 1038805Smckusick 10424456Smckusick case ifstmt: /* scanned if (...) */ 10524456Smckusick if (ps.p_stack[ps.tos] == elsehead && ps.else_if) /* "else if ..." */ 10624456Smckusick ps.i_l_follow = ps.il[ps.tos]; 10724456Smckusick case dolit: /* 'do' */ 10824456Smckusick case forstmt: /* for (...) */ 10924456Smckusick ps.p_stack[++ps.tos] = tk; 11024456Smckusick ps.il[ps.tos] = ps.ind_level = ps.i_l_follow; 11124456Smckusick ++ps.i_l_follow; /* subsequent statements should be 11224456Smckusick * indented 1 */ 11324456Smckusick ps.search_brace = btype_2; 1148805Smckusick break; 1158805Smckusick 11624456Smckusick case lbrace: /* scanned { */ 11724456Smckusick break_comma = false;/* don't break comma in an initial list */ 11824456Smckusick if (ps.p_stack[ps.tos] == stmt || ps.p_stack[ps.tos] == decl 11924456Smckusick || ps.p_stack[ps.tos] == stmtl) 12024456Smckusick ++ps.i_l_follow; /* it is a random, isolated stmt group or 12124456Smckusick * a declaration */ 1228805Smckusick else { 1238805Smckusick if (s_code == e_code) { 12424456Smckusick /* only do this if there is nothing on the line */ 12524456Smckusick --ps.ind_level; 12624456Smckusick /* it is a group as part of a while, for, etc. */ 12724456Smckusick if (ps.p_stack[ps.tos] == swstmt && ps.case_indent) 12824456Smckusick --ps.ind_level; 12924456Smckusick /* 13024456Smckusick * for a switch, brace should be two levels out from 13124456Smckusick * the code 13224456Smckusick */ 1338805Smckusick } 1348805Smckusick } 1358805Smckusick 13624456Smckusick ps.p_stack[++ps.tos] = lbrace; 13724456Smckusick ps.il[ps.tos] = ps.ind_level; 13824456Smckusick ps.p_stack[++ps.tos] = stmt; 13924456Smckusick /* allow null stmt between braces */ 14024456Smckusick ps.il[ps.tos] = ps.i_l_follow; 1418805Smckusick break; 1428805Smckusick 14324456Smckusick case whilestmt: /* scanned while (...) */ 14424456Smckusick if (ps.p_stack[ps.tos] == dohead) { 14524456Smckusick /* it is matched with do stmt */ 14624456Smckusick ps.ind_level = ps.i_l_follow = ps.il[ps.tos]; 14724456Smckusick ps.p_stack[++ps.tos] = whilestmt; 14824456Smckusick ps.il[ps.tos] = ps.ind_level = ps.i_l_follow; 1498805Smckusick } 15024456Smckusick else { /* it is a while loop */ 15124456Smckusick ps.p_stack[++ps.tos] = whilestmt; 15224456Smckusick ps.il[ps.tos] = ps.i_l_follow; 15324456Smckusick ++ps.i_l_follow; 15424456Smckusick ps.search_brace = btype_2; 1558805Smckusick } 1568805Smckusick 1578805Smckusick break; 1588805Smckusick 15924456Smckusick case elselit: /* scanned an else */ 1608805Smckusick 16124456Smckusick if (ps.p_stack[ps.tos] != ifhead) 16224456Smckusick diag(1,"Unmatched 'else'"); 1638805Smckusick else { 16424456Smckusick ps.ind_level = ps.il[ps.tos]; /* indentation for else should be same as for if */ 16524456Smckusick ps.i_l_follow = ps.ind_level + 1; /* everything following should be in 1 level */ 16624456Smckusick ps.p_stack[ps.tos] = elsehead; 16724456Smckusick /* remember if with else */ 16824456Smckusick ps.search_brace = btype_2; 1698805Smckusick } 1708805Smckusick 1718805Smckusick break; 1728805Smckusick 17324456Smckusick case rbrace: /* scanned a } */ 17424456Smckusick /* stack should have <lbrace> <stmt> or <lbrace> <stmtl> */ 17524456Smckusick if (ps.p_stack[ps.tos - 1] == lbrace) { 17624456Smckusick ps.ind_level = ps.i_l_follow = ps.il[--ps.tos]; 17724456Smckusick ps.p_stack[ps.tos] = stmt; 1788805Smckusick } 17924456Smckusick else 18024456Smckusick diag(1,"Stmt nesting error."); 1818805Smckusick break; 1828805Smckusick 18324456Smckusick case swstmt: /* had switch (...) */ 18424456Smckusick ps.p_stack[++ps.tos] = swstmt; 18524456Smckusick ps.cstk[ps.tos] = case_ind; 18624456Smckusick /* save current case indent level */ 18724456Smckusick ps.il[ps.tos] = ps.i_l_follow; 18824456Smckusick case_ind = ps.i_l_follow + ps.case_indent; /* cases should be one 18924456Smckusick * level down from 19024456Smckusick * switch */ 191*33231Sbostic ps.i_l_follow += ps.case_indent + 1; /* statements should be 19224456Smckusick * two levels in */ 19324456Smckusick ps.search_brace = btype_2; 1948805Smckusick break; 1958805Smckusick 19624456Smckusick case semicolon: /* this indicates a simple stmt */ 19724456Smckusick break_comma = false;/* turn off flag to break after commas in 19824456Smckusick * a declaration */ 19924456Smckusick ps.p_stack[++ps.tos] = stmt; 20024456Smckusick ps.il[ps.tos] = ps.ind_level; 2018805Smckusick break; 2028805Smckusick 20324456Smckusick default: /* this is an error */ 20424456Smckusick diag(1,"Unknown code to parser"); 2058805Smckusick return; 2068805Smckusick 2078805Smckusick 20824456Smckusick } /* end of switch */ 2098805Smckusick 21024456Smckusick reduce(); /* see if any reduction can be done */ 2118805Smckusick #ifdef debug 21224456Smckusick for (i = 1; i <= ps.tos; ++i) 21324456Smckusick printf("(%d %d)", ps.p_stack[i], ps.il[i]); 21424456Smckusick printf("\n"); 2158805Smckusick #endif 2168805Smckusick return; 2178805Smckusick } 21824456Smckusick /* 21924456Smckusick * Copyright (C) 1976 by the Board of Trustees of the University of Illinois 22024456Smckusick * 22124456Smckusick * All rights reserved 22224456Smckusick * 22324456Smckusick * 22424456Smckusick * NAME: reduce 22524456Smckusick * 22624456Smckusick * FUNCTION: Implements the reduce part of the parsing algorithm 22724456Smckusick * 22824456Smckusick * ALGORITHM: The following reductions are done. Reductions are repeated 22924456Smckusick * until no more are possible. 23024456Smckusick * 23124456Smckusick * Old TOS New TOS <stmt> <stmt> <stmtl> <stmtl> <stmt> <stmtl> do 23224456Smckusick * <stmt> "dostmt" if <stmt> "ifstmt" switch <stmt> <stmt> 23324456Smckusick * decl <stmt> <stmt> "ifelse" <stmt> <stmt> for <stmt> <stmt> 23424456Smckusick * while <stmt> <stmt> "dostmt" while <stmt> 23524456Smckusick * 23624456Smckusick * On each reduction, ps.i_l_follow (the indentation for the following line) is 23724456Smckusick * set to the indentation level associated with the old TOS. 23824456Smckusick * 23924456Smckusick * PARAMETERS: None 24024456Smckusick * 24124456Smckusick * RETURNS: Nothing 24224456Smckusick * 24324456Smckusick * GLOBALS: ps.cstk ps.i_l_follow = ps.il ps.p_stack = ps.tos = 24424456Smckusick * 24524456Smckusick * CALLS: None 24624456Smckusick * 24724456Smckusick * CALLED BY: parse 24824456Smckusick * 24924456Smckusick * HISTORY: initial coding November 1976 D A Willcox of CAC 25024456Smckusick * 25124456Smckusick */ 2528805Smckusick /*----------------------------------------------*\ 25324456Smckusick * | REDUCTION PHASE 2548805Smckusick \*----------------------------------------------*/ 25524456Smckusick reduce() { 2568805Smckusick 25724456Smckusick register int i; 2588805Smckusick 25924456Smckusick for (;;) { /* keep looping until there is nothing 26024456Smckusick * left to reduce */ 2618805Smckusick 26224456Smckusick switch (ps.p_stack[ps.tos]) { 2638805Smckusick 2648805Smckusick case stmt: 26524456Smckusick switch (ps.p_stack[ps.tos - 1]) { 2668805Smckusick 2678805Smckusick case stmt: 2688805Smckusick case stmtl: 26924456Smckusick /* stmtl stmt or stmt stmt */ 27024456Smckusick ps.p_stack[--ps.tos] = stmtl; 2718805Smckusick break; 2728805Smckusick 27324456Smckusick case dolit: /* <do> <stmt> */ 27424456Smckusick ps.p_stack[--ps.tos] = dohead; 27524456Smckusick ps.i_l_follow = ps.il[ps.tos]; 2768805Smckusick break; 2778805Smckusick 2788805Smckusick case ifstmt: 27924456Smckusick /* <if> <stmt> */ 28024456Smckusick ps.p_stack[--ps.tos] = ifhead; 28124456Smckusick for (i = ps.tos - 1; 2828805Smckusick ( 28324456Smckusick ps.p_stack[i] != stmt 2848805Smckusick && 28524456Smckusick ps.p_stack[i] != stmtl 2868805Smckusick && 28724456Smckusick ps.p_stack[i] != lbrace 2888805Smckusick ); 2898805Smckusick --i); 29024456Smckusick ps.i_l_follow = ps.il[i]; 29124456Smckusick /* 29224456Smckusick * for the time being, we will assume that there 29324456Smckusick * is no else on this if, and set the indentation 29424456Smckusick * level accordingly. If an else is scanned, it 29524456Smckusick * will be fixed up later 29624456Smckusick */ 2978805Smckusick break; 2988805Smckusick 2998805Smckusick case swstmt: 30024456Smckusick /* <switch> <stmt> */ 30124456Smckusick case_ind = ps.cstk[ps.tos - 1]; 3028805Smckusick 30324456Smckusick case decl: /* finish of a declaration */ 3048805Smckusick case elsehead: 30524456Smckusick /* <<if> <stmt> else> <stmt> */ 3068805Smckusick case forstmt: 30724456Smckusick /* <for> <stmt> */ 3088805Smckusick case whilestmt: 30924456Smckusick /* <while> <stmt> */ 31024456Smckusick ps.p_stack[--ps.tos] = stmt; 31124456Smckusick ps.i_l_follow = ps.il[ps.tos]; 3128805Smckusick break; 3138805Smckusick 31424456Smckusick default: /* <anything else> <stmt> */ 3158805Smckusick return; 3168805Smckusick 31724456Smckusick } /* end of section for <stmt> on top of 31824456Smckusick * stack */ 3198805Smckusick break; 3208805Smckusick 32124456Smckusick case whilestmt: /* while (...) on top */ 32224456Smckusick if (ps.p_stack[ps.tos - 1] == dohead) { 32324456Smckusick /* it is termination of a do while */ 32424456Smckusick ps.p_stack[--ps.tos] = stmt; 3258805Smckusick break; 3268805Smckusick } 3278805Smckusick else 3288805Smckusick return; 3298805Smckusick 33024456Smckusick default: /* anything else on top */ 3318805Smckusick return; 3328805Smckusick 33324456Smckusick } 33424456Smckusick } 3358805Smckusick } 336