Menu
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 */
305
The parser is stumped by the terms rule:
terms
: /* nothing */
| term
| term terms
;
Since terms can mean 'nothing', there would be cases where the input to be parsed can map to either the grammar term or term terms, thus causing reduce-reduce conflict (which means there are two way to reduce the same input, thus the parser can't make the decision).
One way to fix this is to remove the /* nothing */ clause but that would certainly change your grammar although I doubt you would want to allow terms to be 'nothing' since you would be allowing double | in the expressions rule.
If you still want to maintain the grammar, you need to break the rule into pieces, for example:
expression
: terms_or_nothing
| terms_or_nothing '{' CODE '}'
;
terms_or_nothing
: /* nothing */
| terms
terms
: term
| term terms
;
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
