Is this grammar not LR(1)?

B

by_snake

New Member
I'm working on parse generator for PHP. Currently I'm trying to implement canonical LR(1) parser, but it outputs reduce-reduce conflict on following grammar. Is this grammar not LR(1)? Or should I recheck my algorithms?Grammar in Bison(-like) notation: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:Computed table: |$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, , , , | , , , , , , , , , , , , , , )and conflicts:conflict: state = 36, terminal = ; , production = terms -> . /* empty production */conflict: state = 36, terminal = { , production = terms -> . /* empty production */conflict: state = 36, terminal = | , production = terms -> . /* empty production */
 
You must log in or register to reply here.
Back
Top