121971Sdist /* 221971Sdist * Copyright (c) 1980 Regents of the University of California. 333767Sbostic * Copyright (c) 1976 Board of Trustees of the University of Illinois. 433767Sbostic * All rights reserved. 533767Sbostic * 633767Sbostic * Redistribution and use in source and binary forms are permitted 7*34885Sbostic * provided that the above copyright notice and this paragraph are 8*34885Sbostic * duplicated in all such forms and that any documentation, 9*34885Sbostic * advertising materials, and other materials related to such 10*34885Sbostic * distribution and use acknowledge that the software was developed 11*34885Sbostic * by the University of California, Berkeley and the University 12*34885Sbostic * of Illinois, Urbana. The name of either 13*34885Sbostic * University may not be used to endorse or promote products derived 14*34885Sbostic * from this software without specific prior written permission. 15*34885Sbostic * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 16*34885Sbostic * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 17*34885Sbostic * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. 1821971Sdist */ 198805Smckusick 2021971Sdist #ifndef lint 21*34885Sbostic static char sccsid[] = "@(#)parse.c 5.6 (Berkeley) 06/29/88"; 2233767Sbostic #endif /* not lint */ 2321971Sdist 2433767Sbostic /* 2524456Smckusick * FILE NAME: 2624456Smckusick * parse.c 2724456Smckusick * 2824456Smckusick * PURPOSE: 2924456Smckusick * Contains the routines which keep track of the parse stack. 3024456Smckusick * 3124456Smckusick * GLOBALS: 3224456Smckusick * ps.p_stack = The parse stack, set by both routines 3324456Smckusick * ps.il = Stack of indentation levels, set by parse 3424456Smckusick * ps.cstk = Stack of case statement indentation levels, set by parse 3524456Smckusick * ps.tos = Pointer to top of stack, set by both routines. 3624456Smckusick * 3724456Smckusick * FUNCTIONS: 3824456Smckusick * parse 3924456Smckusick * reduce 4024456Smckusick */ 4124456Smckusick /*- 4224456Smckusick * Copyright (C) 1976 by the Board of Trustees of the University of Illinois 4324456Smckusick * 4424456Smckusick * All rights reserved 4524456Smckusick * 4624456Smckusick * 4724456Smckusick * NAME: parse 4824456Smckusick * 4924456Smckusick * FUNCTION: Parse is given one input which is a "maxi token" just scanned 5024456Smckusick * from input. Maxi tokens are signifigant constructs such as else, {, 5124456Smckusick * do, if (...), etc. Parse works with reduce to maintain a parse stack 5224456Smckusick * of these constructs. Parse is responsible for the "shift" portion of 5324456Smckusick * the parse algorithm, and reduce handles the "reduce" portion. 5424456Smckusick * 5524456Smckusick * HISTORY: initial coding November 1976 D A Willcox of CAC 5624456Smckusick * 5724456Smckusick */ 588805Smckusick 5933231Sbostic #include "./indent_globs.h" 6033231Sbostic #include "./indent_codes.h" 618805Smckusick 628805Smckusick 638805Smckusick 648805Smckusick 6524456Smckusick parse(tk) 6624456Smckusick int tk; /* the code for the construct scanned */ 678805Smckusick { 6824456Smckusick int i; 698805Smckusick 708805Smckusick #ifdef debug 7124456Smckusick printf("%2d - %s\n", tk, token); 728805Smckusick #endif 7324456Smckusick while (ps.p_stack[ps.tos] == ifhead && tk != elselit) { 7424456Smckusick /* true if we have an if without an else */ 7524456Smckusick ps.p_stack[ps.tos] = stmt; /* apply the if(..) stmt ::= stmt 7624456Smckusick * reduction */ 7724456Smckusick reduce(); /* see if this allows any reduction */ 788805Smckusick } 798805Smckusick 808805Smckusick 8124456Smckusick switch (tk) { /* go on and figure out what to do with 8224456Smckusick * the input */ 838805Smckusick 8424456Smckusick case decl: /* scanned a declaration word */ 8524456Smckusick ps.search_brace = btype_2; 8624456Smckusick /* indicate that following brace should be on same line */ 8724456Smckusick if (ps.p_stack[ps.tos] != decl) { /* only put one declaration onto 8824456Smckusick * stack */ 8924456Smckusick break_comma = true; /* while in declaration, newline 9024456Smckusick * should be forced after comma */ 9124456Smckusick ps.p_stack[++ps.tos] = decl; 9224456Smckusick ps.il[ps.tos] = ps.i_l_follow; 938805Smckusick 9424456Smckusick if (ps.ljust_decl) { /* only do if we want left 9524456Smckusick * justified declarations */ 9624456Smckusick ps.ind_level = 0; 9724456Smckusick for (i = ps.tos - 1; i > 0; --i) 9824456Smckusick if (ps.p_stack[i] == decl) 9924456Smckusick ++ps.ind_level; /* indentation is number 10024456Smckusick * of declaration levels 10124456Smckusick * deep we are */ 10224456Smckusick ps.i_l_follow = ps.ind_level; 1038805Smckusick } 1048805Smckusick } 1058805Smckusick break; 1068805Smckusick 10724456Smckusick case ifstmt: /* scanned if (...) */ 10824456Smckusick if (ps.p_stack[ps.tos] == elsehead && ps.else_if) /* "else if ..." */ 10924456Smckusick ps.i_l_follow = ps.il[ps.tos]; 11024456Smckusick case dolit: /* 'do' */ 11124456Smckusick case forstmt: /* for (...) */ 11224456Smckusick ps.p_stack[++ps.tos] = tk; 11324456Smckusick ps.il[ps.tos] = ps.ind_level = ps.i_l_follow; 11424456Smckusick ++ps.i_l_follow; /* subsequent statements should be 11524456Smckusick * indented 1 */ 11624456Smckusick ps.search_brace = btype_2; 1178805Smckusick break; 1188805Smckusick 11924456Smckusick case lbrace: /* scanned { */ 12024456Smckusick break_comma = false;/* don't break comma in an initial list */ 12124456Smckusick if (ps.p_stack[ps.tos] == stmt || ps.p_stack[ps.tos] == decl 12224456Smckusick || ps.p_stack[ps.tos] == stmtl) 12324456Smckusick ++ps.i_l_follow; /* it is a random, isolated stmt group or 12424456Smckusick * a declaration */ 1258805Smckusick else { 1268805Smckusick if (s_code == e_code) { 12724456Smckusick /* only do this if there is nothing on the line */ 12824456Smckusick --ps.ind_level; 12924456Smckusick /* it is a group as part of a while, for, etc. */ 13024456Smckusick if (ps.p_stack[ps.tos] == swstmt && ps.case_indent) 13124456Smckusick --ps.ind_level; 13224456Smckusick /* 13324456Smckusick * for a switch, brace should be two levels out from 13424456Smckusick * the code 13524456Smckusick */ 1368805Smckusick } 1378805Smckusick } 1388805Smckusick 13924456Smckusick ps.p_stack[++ps.tos] = lbrace; 14024456Smckusick ps.il[ps.tos] = ps.ind_level; 14124456Smckusick ps.p_stack[++ps.tos] = stmt; 14224456Smckusick /* allow null stmt between braces */ 14324456Smckusick ps.il[ps.tos] = ps.i_l_follow; 1448805Smckusick break; 1458805Smckusick 14624456Smckusick case whilestmt: /* scanned while (...) */ 14724456Smckusick if (ps.p_stack[ps.tos] == dohead) { 14824456Smckusick /* it is matched with do stmt */ 14924456Smckusick ps.ind_level = ps.i_l_follow = ps.il[ps.tos]; 15024456Smckusick ps.p_stack[++ps.tos] = whilestmt; 15124456Smckusick ps.il[ps.tos] = ps.ind_level = ps.i_l_follow; 1528805Smckusick } 15324456Smckusick else { /* it is a while loop */ 15424456Smckusick ps.p_stack[++ps.tos] = whilestmt; 15524456Smckusick ps.il[ps.tos] = ps.i_l_follow; 15624456Smckusick ++ps.i_l_follow; 15724456Smckusick ps.search_brace = btype_2; 1588805Smckusick } 1598805Smckusick 1608805Smckusick break; 1618805Smckusick 16224456Smckusick case elselit: /* scanned an else */ 1638805Smckusick 16424456Smckusick if (ps.p_stack[ps.tos] != ifhead) 16524456Smckusick diag(1,"Unmatched 'else'"); 1668805Smckusick else { 16724456Smckusick ps.ind_level = ps.il[ps.tos]; /* indentation for else should be same as for if */ 16824456Smckusick ps.i_l_follow = ps.ind_level + 1; /* everything following should be in 1 level */ 16924456Smckusick ps.p_stack[ps.tos] = elsehead; 17024456Smckusick /* remember if with else */ 17124456Smckusick ps.search_brace = btype_2; 1728805Smckusick } 1738805Smckusick 1748805Smckusick break; 1758805Smckusick 17624456Smckusick case rbrace: /* scanned a } */ 17724456Smckusick /* stack should have <lbrace> <stmt> or <lbrace> <stmtl> */ 17824456Smckusick if (ps.p_stack[ps.tos - 1] == lbrace) { 17924456Smckusick ps.ind_level = ps.i_l_follow = ps.il[--ps.tos]; 18024456Smckusick ps.p_stack[ps.tos] = stmt; 1818805Smckusick } 18224456Smckusick else 18324456Smckusick diag(1,"Stmt nesting error."); 1848805Smckusick break; 1858805Smckusick 18624456Smckusick case swstmt: /* had switch (...) */ 18724456Smckusick ps.p_stack[++ps.tos] = swstmt; 18824456Smckusick ps.cstk[ps.tos] = case_ind; 18924456Smckusick /* save current case indent level */ 19024456Smckusick ps.il[ps.tos] = ps.i_l_follow; 19124456Smckusick case_ind = ps.i_l_follow + ps.case_indent; /* cases should be one 19224456Smckusick * level down from 19324456Smckusick * switch */ 19433231Sbostic ps.i_l_follow += ps.case_indent + 1; /* statements should be 19524456Smckusick * two levels in */ 19624456Smckusick ps.search_brace = btype_2; 1978805Smckusick break; 1988805Smckusick 19924456Smckusick case semicolon: /* this indicates a simple stmt */ 20024456Smckusick break_comma = false;/* turn off flag to break after commas in 20124456Smckusick * a declaration */ 20224456Smckusick ps.p_stack[++ps.tos] = stmt; 20324456Smckusick ps.il[ps.tos] = ps.ind_level; 2048805Smckusick break; 2058805Smckusick 20624456Smckusick default: /* this is an error */ 20724456Smckusick diag(1,"Unknown code to parser"); 2088805Smckusick return; 2098805Smckusick 2108805Smckusick 21124456Smckusick } /* end of switch */ 2128805Smckusick 21324456Smckusick reduce(); /* see if any reduction can be done */ 2148805Smckusick #ifdef debug 21524456Smckusick for (i = 1; i <= ps.tos; ++i) 21624456Smckusick printf("(%d %d)", ps.p_stack[i], ps.il[i]); 21724456Smckusick printf("\n"); 2188805Smckusick #endif 2198805Smckusick return; 2208805Smckusick } 22124456Smckusick /* 22224456Smckusick * Copyright (C) 1976 by the Board of Trustees of the University of Illinois 22324456Smckusick * 22424456Smckusick * All rights reserved 22524456Smckusick * 22624456Smckusick * 22724456Smckusick * NAME: reduce 22824456Smckusick * 22924456Smckusick * FUNCTION: Implements the reduce part of the parsing algorithm 23024456Smckusick * 23124456Smckusick * ALGORITHM: The following reductions are done. Reductions are repeated 23224456Smckusick * until no more are possible. 23324456Smckusick * 23424456Smckusick * Old TOS New TOS <stmt> <stmt> <stmtl> <stmtl> <stmt> <stmtl> do 23524456Smckusick * <stmt> "dostmt" if <stmt> "ifstmt" switch <stmt> <stmt> 23624456Smckusick * decl <stmt> <stmt> "ifelse" <stmt> <stmt> for <stmt> <stmt> 23724456Smckusick * while <stmt> <stmt> "dostmt" while <stmt> 23824456Smckusick * 23924456Smckusick * On each reduction, ps.i_l_follow (the indentation for the following line) is 24024456Smckusick * set to the indentation level associated with the old TOS. 24124456Smckusick * 24224456Smckusick * PARAMETERS: None 24324456Smckusick * 24424456Smckusick * RETURNS: Nothing 24524456Smckusick * 24624456Smckusick * GLOBALS: ps.cstk ps.i_l_follow = ps.il ps.p_stack = ps.tos = 24724456Smckusick * 24824456Smckusick * CALLS: None 24924456Smckusick * 25024456Smckusick * CALLED BY: parse 25124456Smckusick * 25224456Smckusick * HISTORY: initial coding November 1976 D A Willcox of CAC 25324456Smckusick * 25424456Smckusick */ 2558805Smckusick /*----------------------------------------------*\ 25624456Smckusick * | REDUCTION PHASE 2578805Smckusick \*----------------------------------------------*/ 25824456Smckusick reduce() { 2598805Smckusick 26024456Smckusick register int i; 2618805Smckusick 26224456Smckusick for (;;) { /* keep looping until there is nothing 26324456Smckusick * left to reduce */ 2648805Smckusick 26524456Smckusick switch (ps.p_stack[ps.tos]) { 2668805Smckusick 2678805Smckusick case stmt: 26824456Smckusick switch (ps.p_stack[ps.tos - 1]) { 2698805Smckusick 2708805Smckusick case stmt: 2718805Smckusick case stmtl: 27224456Smckusick /* stmtl stmt or stmt stmt */ 27324456Smckusick ps.p_stack[--ps.tos] = stmtl; 2748805Smckusick break; 2758805Smckusick 27624456Smckusick case dolit: /* <do> <stmt> */ 27724456Smckusick ps.p_stack[--ps.tos] = dohead; 27824456Smckusick ps.i_l_follow = ps.il[ps.tos]; 2798805Smckusick break; 2808805Smckusick 2818805Smckusick case ifstmt: 28224456Smckusick /* <if> <stmt> */ 28324456Smckusick ps.p_stack[--ps.tos] = ifhead; 28424456Smckusick for (i = ps.tos - 1; 2858805Smckusick ( 28624456Smckusick ps.p_stack[i] != stmt 2878805Smckusick && 28824456Smckusick ps.p_stack[i] != stmtl 2898805Smckusick && 29024456Smckusick ps.p_stack[i] != lbrace 2918805Smckusick ); 2928805Smckusick --i); 29324456Smckusick ps.i_l_follow = ps.il[i]; 29424456Smckusick /* 29524456Smckusick * for the time being, we will assume that there 29624456Smckusick * is no else on this if, and set the indentation 29724456Smckusick * level accordingly. If an else is scanned, it 29824456Smckusick * will be fixed up later 29924456Smckusick */ 3008805Smckusick break; 3018805Smckusick 3028805Smckusick case swstmt: 30324456Smckusick /* <switch> <stmt> */ 30424456Smckusick case_ind = ps.cstk[ps.tos - 1]; 3058805Smckusick 30624456Smckusick case decl: /* finish of a declaration */ 3078805Smckusick case elsehead: 30824456Smckusick /* <<if> <stmt> else> <stmt> */ 3098805Smckusick case forstmt: 31024456Smckusick /* <for> <stmt> */ 3118805Smckusick case whilestmt: 31224456Smckusick /* <while> <stmt> */ 31324456Smckusick ps.p_stack[--ps.tos] = stmt; 31424456Smckusick ps.i_l_follow = ps.il[ps.tos]; 3158805Smckusick break; 3168805Smckusick 31724456Smckusick default: /* <anything else> <stmt> */ 3188805Smckusick return; 3198805Smckusick 32024456Smckusick } /* end of section for <stmt> on top of 32124456Smckusick * stack */ 3228805Smckusick break; 3238805Smckusick 32424456Smckusick case whilestmt: /* while (...) on top */ 32524456Smckusick if (ps.p_stack[ps.tos - 1] == dohead) { 32624456Smckusick /* it is termination of a do while */ 32724456Smckusick ps.p_stack[--ps.tos] = stmt; 3288805Smckusick break; 3298805Smckusick } 3308805Smckusick else 3318805Smckusick return; 3328805Smckusick 33324456Smckusick default: /* anything else on top */ 3348805Smckusick return; 3358805Smckusick 33624456Smckusick } 33724456Smckusick } 3388805Smckusick } 339