Ngữ pháp này không phải là LR (1)?

Question

Tôi đang làm việc theo số parse generator for PHP. Hiện tại tôi đang cố gắng để implement canonical LR(1) parser, nhưng nó kết quả đầu ra giảm thiểu xung đột về ngữ pháp sau đây. Ngữ pháp này không phải là LR (1)? Hay tôi nên kiểm tra lại thuật toán của mình?

Grammar in Bison (-like) ký hiệu:

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:

Tính toán bảng:

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

và xung đột:

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

Các phân tích cú pháp được bối rối bởi các terms quy tắc:

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

Kể từ terms có thể có nghĩa là 'không có gì', sẽ có trường hợp đầu vào được phân tích có thể ánh xạ tới một trong hai ngữ pháp term hoặc term terms, gây làm giảm-giảm xung đột (có nghĩa là có hai cách để giảm cùng một đầu vào, do đó trình phân tích cú pháp không thể đưa ra quyết định).

Một cách để sửa lỗi này là để loại bỏ các khoản /* nothing */ nhưng điều đó chắc chắn sẽ thay đổi ngữ pháp của bạn mặc dù tôi nghi ngờ bạn sẽ muốn cho phép terms là 'không có gì' vì bạn sẽ được cho phép tăng gấp đôi | trong quy tắc expressions.

Nếu bạn vẫn muốn duy trì ngữ pháp, bạn cần phải phá vỡ các quy tắc thành từng miếng, ví dụ:

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

terms_or_nothing 
    : /* nothing */ 
    | terms 

terms 
    : term 
    | term terms 
    ;