Re: Shouldn't precedence rules fix this shift/reduce error?

Jeffrey Chen (jchen@netcom.com) writes:


>I need to parse simple arithmetic expressions involving numbers
>(VALUE_TOKs), unary minus, and plus. Plus, optionally may have an
>"instance name" appended to the operator:
>...


>My yacc grammar is below, along with PCYACC's yy.lrt output which
>shows a shift/reduce and reduce/reduce conflict in state 6.
>...
>
>%token VALUE_TOK
>%token IDENTIFIER_TOK
>%token ERROR_TOK
>
>%left '+'
>%left UNARY_MINUS
>
>%start expn
>
>%%
>
>instance.opt
> : /* empty */
> | IDENTIFIER_TOK ':'
> ;
>
>expn
> : VALUE_TOK
> | '-' expn %prec UNARY_MINUS /* rule A */
> | expn instance.opt '+' expn /* rule B */
> ;
>...


Conflicts in the above grammar result from two sources:


a. Using a separate non-terminal instance.opt for the optional "instance
name" with an empty production. As long as you are not doing any
non-trivial semantic processing for such a non-terminal, you can get rid of
such conflicts (at the cost of an exponential increase in the size of the
grammar) by substituting all its RHSs for all occurrences of this
non-terminal.


b. Not having a precedence defined for IDENTIFIER_TOK. The way the parser
uses the declared precedences is to use the last terminal symbol on a rule
RHS to associate a precedence with each rule. Then when resolving a
shift-reduce conflict, it compares the precedence of the rule with the
precedence of the lookahead: If the rule precedence is greater it reduces;
if smaller it shifts. If equal, then it reduces if the lookahead is
declared %left, shifts if declared %right. Since IDENTIFIER_TOK does not
have a precedence, the parser can't decide whether to shift or reduce when a
expn is followed by an IDENTIFIER_TOK.


Making the changes suggested above we get the following grammar which is
declared conflict-free by bison.




%token VALUE_TOK
%token IDENTIFIER_TOK
%token ERROR_TOK


%left '+' IDENTIFIER_TOK
%left UNARY_MINUS


%start expn


%%


expn
: VALUE_TOK
| '-' expn %prec UNARY_MINUS
| expn IDENTIFIER_TOK ':' '+' expn
| expn '+' expn
        ;


If giving IDENTIFIER_TOK a precedence causes problems, you can enforce
precedence levels without using yacc's precedence levels by having separate
levels of non-terminals (like the classical arithmetic expression grammar).
Another alternative might be able to get your lexer to return a separate
token for the sequence IDENTIFIER_TOK ':' '+' (possibly using start-states
or token buffering).


-zerksis umrigar.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.