Bison reduce/reduce, shift/reduce conflicts -

Bison reduce/reduce, shift/reduce conflicts -

hey guys i'm having problem bison code... after compiling chunk of code, 58 shift/reduce , 40 reduce/reduce conflicts... tips on how constrain them, or point me guide on how it? in advance!! (everything starts t_, t_get tokens defined above code)

start:t_get g |t_head g |t_post g ; g:url canon ; url: t_http t_dslash t_host t_abs_path ; canon:gh canon|rh canon|eh canon|mb ; gh:t_con t_akt t_seq gh|t_date t_akt d gh|t_trans t gh| ; d:t_day t_slash t_month t_slash t_year t_hour t_akt t_min ; t:t_chunked |t_gzip |t_deflate ; rh:t_acc t_akt t_seq rh|t_ref t_akt t_seq rh|t_user t_akt t_seq rh| ; eh:t_content t_akt t_seq eh|t_exp t_akt t_seq eh| ; mb:t_seq| ; %% int main(){ yyparse(); }

even if dont have time study logic in code, appreciate general help in these conflicts,like how generated etc

use bison's -v alternative verbose output giving states , conflicts in generated parser. if you'll see state like:

state 7 4 g: url . canon t_acc shift, , go state 12 : t_trans shift, , go state 19 t_user shift, , go state 20 $end cut down using rule 13 (gh) $end [reduce using rule 21 (rh)] $end [reduce using rule 24 (eh)] $end [reduce using rule 26 (mb)] t_acc [reduce using rule 13 (gh)] :

this telling when parser has seen url , looking recognize canon, can't tell -- should recognize empty gh, rh, eh, or mb, or should shift token recognize non-empty 1 of those?

these conflicts come basic ambiguity in grammar -- have canon rule consists of 0 or more repeats of gh, rh, and/or eh, , each of rules consist of 0 or more repeats of something. has no way of telling how many empty things insert parse tree (as consume no input, arbitrary number can added), , has no thought whether grouping similar things single gh (or rh or eh) or multiple distinct ones.

so prepare this, need decide want. probably, don't care grouping of gh/rh/eh structures, nor care empty ones, should rid of recursion rules:

gh:t_con t_akt t_seq|t_date t_akt d|t_trans t; rh:t_acc t_akt t_seq|t_ref t_akt t_seq|t_user t_akt t_seq; eh:t_content t_akt t_seq|t_exp t_akt t_seq;

now each of rules match 1 construct, , if have multiple, they'll grouped canon rule. fixes conflicts have, still leaves potential problem -- canon rule right recursive, suck entire input onto stack before reducing rules (since right-recursion, reduces right-to-left). want create rule left recursive instead -- general rule in bison always utilize left recursion , not right recursion, unless need right recursion reason. gives grammar:

start : t_get g | t_head g | t_post g ; g : url canon mb ; url : t_http t_dslash t_host t_abs_path ; canon : canon gh | canon rh | canon eh | ; gh : t_con t_akt t_seq | t_date t_akt d | t_trans t ; d : t_day t_slash t_month t_slash t_year t_hour t_akt t_min ; t : t_chunked | t_gzip | t_deflate ; rh : t_acc t_akt t_seq | t_ref t_akt t_seq | t_user t_akt t_seq ; eh : t_content t_akt t_seq | t_exp t_akt t_seq ; mb : t_seq | ;

bison