È questa grammatica non LR (1)?

Question

Sto lavorando su parse generatore per PHP . Attualmente sto cercando di implementare canonica LR (1) parser , ma uscite riducono-riducono conflitto seguente grammatica. È questa grammatica non LR (1)? O dovrei ricontrollare i miei algoritmi?

Grammar in Bison notazione (like):

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
    ;

Modifica

Tavolo calcolato:

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

e conflitti:

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

Il parser è sconcertato dalla regola terms:

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

Da terms può significare 'nulla', ci sarebbero casi in cui l'input da analizzare può mappare sia alla term grammatica o term terms, provocando così ridurre-ridurre il conflitto (che significa che ci sono due modi per ridurre lo stesso ingresso, in tal modo il parser non può prendere la decisione).

Un modo per risolvere questo problema è quello di rimuovere la clausola /* nothing */ ma che sarebbe certamente cambiare la grammatica anche se dubito che si vorrebbe consentire terms di essere 'nulla' dal momento che si sarebbe permettendo doppio | nella regola expressions.

Se si desidera continuare a mantenere la grammatica, è necessario rompere la regola in pezzi, per esempio:

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

terms_or_nothing
    : /* nothing */
    | terms

terms
    : term
    | term terms
    ;