Est-ce la grammaire non LR (1)?
-
19-09-2019 - |
Question
Je travaille sur Parse générateur pour PHP . Actuellement, je suis en train de mettre en œuvre l'analyseur LR (1) canonique , mais sorties réduisent-réduire les conflits sur la grammaire suivante. Est-ce la grammaire non LR (1)? Ou devrais-je revérifier mes algorithmes?
Grammaire en notation Bison (de -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
;
EDIT:
Tableau calculée:
|$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, , , , | , , , , , , , , , , , , , , )
et conflits:
conflict: state = 36, terminal = ; , production = terms -> . /* empty production */
conflict: state = 36, terminal = { , production = terms -> . /* empty production */
conflict: state = 36, terminal = | , production = terms -> . /* empty production */
La solution
L'analyseur est déconcerté par la règle de terms
:
terms
: /* nothing */
| term
| term terms
;
Depuis terms
peut signifier « rien », il y aurait des cas où l'entrée à analyser peut mapper soit la term
de grammaire ou term terms
, provoquant ainsi de réduire-réduire les conflits (ce qui signifie qu'il ya deux façons de réduire la même entrée, ainsi que l'analyseur ne peut pas prendre la décision).
Une façon de résoudre ce problème est de supprimer la clause de /* nothing */
mais ce serait certainement changer votre grammaire bien que je doute que vous voulez permettre terms
d'être « rien » puisque vous permettrions à double |
dans la règle de expressions
.
Si vous voulez continuer à maintenir la grammaire, vous devez briser la règle en morceaux, par exemple:
expression
: terms_or_nothing
| terms_or_nothing '{' CODE '}'
;
terms_or_nothing
: /* nothing */
| terms
terms
: term
| term terms
;