이 문법은 LR이 아닌가? (1)?
-
19-09-2019 - |
문제
나는 일하고있다 PHP 용 구조 생성기. 현재 나는 노력하고있다 표준 LR (1) 파서를 구현합니다, 그러나 문법에 따라 갈등이 줄어든다. 이 문법은 LR이 아닌가? (1)? 아니면 알고리즘을 다시 확인해야합니까?
들소의 문법 (-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
;
편집하다:
계산 된 테이블 :
|$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, , , , | , , , , , , , , , , , , , , )
그리고 갈등 :
conflict: state = 36, terminal = ; , production = terms -> . /* empty production */
conflict: state = 36, terminal = { , production = terms -> . /* empty production */
conflict: state = 36, terminal = | , production = terms -> . /* empty production */
해결책
파서는 terms
규칙:
terms
: /* nothing */
| term
| term terms
;
부터 terms
'아무것도'를 의미 할 수 있습니다. 구문 분석 할 입력이 문법에 매핑 될 수있는 경우가 있습니다. term
또는 term terms
, 따라서 감소 감소 충돌을 유발합니다 (이는 동일한 입력을 줄이는 두 가지 방법이 있음을 의미하므로 파서는 결정을 내릴 수 없습니다).
이것을 고치는 한 가지 방법은 제거하는 것입니다 /* nothing */
조항이지만, 당신이 허용하고 싶다고 의심하지만 그것은 당신의 문법을 확실히 바꿀 것입니다. terms
두 배를 허용하기 때문에 '아무것도' |
에서 expressions
규칙.
그래도 문법을 유지하려면 규칙을 조각으로 나누어야합니다.
expression
: terms_or_nothing
| terms_or_nothing '{' CODE '}'
;
terms_or_nothing
: /* nothing */
| terms
terms
: term
| term terms
;
제휴하지 않습니다 StackOverflow