RE: Re: bison info doc - precedence in recursive parsing

[anand]

Hello Akim,
    consider simple example below
 
     expr :   a
              |  expr + b  {
                 $$ = $1 + $2;
                           }
              | expr * b {
                 $$ = $1 * $2;
                           };
 
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.
 
Regards,
Anand
 
 
 
--------- Original Message --------- Subject: Re: bison info doc - precedence 
in recursive parsing
From: "Akim Demaille" <address@hidden>
Date: 2/3/19 11:32 pm
To: address@hidden
Cc: "Bison Help" <address@hidden>

Hi Anand,
 
 > Le 3 f&eacute;vr. 2019 &agrave; 07:50, <address@hidden> <address@hidden> a 
 > &eacute;crit :
 > 
 > Hello,
 > in info doc of bison, it is mentioned that rule gets its precendence from 
 > last terminal symbol.
 > pasted below:
 > The first effect of the precedence declarations is to assign precedence 
 > levels to the terminal symbols declared. The second effect is to assign 
 > precedence levels to certain rules: each rule gets its precedence from the 
 > last terminal symbol mentioned in the components. 
 > 
 > For below example, how the parsing will happen if above is the case:
 > 
 > nonterm1 : nonterm2
 > | nonterm1 term1 nonterm3 nonterm4
 > | nonterm1 term2 nonterm5 nonterm6
 > 
 > One more example:
 > nonterm1 : nonterm2 nonterm3
 > | nonterm1 term1 nonterm2 nonterm3
 > | nonterm1 term2 nonterm2 nonterm3
 > 
 > Consider first example. First parser will consume nonterm2 then for term1 
 > rule, nonterm1 will hold nonterm2 value and term2 higher precedence than 
 > term1, parser have to pass value to nonterm1 in term2 rule but it is invalid 
 > if we provide term1 precedence to term1 rule because as the statement 
 > suggests, last terminal token gives rule precedence. Assigning value of 
 > "nonterm3 nonterm4" to nonterm1 in term2 rule is not possible or is it?
 > Value is for term or nonterm but not partial set of symbols in rule. is it 
 > right?
 > Does the info doc says last terminal symbol as last but one symbol which if 
 > it is terminal?
 
 Your question is a bit confusing, I'm not sure I really understand what you 
mean. However, note that precedence is *only* about solving shift/reduce 
conflicts. In your grammar, it is unlikely that you would get a shift/reduce 
conflict. Rather, the parser will try to follow both "nonterm1 : nonterm1 term1 
nonterm3 nonterm4" and "nonterm1 : nonterm1 term2 nonterm5 nonterm6" in 
parallel, and it will easily see which one to chose when it sees term1 or term2 
arriving. So it does not care what precedence you gave to who.
 
 Make a full example, feed it to bison with --graph, and look at the resulting 
graph. You should understand what is going on (provided you understand how LR 
parsers work).
 
 Cheers.