Using yacc precedence for rules with no terminals, only non-terminals

Question

could some one help me on this i have this rule :

e   : T_NUM                                            { $$ = mk_int($1);}
| T_POP e[l]                                       { $$ = mk_app(mk_op(POP),$l);}
| T_NEXT e[l]                                      { $$ = mk_app(mk_op(NEXT),$l);}
| "{" e[x] "," e[y] "}"                            { $$ = mk_point($x,$y);}
| e T_PLUS e                                       { $$ = mk_app(mk_app(mk_op(PLUS),$1),$3);}
| e T_MINUS e                                      { $$ = mk_app(mk_app(mk_op(MINUS),$1),$3);}
| e T_DIV e                                        { $$ = mk_app(mk_app(mk_op(DIV),$1),$3);}
| e T_MULT e                                       { $$ = mk_app(mk_app(mk_op(MULT),$1),$3);}
| e T_LEQ e                                        { $$ = mk_app(mk_app(mk_op(LEQ),$1),$3) ;}
| e T_LE e                                         { $$ = mk_app(mk_app(mk_op(LE),$1),$3) ;}
| e T_GEQ e                                        { $$ = mk_app(mk_app(mk_op(GEQ),$1),$3) ;}
| e T_GE e                                         { $$ = mk_app(mk_app(mk_op(GE),$1),$3) ;}
| e T_OR e                                         { $$ = mk_app(mk_app(mk_op(OR),$1),$3) ;}
| e T_AND e                                        { $$ = mk_app(mk_app(mk_op(AND),$1),$3) ;}
| T_ID                                             { $$ = mk_id($1);}/*Reconnaissance d'identificateurs et de variables*/
| e T_EQ e                                         { $$ = mk_app(mk_app(mk_op(EQ),$1),$3) ;}
| T_NOT e[expr]                                    { $$ = mk_app(mk_op(NOT),$expr) ;}
| T_FUN T_ID[var] arg_list[expr]                   { $$ = mk_fun($var,$expr);env = push_rec_env($var,$$,env);} /*Définition de fonctions*/
| T_LET T_ID[x] T_EQUAL e[arg] T_IN e[exp]         { $$ = mk_app(mk_fun($x,$exp),$arg); env = push_rec_env($x,$$,env);}/*Fonction IN*/
| e[exp] T_WHERE T_ID[x] T_EQUAL e[arg]            { $$ = mk_app(mk_fun($x,$exp),$arg); env = push_rec_env($x,$$,env);}/*Fonction WHERE*/
| T_IF e[cond] T_THEN e[then_br] T_ELSE e[else_br] { $$ = mk_cond($cond, $then_br, $else_br) ;}
| '[' list[l] ']'                                  { $$ = $l;}/*OP sur Listes*/
| e[exp] T_PUSH e[l]                               { $$ = mk_app(mk_app(mk_op(PUSH),$exp),$l);} 
| '(' f_arg[fun] e[arg] ')'                        { $$ = mk_app($fun,$arg);}/*Exécution de fonctions à plusieurs variables*/
| '(' e ')'                                        { $$ = $2;}/*Ignorer les parentheses inutiles*/
;

my problem is that at '(' f_arg[fun] e[arg] ')' i would like to remove the '()' around the syntax but this generates tons of conflicts so if some one could give me a hand on how could i change this syntax to work without the parentheses for information the f_arg:

f_arg :e                                                            {$$ = $1;}
  |f_arg[fun] e[arg]                                            {$$ = mk_app($fun,$arg);}
  ;

thanks all

the full code can be found at

https://github.com/WillianPaiva/project_AS

and sorry about my English

score 1 · Answer 1 · answered Apr 24 '14 at 16:58

1

Well, I've not tried to compile and test it. But it looks like you are creating a loop with your rules when removing the '(' and the )'. You are saying that e->f_arg and then f_arg->e. Obviously this creates conflicts.

If you replace | '(' f_arg[fun] e[arg] ')' by | e[arg] f_arg[fun] and replace also f_arg :e by f_arg : (an empty rule) . Then, you need to reconfigure all the actions of your grammar, the code in front of every rule.

If my suggestion doesn't work, you have to figure out a way to remove that loop between e and f_arg

answered Apr 24 '14 at 16:58

g_tec

631
4
9

that does not work mostly because the f_arg and e are the same type basically what i'm trying to do is recognize a sequence of n "e". and that loop between e and f_arg was the best way i found for it thanks anyway – willian ver valem Apr 24 '14 at 18:16
If it doesn't work. You should double all the "e" rules with another name. Then put the f_arg rule point to this new rules. It's not pretty, but it's the only way in other to have no conflicts. – g_tec Apr 24 '14 at 21:39

Chris Dodd · Accepted Answer · 2014-04-25T19:10:47.937

The problem is that unadorned function application is ambiguous with respect to all of your binary infix and prefix oparators -- should an input like a b + c be parsed as (a b) + c or a (b + c)? Since there's no token involved in function application, the normal yacc/bison precedence rules won't work for it without extra help.

Assuming you want to give function application the highest precedence (the normal case, I beleive), you can make this work with some extra work.

Add the following precedence rule to the end of your list (highest precedence):

%left FUNCTION_APPLICATION T_NUM T_ID '{' '('

Make your function rule:

| e[fun] e[arg] %prec FUNCTION_APPLICATION { $$ = mk_app($fun,$arg); }

depending on what you have elsewhere in the grammar, you might need to add some more tokens to the precedence rules and/or rearrange things slightly. In particular, every token in FIRST(e) needs a precedence, and if its precedence for function application is different from its precedence for other uses, things won't work (as each token can only have one precedence). As long as function application is higher precedence than everything else, things should be resolvable.

with your solution it did work when running the program the problem i got 63 new shift reduce problems that i will try to solve by myself once the objective of this is to learn but if is not to much to ask i didn't understand the %prec FUNCTION_APPLICATION and what exactly is the FUNCTION_APPLICATION since i have no token with this name — willian ver valem, Apr 25 '14 at 20:26
`FUNCTION_APPLICATION` is a 'fake' (non-existent) token that exists solely for setting the precedence of the function application rule (which does not contain any tokens). `%prec` is a special directive that can be applied to a rule to manually set it's precedence to that of some other token. — Chris Dodd, Apr 25 '14 at 20:31
The shift/reduce conflicts are probabaly from some token in FIRST(e) that needs a precedence.... — Chris Dodd, Apr 25 '14 at 20:32

Using yacc precedence for rules with no terminals, only non-terminals

2 Answers2

Linked