명확한 문법에서 Shift-Reduce 충돌을 해결하는 방법

StackOverflow https://stackoverflow.com/questions/958885

문제

LALR(1) 파서 생성기(Bison, 그러나 문제는 해당 도구에만 국한되지 않음)를 사용하여 간단한 문법을 ​​구문 분석하려고 하는데 Shift-Reduce 충돌이 발생합니다.이 문제를 해결하는 방법에 대해 내가 찾은 문서 및 기타 소스에는 다음 중 하나 이상이 나와 있는 경향이 있습니다.

  • 문법이 모호한 경우(예:if-then-else 모호성), 모호성을 수정하려면 언어를 변경하세요.
  • 연산자 우선순위 문제인 경우 우선순위를 명시적으로 지정하세요.
  • 기본 해상도를 수락하고 생성기에 이에 대해 불평하지 않도록 지시합니다.

그러나 다음 중 어느 것도 내 상황에 적용되지 않는 것 같습니다.내가 알 수 있는 한 문법은 명확하고(물론 예측 문자가 하나만 있으면 모호하지만) 연산자가 하나뿐이며 기본 해결 방법으로 인해 올바른 형식의 입력에 대해 구문 분석 오류가 발생합니다.위의 버킷에 속하지 않는 Shift-Reduce 충돌을 제거하기 위해 문법 정의를 재작업하는 기술이 있습니까?

구체적으로 문제의 문법은 다음과 같습니다.

%token LETTER

%%
%start input;
input:          /* empty */ | input input_elt;
input_elt:      rule | statement;
statement:      successor ';';
rule:           LETTER "->" successor ';';
successor:      /* empty */ | successor LETTER;
%%

이는 "[A-Za-z]+" 또는 "[A-Za-z] -> [A-Za-z]+" 형식의 세미콜론으로 구분된 줄을 구문 분석하는 것입니다.

도움이 되었습니까?

해결책

Solaris 버전 사용 yacc, 나는 얻다:

1: shift/reduce conflict (shift 5, red'n 7) on LETTER
state 1
    $accept :  input_$end
    input :  input_input_elt
    successor : _    (7)

    $end  accept
    LETTER  shift 5
    .  reduce 7

    input_elt  goto 2
    rule  goto 3
    statement  goto 4
    successor  goto 6

따라서 문제는 빈 규칙, 특히 빈 후임자라는 점입니다.세미콜론을 유효한 입력으로 허용할지 여부는 완전히 명확하지 않습니다. 현재로서는 그렇습니다.후속 규칙을 다음과 같이 수정한 경우:

successor: LETTER | successor LETTER;

이동/감소 충돌이 제거됩니다.

다른 팁

문법을 줄여서 올려주셔서 감사합니다.후속 규칙을 다음으로 변경 -

successor:      /* empty */ | LETTER successor;

...나를 위해 일했습니다.ITYM 언어 분명해 보였습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top