Re: bison info doc - precedence in recursive parsing

[Akim Demaille]

Hi Anand,

Sorry, I missed your message :(

> Le 14 févr. 2019 à 07:05, address@hidden a écrit :
> 
> Hello Akim,
>    consider simple example below
> 
>     expr :   a
>              |  expr + b  {
>                 $$ = $1 + $2;
>                           }
>              | expr * b {
>                 $$ = $1 * $2;
>                           };

This is not valid, + and * must be quoted.

> if input is  2 + 3*5, $$ on * will be 15. This 15 will go to + statement to 
> $2 and $$ in + statement will be 2 + 15.
> Now consider below example
> 
>     expr : b1 b2
>              | expr + b1 b2 {
>                 sprintf($$, "%d%s",  atoi($1) + $2, $3);
>                          }
>              | expr * b1 b2 {
>                 $$ = sprintf($$, "%d%s", atoi($1) * $2, $3);
>                          };
>     b1: numeric
>     b2: alpha
> 
> b1 and b2 are nonterminals and numeric and alpha are terminals.
> if input is 2a + 3a * 5a, then * rule gives output 15a.
> + rule has precedence of + terminal symbol which is last terminal symbol 
> according to info doc.
> In + rule, expr will have 2a but b1 b2 can't get 15a because both are 
> separate symbols.
> This is case if + goes on right associative.
> Differant way is in action of + rule, expr gets 15a and 2a goes to b1 b2 but 
> it is not in order.
> In case + is left associative like *, then expr gets 2a and b1 b2 gets  3a 
> which works.
> However if b1 b2 are replaced by single terminal rule as b : b1 b2
> then + can take right associative and it can be workable.
> This is why I asked if info doc interpretation should be different.

There is no question here: %left and %right are there to solve conflicts, and 
your grammar has no conflicts.  Just run the tool and see what it says:

$ cat /tmp/anand.y
%%
expr : b1 b2
| expr "+" b1 b2
| expr "*" b1 b2
b1: "numeric"
b2: "alpha"
$ bison -Wall /tmp/anand.y
$

Your grammar has no conflict, %left is useless.  And Bison will tell you.

$ cat /tmp/anand.y
%left "+"
%left "*"
%%
expr : b1 b2
| expr "+" b1 b2
| expr "*" b1 b2
b1: "numeric"
b2: "alpha"
$ bison -Wall /tmp/anand.y
/tmp/anand.y:1.1-5: warning: useless precedence and associativity for "+" 
[-Wprecedence]
 %left "+"
 ^~~~~
/tmp/anand.y:2.1-5: warning: useless precedence and associativity for "*" 
[-Wprecedence]
 %left "*"
 ^~~~~
$


If you _want_ to use %left, then make your operator really binary: left _and_ 
right recursive on its LHS.  And check in the output file that it does what you 
meant.

$ cat /tmp/anand.y
%left "+"
%left "*"
%%
expr : b1 b2
| expr "+" expr
| expr "*" expr
b1: "numeric"
b2: "alpha"
$ bison -Wall -rall /tmp/anand.y
$ sed -n '/State 9/,$p' anand.output
State 9

    2 expr: expr . "+" expr
    2     | expr "+" expr .  [$end, "+"]
    3     | expr . "*" expr

    "*"  shift, and go to state 6

    $default  reduce using rule 2 (expr)

    Conflict between rule 2 and token "+" resolved as reduce (%left "+").
    Conflict between rule 2 and token "*" resolved as shift ("+" < "*").


State 10

    2 expr: expr . "+" expr
    3     | expr . "*" expr
    3     | expr "*" expr .  [$end, "+", "*"]

    $default  reduce using rule 3 (expr)

    Conflict between rule 3 and token "+" resolved as reduce ("+" < "*").
    Conflict between rule 3 and token "*" resolved as reduce (%left "*").
$