Czy ta gramatyka nie jest LR (1)?

Question

Pracuję nad parse generator for PHP. Obecnie próbuję wykonać implement canonical LR(1) parser, ale generuje on konflikt zmniejszający redukcję w następującej gramatyce. Czy ta gramatyka nie jest LR (1)? Czy powinienem ponownie sprawdzić moje algorytmy?

gramatyki Bison (-podobnych) oznaczenia:

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 
    ; 

Edycja:

komputerowa tabeli:

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

konflikty:

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

Parser jest zakłopotany przez terms zasady:

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

Od terms może oznaczać „nic”, nie byłoby sprawy, w których wejście do być analizowany może odwzorowywać albo gramatyki term lub term terms, powodując skrócenie-zredukować konflikt (co oznacza, że ​​istnieją dwa sposoby zmniejszenia tego samego wejścia, dlatego parser nie może podjąć decyzji).

Jednym ze sposobów, aby to naprawić jest usunięcie klauzuli /* nothing */ ale to na pewno zmieni swoją gramatykę, choć wątpię, aby zezwolić terms być „nic”, ponieważ można byłoby umożliwienie podwójne | w regule expressions.

Jeśli nadal chcesz zachować gramatykę, trzeba złamać regułę na kawałki, na przykład:

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

terms_or_nothing 
    : /* nothing */ 
    | terms 

terms 
    : term 
    | term terms 
    ;