¿Es esta gramática no LR (1)?

Question

Estoy trabajando en de análisis generador para PHP . Actualmente estoy tratando de poner en práctica canónica LR (1) analizador , pero salidas de reducir el efecto de reducir los conflictos en la siguiente gramática. ¿Es esta gramática no LR (1)? O debería volver a comprobar mis algoritmos?

Gramática en notación bisonte (similares):

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 regla terms:

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

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

Una forma de solucionar este problema es eliminar la cláusula /* nothing */ pero eso ciertamente cambiar su gramática aunque dudo que se desea permitir que terms a 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
    ;