From: "Campbell, Rolf [SKY:1U32:EXCH]" Newsgroups: comp.os.msdos.djgpp Subject: Re: Bison and particular expressions. Date: Thu, 24 Jun 1999 11:57:12 -0400 Organization: Nortel Networks Lines: 1163 Message-ID: <37725553.F53197D6@americasm01.nt.com> References: <37711A9A DOT 4D73B486 AT americasm01 DOT nt DOT com> <7kt4t8$3bq$1 AT nnrp1 DOT deja DOT com> NNTP-Posting-Host: bmerhc00.ca.nortel.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 4.6 [en] (X11; I; HP-UX B.10.20 9000/712) X-Accept-Language: en To: djgpp AT delorie DOT com DJ-Gateway: from newsgroup comp.os.msdos.djgpp Reply-To: djgpp AT delorie DOT com deleveld AT my-deja DOT com wrote: > Hi Rolf, > > I've had some similar problems as what you have described and > I found that there was always a problem with the grammer, even > if I initially didn't think there was a problem. > > What I found very helpful is to run Bison with the -v option > and look at the parser states written in the .out file, and look > for shift/reduce and reduce/reduce conflicts which (i think) > is the basis of your problems. > > If you can't figure out how to read the .out file, post it or > send it to me and and I'll have a shot... > Doug Eleveld Rule #11 & #34 seem to be the one's that cause my problem. Sorry for the huge post, but it's a complex program. What I would like to happen is that it would wait until after parsing the first "parm" and the "," before choosing which rule to apply. Is that possible, or is there some other way to do this? Terminals which are not used: EQUAL AND OR XOR NOTEQUAL SHIFTLEFT SHIFTRIGHT VAR_ARGS CHAR_LITERAL ARROW GTHAN LTHAN State 29 contains 1 shift/reduce conflict. State 44 contains 1 shift/reduce conflict. State 57 contains 1 shift/reduce conflict. State 60 contains 1 shift/reduce conflict. Grammar rule 1 file -> /* empty */ rule 2 file -> file declaration rule 3 file -> file extern rule 4 extern -> EXTERN STRING '{' declarations '}' rule 5 extern -> EXTERN '{' declarations '}' rule 6 extern -> EXTERN declaration rule 7 declarations -> declaration rule 8 declarations -> declarations declaration rule 9 declarations -> declarations extern rule 10 declaration -> parm ';' rule 11 declaration -> parm ',' ref id ext ';' rule 12 declaration -> function ';' rule 13 declaration -> TYPEDEF parm ';' rule 14 function -> parm parmList rule 15 parmList -> '(' ')' rule 16 parmList -> partialparmList ')' rule 17 parmList -> partialparmList ',' ELISPCE ')' rule 18 partialparmList -> '(' parm rule 19 partialparmList -> partialparmList ',' parm rule 20 parm -> btype ref id ext rule 21 id -> ID rule 22 id -> '(' '*' id '(' parmList ')' ')' rule 23 ext -> /* empty */ rule 24 ext -> extIndex '=' ID rule 25 extIndex -> /* empty */ rule 26 extIndex -> extIndex '[' ']' rule 27 extIndex -> extIndex '[' ID ']' rule 28 ref -> /* empty */ rule 29 ref -> ref '*' rule 30 ref -> ref '&' rule 31 btype -> builtIn rule 32 btype -> struct rule 33 btype -> ID rule 34 btype -> parm ',' parm ',' rule 35 struct -> STRUCT '{' declarations '}' rule 36 builtIn -> typeKeyword rule 37 builtIn -> typeKeyword builtIn rule 38 typeKeyword -> INT rule 39 typeKeyword -> SHORT rule 40 typeKeyword -> LONG rule 41 typeKeyword -> CHAR rule 42 typeKeyword -> VOID rule 43 typeKeyword -> UNSIGNED rule 44 typeKeyword -> SIGNED rule 45 typeKeyword -> CONST Terminals, with rules where they appear $ (-1) '&' (38) 30 '(' (40) 15 18 22 ')' (41) 15 16 17 22 '*' (42) 22 29 ',' (44) 11 17 19 34 ';' (59) 10 11 12 13 '=' (61) 24 '[' (91) 26 27 ']' (93) 26 27 '{' (123) 4 5 35 '}' (125) 4 5 35 error (256) ID (258) 21 24 27 33 EQUAL (259) AND (260) OR (261) XOR (262) NOTEQUAL (263) SHIFTLEFT (264) SHIFTRIGHT (265) VAR_ARGS (266) STRING (267) 4 CHAR_LITERAL (268) ELISPCE (269) 17 ARROW (270) GTHAN (271) LTHAN (272) CONST (273) 45 CHAR (274) 41 UNSIGNED (275) 43 SIGNED (276) 44 INT (277) 38 SHORT (278) 39 LONG (279) 40 VOID (280) 42 TYPEDEF (281) 13 STRUCT (282) 35 EXTERN (283) 4 5 6 Nonterminals, with rules where they appear file (40) on left: 1 2 3, on right: 2 3 extern (41) on left: 4 5 6, on right: 3 9 declarations (42) on left: 7 8 9, on right: 4 5 8 9 35 declaration (43) on left: 10 11 12 13, on right: 2 6 7 8 function (44) on left: 14, on right: 12 parmList (45) on left: 15 16 17, on right: 14 22 partialparmList (46) on left: 18 19, on right: 16 17 19 parm (47) on left: 20, on right: 10 11 13 14 18 19 34 id (48) on left: 21 22, on right: 11 20 22 ext (49) on left: 23 24, on right: 11 20 extIndex (50) on left: 25 26 27, on right: 24 26 27 ref (51) on left: 28 29 30, on right: 11 20 29 30 btype (52) on left: 31 32 33 34, on right: 20 struct (53) on left: 35, on right: 32 builtIn (54) on left: 36 37, on right: 31 37 typeKeyword (55) on left: 38 39 40 41 42 43 44 45, on right: 36 37 state 0 $default reduce using rule 1 (file) file go to state 1 state 1 file -> file . declaration (rule 2) file -> file . extern (rule 3) $ go to state 79 ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 TYPEDEF shift, and go to state 11 STRUCT shift, and go to state 12 EXTERN shift, and go to state 13 extern go to state 14 declaration go to state 15 function go to state 16 parm go to state 17 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 2 btype -> ID . (rule 33) $default reduce using rule 33 (btype) state 3 typeKeyword -> CONST . (rule 45) $default reduce using rule 45 (typeKeyword) state 4 typeKeyword -> CHAR . (rule 41) $default reduce using rule 41 (typeKeyword) state 5 typeKeyword -> UNSIGNED . (rule 43) $default reduce using rule 43 (typeKeyword) state 6 typeKeyword -> SIGNED . (rule 44) $default reduce using rule 44 (typeKeyword) state 7 typeKeyword -> INT . (rule 38) $default reduce using rule 38 (typeKeyword) state 8 typeKeyword -> SHORT . (rule 39) $default reduce using rule 39 (typeKeyword) state 9 typeKeyword -> LONG . (rule 40) $default reduce using rule 40 (typeKeyword) state 10 typeKeyword -> VOID . (rule 42) $default reduce using rule 42 (typeKeyword) state 11 declaration -> TYPEDEF . parm ';' (rule 13) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 STRUCT shift, and go to state 12 parm go to state 22 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 12 struct -> STRUCT . '{' declarations '}' (rule 35) '{' shift, and go to state 23 state 13 extern -> EXTERN . STRING '{' declarations '}' (rule 4) extern -> EXTERN . '{' declarations '}' (rule 5) extern -> EXTERN . declaration (rule 6) ID shift, and go to state 2 STRING shift, and go to state 24 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 TYPEDEF shift, and go to state 11 STRUCT shift, and go to state 12 '{' shift, and go to state 25 declaration go to state 26 function go to state 16 parm go to state 17 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 14 file -> file extern . (rule 3) $default reduce using rule 3 (file) state 15 file -> file declaration . (rule 2) $default reduce using rule 2 (file) state 16 declaration -> function . ';' (rule 12) ';' shift, and go to state 27 state 17 declaration -> parm . ';' (rule 10) declaration -> parm . ',' ref id ext ';' (rule 11) function -> parm . parmList (rule 14) btype -> parm . ',' parm ',' (rule 34) ';' shift, and go to state 28 ',' shift, and go to state 29 '(' shift, and go to state 30 parmList go to state 31 partialparmList go to state 32 state 18 parm -> btype . ref id ext (rule 20) $default reduce using rule 28 (ref) ref go to state 33 state 19 btype -> struct . (rule 32) $default reduce using rule 32 (btype) state 20 btype -> builtIn . (rule 31) $default reduce using rule 31 (btype) state 21 builtIn -> typeKeyword . (rule 36) builtIn -> typeKeyword . builtIn (rule 37) CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 $default reduce using rule 36 (builtIn) builtIn go to state 34 typeKeyword go to state 21 state 22 declaration -> TYPEDEF parm . ';' (rule 13) btype -> parm . ',' parm ',' (rule 34) ';' shift, and go to state 35 ',' shift, and go to state 36 state 23 struct -> STRUCT '{' . declarations '}' (rule 35) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 TYPEDEF shift, and go to state 11 STRUCT shift, and go to state 12 declarations go to state 37 declaration go to state 38 function go to state 16 parm go to state 17 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 24 extern -> EXTERN STRING . '{' declarations '}' (rule 4) '{' shift, and go to state 39 state 25 extern -> EXTERN '{' . declarations '}' (rule 5) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 TYPEDEF shift, and go to state 11 STRUCT shift, and go to state 12 declarations go to state 40 declaration go to state 38 function go to state 16 parm go to state 17 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 26 extern -> EXTERN declaration . (rule 6) $default reduce using rule 6 (extern) state 27 declaration -> function ';' . (rule 12) $default reduce using rule 12 (declaration) state 28 declaration -> parm ';' . (rule 10) $default reduce using rule 10 (declaration) state 29 declaration -> parm ',' . ref id ext ';' (rule 11) btype -> parm ',' . parm ',' (rule 34) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 STRUCT shift, and go to state 12 ID [reduce using rule 28 (ref)] $default reduce using rule 28 (ref) parm go to state 41 ref go to state 42 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 30 parmList -> '(' . ')' (rule 15) partialparmList -> '(' . parm (rule 18) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 STRUCT shift, and go to state 12 ')' shift, and go to state 43 parm go to state 44 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 31 function -> parm parmList . (rule 14) $default reduce using rule 14 (function) state 32 parmList -> partialparmList . ')' (rule 16) parmList -> partialparmList . ',' ELISPCE ')' (rule 17) partialparmList -> partialparmList . ',' parm (rule 19) ',' shift, and go to state 45 ')' shift, and go to state 46 state 33 parm -> btype ref . id ext (rule 20) ref -> ref . '*' (rule 29) ref -> ref . '&' (rule 30) ID shift, and go to state 47 '(' shift, and go to state 48 '*' shift, and go to state 49 '&' shift, and go to state 50 id go to state 51 state 34 builtIn -> typeKeyword builtIn . (rule 37) $default reduce using rule 37 (builtIn) state 35 declaration -> TYPEDEF parm ';' . (rule 13) $default reduce using rule 13 (declaration) state 36 btype -> parm ',' . parm ',' (rule 34) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 STRUCT shift, and go to state 12 parm go to state 41 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 37 declarations -> declarations . declaration (rule 8) declarations -> declarations . extern (rule 9) struct -> STRUCT '{' declarations . '}' (rule 35) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 TYPEDEF shift, and go to state 11 STRUCT shift, and go to state 12 EXTERN shift, and go to state 13 '}' shift, and go to state 52 extern go to state 53 declaration go to state 54 function go to state 16 parm go to state 17 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 38 declarations -> declaration . (rule 7) $default reduce using rule 7 (declarations) state 39 extern -> EXTERN STRING '{' . declarations '}' (rule 4) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 TYPEDEF shift, and go to state 11 STRUCT shift, and go to state 12 declarations go to state 55 declaration go to state 38 function go to state 16 parm go to state 17 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 40 extern -> EXTERN '{' declarations . '}' (rule 5) declarations -> declarations . declaration (rule 8) declarations -> declarations . extern (rule 9) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 TYPEDEF shift, and go to state 11 STRUCT shift, and go to state 12 EXTERN shift, and go to state 13 '}' shift, and go to state 56 extern go to state 53 declaration go to state 54 function go to state 16 parm go to state 17 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 41 btype -> parm . ',' parm ',' (rule 34) btype -> parm ',' parm . ',' (rule 34) ',' shift, and go to state 57 state 42 declaration -> parm ',' ref . id ext ';' (rule 11) ref -> ref . '*' (rule 29) ref -> ref . '&' (rule 30) ID shift, and go to state 47 '(' shift, and go to state 48 '*' shift, and go to state 49 '&' shift, and go to state 50 id go to state 58 state 43 parmList -> '(' ')' . (rule 15) $default reduce using rule 15 (parmList) state 44 partialparmList -> '(' parm . (rule 18) btype -> parm . ',' parm ',' (rule 34) ',' shift, and go to state 36 ',' [reduce using rule 18 (partialparmList)] $default reduce using rule 18 (partialparmList) state 45 parmList -> partialparmList ',' . ELISPCE ')' (rule 17) partialparmList -> partialparmList ',' . parm (rule 19) ID shift, and go to state 2 ELISPCE shift, and go to state 59 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 STRUCT shift, and go to state 12 parm go to state 60 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 46 parmList -> partialparmList ')' . (rule 16) $default reduce using rule 16 (parmList) state 47 id -> ID . (rule 21) $default reduce using rule 21 (id) state 48 id -> '(' . '*' id '(' parmList ')' ')' (rule 22) '*' shift, and go to state 61 state 49 ref -> ref '*' . (rule 29) $default reduce using rule 29 (ref) state 50 ref -> ref '&' . (rule 30) $default reduce using rule 30 (ref) state 51 parm -> btype ref id . ext (rule 20) '=' reduce using rule 25 (extIndex) '[' reduce using rule 25 (extIndex) $default reduce using rule 23 (ext) ext go to state 62 extIndex go to state 63 state 52 struct -> STRUCT '{' declarations '}' . (rule 35) $default reduce using rule 35 (struct) state 53 declarations -> declarations extern . (rule 9) $default reduce using rule 9 (declarations) state 54 declarations -> declarations declaration . (rule 8) $default reduce using rule 8 (declarations) state 55 extern -> EXTERN STRING '{' declarations . '}' (rule 4) declarations -> declarations . declaration (rule 8) declarations -> declarations . extern (rule 9) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 TYPEDEF shift, and go to state 11 STRUCT shift, and go to state 12 EXTERN shift, and go to state 13 '}' shift, and go to state 64 extern go to state 53 declaration go to state 54 function go to state 16 parm go to state 17 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 56 extern -> EXTERN '{' declarations '}' . (rule 5) $default reduce using rule 5 (extern) state 57 btype -> parm ',' . parm ',' (rule 34) btype -> parm ',' parm ',' . (rule 34) ID shift, and go to state 2 CONST shift, and go to state 3 CHAR shift, and go to state 4 UNSIGNED shift, and go to state 5 SIGNED shift, and go to state 6 INT shift, and go to state 7 SHORT shift, and go to state 8 LONG shift, and go to state 9 VOID shift, and go to state 10 STRUCT shift, and go to state 12 ID [reduce using rule 34 (btype)] $default reduce using rule 34 (btype) parm go to state 41 btype go to state 18 struct go to state 19 builtIn go to state 20 typeKeyword go to state 21 state 58 declaration -> parm ',' ref id . ext ';' (rule 11) ';' reduce using rule 23 (ext) $default reduce using rule 25 (extIndex) ext go to state 65 extIndex go to state 63 state 59 parmList -> partialparmList ',' ELISPCE . ')' (rule 17) ')' shift, and go to state 66 state 60 partialparmList -> partialparmList ',' parm . (rule 19) btype -> parm . ',' parm ',' (rule 34) ',' shift, and go to state 36 ',' [reduce using rule 19 (partialparmList)] $default reduce using rule 19 (partialparmList) state 61 id -> '(' '*' . id '(' parmList ')' ')' (rule 22) ID shift, and go to state 47 '(' shift, and go to state 48 id go to state 67 state 62 parm -> btype ref id ext . (rule 20) $default reduce using rule 20 (parm) state 63 ext -> extIndex . '=' ID (rule 24) extIndex -> extIndex . '[' ']' (rule 26) extIndex -> extIndex . '[' ID ']' (rule 27) '=' shift, and go to state 68 '[' shift, and go to state 69 state 64 extern -> EXTERN STRING '{' declarations '}' . (rule 4) $default reduce using rule 4 (extern) state 65 declaration -> parm ',' ref id ext . ';' (rule 11) ';' shift, and go to state 70 state 66 parmList -> partialparmList ',' ELISPCE ')' . (rule 17) $default reduce using rule 17 (parmList) state 67 id -> '(' '*' id . '(' parmList ')' ')' (rule 22) '(' shift, and go to state 71 state 68 ext -> extIndex '=' . ID (rule 24) ID shift, and go to state 72 state 69 extIndex -> extIndex '[' . ']' (rule 26) extIndex -> extIndex '[' . ID ']' (rule 27) ID shift, and go to state 73 ']' shift, and go to state 74 state 70 declaration -> parm ',' ref id ext ';' . (rule 11) $default reduce using rule 11 (declaration) state 71 id -> '(' '*' id '(' . parmList ')' ')' (rule 22) '(' shift, and go to state 30 parmList go to state 75 partialparmList go to state 32 state 72 ext -> extIndex '=' ID . (rule 24) $default reduce using rule 24 (ext) state 73 extIndex -> extIndex '[' ID . ']' (rule 27) ']' shift, and go to state 76 state 74 extIndex -> extIndex '[' ']' . (rule 26) $default reduce using rule 26 (extIndex) state 75 id -> '(' '*' id '(' parmList . ')' ')' (rule 22) ')' shift, and go to state 77 state 76 extIndex -> extIndex '[' ID ']' . (rule 27) $default reduce using rule 27 (extIndex) state 77 id -> '(' '*' id '(' parmList ')' . ')' (rule 22) ')' shift, and go to state 78 state 78 id -> '(' '*' id '(' parmList ')' ')' . (rule 22) $default reduce using rule 22 (id) state 79 $ go to state 80 state 80 $default accept -- -Rolf Campbell (39)3-6318