Is this grammar not LR(1)?

Question

I'm working on parse generator for PHP. Currently I'm trying to implement canonical LR(1) parser, but it outputs reduce-reduce conflict on following grammar. Is this grammar not LR(1)? Or should I recheck my algorithms?

Grammar in Bison(-like) notation:

syntax : toplevels rules ;

toplevels
    : toplevel
    | toplevel toplevels
    ;

optsem : ';' | /* nothing */ ;

toplevel
    : 'grammar' backslash_separated_name optsem
    | 'option' options optsem
    | '@' period_separated_name '{' CODE '}' optsem
    ;

period_separated_name
    : ID '.' period_separated_name
    | ID
    ;

backslash_separated_name
    : ID '\\' backslash_separated_name
    | ID
    ;

options
    : single_option
    | '(' more_options ')'
    ;

more_options
    : single_option
    | single_option ';'
    | single_option ';' more_options
    ;

single_option
    : period_separated_name '=' STRING
    | period_separated_name '=' '{' CODE '}'
    ;

rules
    : rule
    | rule rules
    ;

rule
    : ID ':' expressions ';'
    ;

expressions
    : expression
    | expression '|' expressions
    ;

expression
    : terms
    | terms '{' CODE '}'
    ;

terms
    : /* nothing */
    | term
    | term terms
    ;

term
    : ID
    | STRING
    ;

EDIT:

