¿Esta gramática no es LR (1)?

Question

Estoy trabajando en parse generator for PHP. Actualmente estoy tratando de implement canonical LR(1) parser, pero genera conflictos de reducción-reducción en la siguiente gramática. ¿Esta gramática no es LR (1)? ¿O debería volver a verificar mis algoritmos?

Gramática de Bison (similares a) la notación:

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:

mesa computarizada:

 |$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, , , , | , , , , , , , , , , , , , , ) 

y conflictos:

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

Answer 1

El analizador está perplejo por la terms regla:

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

Desde terms puede significar 'nada', no habría casos en los que la entrada sea analizado puede asignar a cualquiera de la gramática term o term terms, causando así reducir el efecto de reducir conflicto (lo que significa que hay dos formas de reducir la misma entrada, por lo tanto, el analizador no puede tomar la decisión).

Una forma de solucionar este problema es eliminar la cláusula /* nothing */ pero que sin duda cambiar su gramática aunque dudo que se desea permitir que terms para ser 'nada' ya que estaría permitiendo doble | en la regla expressions.

Si todavía quiere mantener la gramática, es necesario romper la regla en trozos, por ejemplo:

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

terms_or_nothing 
    : /* nothing */ 
    | terms 

terms 
    : term 
    | term terms 
    ;