Bison은 문법의 충돌을 줄이거 나 줄일 것입니다.

Question

나는 들소에 문법을 작성하고 있는데 r/r 충돌이 있습니다 (나는 그것이 어디 있는지 압니다). 그러나 그것을 고치는 방법을 모르겠습니다. 가능한 도움을 주시면 감사하겠습니다.

충돌을 포함 내 코드의 일부는 다음과 같습니다

orismos2: %empty 
|orismos orismos2 
|error {yyerrok;yyclearin;}; 

orismos: orismosmetablitwn 
|orismossunartisis 
|prwtotuposunartisis; 

orismosmetablitwn: tuposdedomenwn listametablitwn SEMICOLON ; 

tuposdedomenwn: INT 
|BOOL 
|STRING; 

listametablitwn: ID nid ; 

nid: %empty 
|pid nid 
|error {yyerrok;yyclearin;}; 

pid: COMMA ID ; 

orismossunartisis: kefalidasunartisis tmimaorismwn tmimaentolwn; 

prwtotuposunartisis: kefalidasunartisis SEMICOLON; 

kefalidasunartisis: typos_synartisis ID OPENBRACKET c CLOSEBRACKET; 

typos_synartisis: INT 
|BOOL 
|VOID; 

는 내가 모든 충돌을 볼 수있는 출력 파일을 만들 수 있습니다. 충돌을 포함하는 파일의

부분은 다음과 같습니다 정말 모든 노력을했지만, 나는 충돌을 제거 할 수 없습니다

State 21 conflicts: 1 reduce/reduce 
State 22 conflicts: 1 reduce/reduce 


Grammar 

    10 orismos2: %empty 
    11   | orismos orismos2 
    12   | error 

    13 orismos: orismosmetablitwn 
    14  | orismossunartisis 
    15  | prwtotuposunartisis 

    16 orismosmetablitwn: tuposdedomenwn listametablitwn SEMICOLON 

    17 tuposdedomenwn: INT 
    18    | BOOL 
    19    | STRING 

    20 listametablitwn: ID nid 

    21 nid: %empty 
    22 | pid nid 
    23 | error 

    24 pid: COMMA ID 

    25 orismossunartisis: kefalidasunartisis tmimaorismwn tmimaentolwn 

    26 prwtotuposunartisis: kefalidasunartisis SEMICOLON 

    27 kefalidasunartisis: typos_synartisis ID OPENBRACKET c CLOSEBRACKET 

    28 typos_synartisis: INT 
    29     | BOOL 
    30     | VOID 


State 21 

    17 tuposdedomenwn: INT . 
    28 typos_synartisis: INT . 

    ID  reduce using rule 17 (tuposdedomenwn) 
    ID  [reduce using rule 28 (typos_synartisis)] 
    $default reduce using rule 17 (tuposdedomenwn) 


State 22 

    18 tuposdedomenwn: BOOL . 
    29 typos_synartisis: BOOL . 

    ID  reduce using rule 18 (tuposdedomenwn) 
    ID  [reduce using rule 29 (typos_synartisis)] 
    $default reduce using rule 18 (tuposdedomenwn) 

... 어떤 아이디어 나 제안을 환영합니다!

감사합니다.

Answer 1

키가 여기에 있습니다. & hellip; 또한

orismos → (13) orismosmetablitwn → (16) tuposdedomenwn listametablitwn 
orismos → (14) orismossunartisis → (25) kefalidasunartisis … → (27) typos_synartisis … 
orismos → (15) prwtotuposunartisis → (26) kefalidasunartisis … → (27) typos_synartisis … 

:

orismos → orismosmetablitwn → tuposdedomenwn listametablitwn → NUMBER ID … 
orismos → orismossunartisis → kefalidasunartisis … → typos_synartisis … → NUMBER ID … 
orismos → prwtotuposunartisis → kefalidasunartisis … → typos_synartisis … → NUMBER ID … 

우리가 orismis이 가능합니다 컨텍스트에있는 말, 우리는 단지 NUMBER을 보았다 :

tuposdedomenwn → NUMBER | BOOL | STRING 
listametablitwn → ID … 
kefalidasunartisis → typos_synartisis ID … 
typos_synartisis → NUMBER | BOOL | VOID 

그래서, 여기에 약간의 유도는 orismos 출신 이제 우리는 ID을보고 있습니다. 위의 세 가지 유도가 모두 가능합니다. 그러나 작은 문제가 있습니다. 첫 번째 문단에서 NUMBER은 tuposdedomenwn에서 파생되며 두 번째 문에서는 typos_synartisis에서 파생됩니다. ID으로 무엇이든 할 수 있기 전에, 우리는 두 파생어 중 어느 것을 줄일지를 알아야하지만, ID 뒤에 토큰이 나타날 때까지는 알 수있는 방법이 없습니다.

즉, 문법에 두 개의 미리보기 토큰이 필요하므로 LALR (1) 파서가 구문 분석 할 수 없습니다. 그런 다음 나중에 의미 론적 확인을해야 할 것

tuposdedomenwn: NUMBER | BOOL | STRING | VOID 

:

가장 간단한 해결 방법은 네 가지 possibilites을 할 수있는 비 터미널을 만드는 종류의 세트를 나타내는 두 개의 비 단자를 결합하는 것 변수가 선언되지 않았는지 확인하려면 VOID 또는 함수가 STRING으로 선언되어 있는지 확인하십시오. (함수가 문자열을 반환 할 수없는 이유는 무엇입니까? 조금 제한적인 것처럼 보입니다.) AST 작성시 또는 나중에 구문의 의미를 확인하는이 전략은 매우 일반적입니다. 예를 들어 변수를 사용하기 전에 선언을 시행하는 유일한 방법입니다.

하지만 의미 검사를 원하지 않으면 단순히 데이터 유형과 ID으로 구성된 비 터미널을 만들어서 감축을 연기 할 수 있습니다.즉, 같은 이어질 것 : 그 변화와

tupodedomenon_kai_metavlites 
     : INT ID 
     | BOOL ID 
     | STRING ID 
     | tupodedomenon_kai_metavlites ',' ID 

tupo_synartisis_kai_metavliton 
     : INT ID 
     | BOOL ID 
     | VOID ID 

orismos: orismosmetablitwn 
     | orismossunartisis 
     | prwtotuposunartisis 

orismosmetablitwn 
     : tupodedomenon_kai_metavlites ';' 

orismossunartisis 
     : kefalidasunartisis tmimaorismwn tmimaentolwn 

prwtotuposunartisis 
     : kefalidasunartisis ';' 

kefalidasunartisis 
     : tupo_synartisis_kai_metavliton '(' c ')' 

의 NUMBER (또는 다른 타입)을 감소 할 필요가 없다; ID 시프트 될 수 있고, 그리고 하나의 환원 또는 다른 가능성은 다음의 토큰에 기초하여 수행 될 것이다 : 변수 선언으로서 다음 토큰 ; 또는 , 경우와 함수 선언으로서 다음 토큰 ( 경우.