Computed table:

      |$en| ; |gra|opt| @ | { |COD| } |ID | . | \ | ( | ) | = |STR| : | | |syn|top|rul|top|opt|bac|opt|per|sin|mor|rul|exp|exp|ter|ter|
       --------------------------------------------------------------------------------------------------------------------------------
    0 (   ,   , s4, s5, s6,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |  1,  2,   ,  3,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
    1 (acc,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
    2 (   ,   ,   ,   ,   ,   ,   ,   , s9,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,  7,   ,   ,   ,   ,   ,   ,   ,  8,   ,   ,   ,   )
    3 (   ,   , s4, s5, s6,   ,   ,   , r2,   ,   ,   ,   ,   ,   ,   ,   |   , 10,   ,  3,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
    4 (   ,   ,   ,   ,   ,   ,   ,   ,s12,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   , 11,   ,   ,   ,   ,   ,   ,   ,   ,   )
    5 (   ,   ,   ,   ,   ,   ,   ,   ,s16,   ,   ,s17,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   , 13, 14, 15,   ,   ,   ,   ,   ,   )
    6 (   ,   ,   ,   ,   ,   ,   ,   ,s19,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   , 18,   ,   ,   ,   ,   ,   ,   )
    7 ( r1,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
    8 (r20,   ,   ,   ,   ,   ,   ,   , s9,   ,   ,   ,   ,   ,   ,   ,   |   ,   , 20,   ,   ,   ,   ,   ,   ,   ,  8,   ,   ,   ,   )
    9 (   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,s21,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   10 (   ,   ,   ,   ,   ,   ,   ,   , r3,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   11 (   ,s23, r5, r5, r5,   ,   ,   , r5,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   , 22,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   12 (   ,r12,   ,   ,   ,   ,   ,   ,   ,   ,s24,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   13 (   ,s23, r5, r5, r5,   ,   ,   , r5,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   , 25,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   14 (   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,s26,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   15 (   ,r13,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   16 (   ,   ,   ,   ,   ,   ,   ,   ,   ,s27,   ,   ,   ,r10,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   17 (   ,   ,   ,   ,   ,   ,   ,   ,s16,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   , 28, 29, 30,   ,   ,   ,   ,   )
   18 (   ,   ,   ,   ,   ,s31,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   19 (   ,   ,   ,   ,   ,r10,   ,   ,   ,s32,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   20 (r21,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   21 (   ,r27,   ,   ,   ,r27,   ,   ,s37,   ,   ,   ,   ,   ,s38,   ,r27|   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   , 33, 34, 35, 36)
   22 (   ,   , r6, r6, r6,   ,   ,   , r6,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   23 (   ,   , r4, r4, r4,   ,   ,   , r4,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   24 (   ,   ,   ,   ,   ,   ,   ,   ,s12,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   , 39,   ,   ,   ,   ,   ,   ,   ,   ,   )
   25 (   ,   , r7, r7, r7,   ,   ,   , r7,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   26 (   ,   ,   ,   ,   ,s40,   ,   ,   ,   ,   ,   ,   ,   ,s41,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   27 (   ,   ,   ,   ,   ,   ,   ,   ,s16,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   , 42,   ,   ,   ,   ,   ,   ,   )
   28 (   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,s43,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   29 (   ,s44,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,r15,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   30 (   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,s45,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   31 (   ,   ,   ,   ,   ,   ,s46,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   32 (   ,   ,   ,   ,   ,   ,   ,   ,s19,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   , 47,   ,   ,   ,   ,   ,   ,   )
   33 (   ,s48,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   34 (   ,r23,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,s49|   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   35 (   ,r25,   ,   ,   ,s50,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,r25|   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   36 (   ,r27,   ,   ,   ,r27,   ,   ,s37,   ,   ,   ,   ,   ,s38,   ,r27|   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   , 51, 36)
   37 (   ,r30,   ,   ,   ,r30,   ,   ,r30,   ,   ,   ,   ,   ,r30,   ,r30|   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   38 (   ,r31,   ,   ,   ,r31,   ,   ,r31,   ,   ,   ,   ,   ,r31,   ,r31|   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   39 (   ,r11,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   40 (   ,   ,   ,   ,   ,   ,s52,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   41 (   ,r18,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   42 (   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   , r9,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   43 (   ,   ,   ,   ,   ,s53,   ,   ,   ,   ,   ,   ,   ,   ,s54,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   44 (   ,   ,   ,   ,   ,   ,   ,   ,s16,   ,   ,   ,r16,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   , 28, 29, 55,   ,   ,   ,   ,   )
   45 (   ,r14,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   46 (   ,   ,   ,   ,   ,   ,   ,s56,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   47 (   ,   ,   ,   ,   , r9,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   48 (r22,   ,   ,   ,   ,   ,   ,   ,r22,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   49 (   ,r27,   ,   ,   ,r27,   ,   ,s37,   ,   ,   ,   ,   ,s38,   ,r27|   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   , 57, 34, 35, 36)
   50 (   ,   ,   ,   ,   ,   ,s58,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   51 (   ,r29,   ,   ,   ,r29,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,r29|   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   52 (   ,   ,   ,   ,   ,   ,   ,s59,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   53 (   ,   ,   ,   ,   ,   ,s60,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   54 (   ,r18,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,r18,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   55 (   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,r17,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   56 (   ,s23, r5, r5, r5,   ,   ,   , r5,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   , 61,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   57 (   ,r24,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   58 (   ,   ,   ,   ,   ,   ,   ,s62,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   59 (   ,r19,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   60 (   ,   ,   ,   ,   ,   ,   ,s63,   ,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   61 (   ,   , r8, r8, r8,   ,   ,   , r8,   ,   ,   ,   ,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   62 (   ,r26,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,r26|   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )
   63 (   ,r19,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,r19,   ,   ,   ,   |   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   ,   )

and conflicts:

conflict: state = 36, terminal =  ; , production = terms ->  .  /* empty production */
conflict: state = 36, terminal =  { , production = terms ->  .  /* empty production */
conflict: state = 36, terminal =  | , production = terms ->  .  /* empty production */

I'd rather not read through all of this and try to work it out for myself, but if you can tell me what the error is (ie where it says the reduce-reduce conflict is) I can try to help you. — danben, Jan 11 '10 at 14:42
@danben I added computed table (left part is action table, right part goto table) and what is conflicting. It seems it has something to do with empty `terms` production. — Jakub Kulhan, Jan 11 '10 at 15:38

score 7 · Accepted Answer · answered Jan 11 '10 at 15:53

The parser is stumped by the terms rule:

terms
    : /* nothing */
    | term
    | term terms
    ;

Since terms can mean 'nothing', there would be cases where the input to be parsed can map to either the grammar term or term terms, thus causing reduce-reduce conflict (which means there are two way to reduce the same input, thus the parser can't make the decision).

One way to fix this is to remove the /* nothing */ clause but that would certainly change your grammar although I doubt you would want to allow terms to be 'nothing' since you would be allowing double | in the expressions rule.

If you still want to maintain the grammar, you need to break the rule into pieces, for example:

expression
    : terms_or_nothing
    | terms_or_nothing '{' CODE '}'
    ;

terms_or_nothing
    : /* nothing */
    | terms

terms
    : term
    | term terms
    ;

Is this grammar not LR(1)?

1 Answers1