다음 감소 감소 오류 (LALR 구문 분석)를 해결할 수 없습니다.

Question

현재 Decaf (프로그래밍 언어) 문법의 일부를 구현 중입니다. 여기 들소 코드의 관련 단편이다 그럼에도 불구하고

type: 
    INT 
    | ID 
    | type LS RS 
    ; 

local_var_decl: 
    type ID SEMICOLON 
    ; 

name: 
    THIS 
    | ID 
    | name DOT ID 
    | name LS expression RS 
    ; 

, 최대한 빨리 이름 생산 규칙 작업을 시작으로, 내 파서 경고를-감소 줄이기 을 제공합니다. 이 (들소에 의해 생성)을 · 출력 파일 내부에 무엇이 여기

: 우리는 다음과 같은 입력 { abc[1] = abc; }을 주면

State 84 

    23 type: ID . 
    61 name: ID . 

    ID  reduce using rule 23 (type) 
    LS  reduce using rule 23 (type) 
    LS  [reduce using rule 61 (name)] 
    $default reduce using rule 61 (name) 

그래서, 그 syntax error, unexpected NUMBER, expected RS을 말한다. NUMBER은 여기 표현 규칙 (기본적으로 어떻게 구문 분석해야합니다)이지만, local_var_decl 규칙을 통해 구문 분석하려고 시도합니다.

이 문제를 해결하기 위해 무엇을 변경해야한다고 생각하십니까? 약 2 시간을 소비하고, 다른 것을 시도하고, 작동하지 않았습니다.

감사합니다.

추신. 여기 link이 전체 입니다 .y 소스 코드

Answer 1

이 정보는 충분한 정보가 나오기 전에 파서가 결정을 내려야하는 일반적인 문제의 특정 인스턴스입니다. 이 경우와 같이 필요한 정보가 멀리 떨어져 있지 않은 경우가 있습니다. 가능한 경우 미리보기를 늘리는 것만으로도 충분합니다. (불행히도, 파서 생성기는 k > 1 인 LR (k) 파서를 생성하지 않으며 바이슨도 예외는 아닙니다.) 일반적인 해결책은 결정할 필요없이 구문 분석을 계속 진행하는 것입니다. bison (C 모드에서만)을 사용하는 또 다른 솔루션은 %glr-parser을 요청하는 것인데, 이는 처리 시간을 추가로 줄이면 처리량을 줄일 필요가있을 때 훨씬 더 유연합니다. 이 경우

는 콘텍스트 중 하나 [ (LS) 뒤에 ID 시작할 수 모두의 type 또는 name을 허용한다. name의 경우 [ 뒤에 숫자가 와야합니다. type의 경우 [ 뒤에 ]이 와야합니다. 따라서 ID 다음에 두 번째 토큰을 볼 수 있다면 즉시 결정할 수 있습니다.

하지만 하나의 토큰 만 볼 수 있습니다 (]). 그리고 문법은 우리가 즉각적인 결정을 내릴 수 있다고 주장합니다. 한 경우에 ID을 name으로, 다른 경우를 type으로 줄여야하기 때문입니다. 따라서 우리는 reduce-reduce 충돌이 발생합니다. bison은 문법 파일에서 항상 감소를 사용하여 해결합니다.

하나의 해결책은 제작 선택 복제를 피하면서이 선택을 강요하는 것입니다. 예 :

type_other: 
    INT 
    | ID LS RS 
    | type_other LS RS 
    ; 
type: ID 
    | type_other 
    ; 

name_other: 
    THIS 
    | ID LS expression RS 
    | name_other DOT ID 
    | name_other LS expression RS 
    ; 
name: ID 
    | name_other 
    ;