GnuWin32 Bison에서 Shift/Reduce 경고를 해결 하시겠습니까?

Question

나는 다음과 같은 규칙을 가지고 있고 바이슨과 함께 구현할 때 나는 5 개의 시프트/감소 경고를 얻는다. 규칙

일부는 다음과 같습니다

Type---->  BOOL 
    | INT 
    | CHAR  
    | DOUBLE 
    | ID 
    | INT '['']' 
; 
rule:   VarDec rule 
    | VarDec 
; 
VarDec: Type ID ';' 
; 

과 Parser.output이 상태에서 나에게 경고를 줄 :

**state 25**

4 rule: VarDec . rule 
5  | VarDec . 

BOOL  shift, and go to state 3 
INT   shift, and go to state 4 
CHAR  shift, and go to state 5 
DOUBLE  shift, and go to state 6 
ID   shift, and go to state 7 

BOOL  [reduce using rule 5 (rule)] 
INT   [reduce using rule 5 (rule)] 
CHAR  [reduce using rule 5 (rule)] 
DOUBLE  [reduce using rule 5 (rule)] 
ID   [reduce using rule 5 (rule)] 
$default reduce using rule 5 (rule) 

rule   go to state 28 
VarDec   go to state 25 
Type   go to state 27 

이 사람이 나에게이 문제를 해결하는 방법에 도움이 될 수 있습니다, 나는 많은 기사를 읽었지 만 무엇이 잘못 되었는가를 알아낼 수 없었으며 모든 사람에게 미리 감사드립니다 ... :)

Answer 1

위의 예제는 shift/reduce 충돌을 재현하기에 충분하지 않습니다. 예를 들어 rule의 인스턴스가 있고 그 뒤에 VarDec 또는 그 뒤에 토큰이옵니다. 나는 다음과 같은 규칙을 추가하는 경우

, 나는 충돌을 재현 할 수 있습니다 : 그 규칙은 문제를 일으키는

decl : rule VarDec; 

.

Answer 2

구문 분석 스택 맨 위에 VarDec이 있고 다음 토큰이 BOOL, INT, CHAR, DOUBLE 또는 ID 인 상태에서 충돌이 발생합니다. 파서는 앞으로 다른 VarDec을 볼 것인지를 결정하기 위해 적어도 두 개의 토큰을 살펴볼 필요가 있습니다.이 경우 바른 행동은 나중에 나중에 토큰을 '규칙'으로 줄이기 위해 앞으로 옮길 것입니다. 그것은 다른 것을보고 있습니다. 어떤 경우에는 현재 스택 맨 위에있는 VarDec을 '규칙'으로 줄이는 것이 올바른 작업입니다.

너무처럼 '규칙'규칙을 변경하여이 특정 충돌을 해결 할 수 있어야한다 :

rule: rule VarDec 
    | VarDec 
; 

대신 바로 재귀의 왼쪽 재귀를 사용할 수 있습니다. 항상은 Bison 규칙에서 오른쪽 재귀 대신 왼쪽 재귀를 사용해야하기 때문에 역시 좋습니다. 이렇게하면 제한된 스택 공간으로 모든 입력을 구문 분석 할 수 있습니다.

Bison으로 식별되는 실제 상태는 해당 변경 사항과 약간 다를 수 있지만 가능한 경우 VarDec이 스택 맨 위에 있고 BOOL, INT, CHAR, DOUBLE 또는 ID 중 하나가 다음 토큰에는 하나의 가능한 동작 만 제공됩니다 (규칙 만 표시). 스택의 VarDec을 '규칙'으로 줄입니다. 다가오는 토큰이 나중에 VarDec으로 축소되지 않을지라도 다른 가능한 구문 분석은 없습니다.