미리보기 토큰 제한으로 인해 yacc에서 Shift/reduce 충돌이 발생합니까?

Question

나는 겉으로보기에는 단순한 변화/무익함을 줄이기 위해 노력해 왔습니다. 당연히 충돌을 무시하면 파서가 잘 작동하지만 규칙을 재구성하면 훨씬 안전 해집니다. 자, 내가 하나의 충돌 상대적으로 복잡한 문법 단순화했습니다 :

statement_list 
    : statement_list statement 
    | 
    ; 

statement 
    : lvalue '=' expression 
    | function 
    ; 

lvalue 
    : IDENTIFIER 
    | '(' expression ')' 
    ; 

expression 
    : lvalue 
    | function 
    ; 

function 
    : IDENTIFIER '(' ')' 
    ; 

은 yacc에서 자세한 옵션을을, 나는 언급 분쟁 상태를 설명이 출력 파일 수 :

state 2 

    lvalue -> IDENTIFIER . (rule 5) 
    function -> IDENTIFIER . '(' ')' (rule 9) 

    '(' shift, and go to state 7 

    '(' [reduce using rule 5 (lvalue)] 
    $default reduce using rule 5 (lvalue) 

감사를 어떤 도움이 필요해.

Answer 1

문제점은 2 토큰 미리보기가 명령문의 끝에 도달했을 때이를 알아야한다는 점입니다. 양식의 입력이있는 경우 : 파서 ​​후

ID = ID (ID) = ID 

두 번째 ID (내다가 (이다), 그것은 그 첫 번째 명령문의 끝인지 모르는를 이동합니다 (( 두 번째 문장의 시작입니다), 또는 이것은 함수입니다. 그래서 위의 예제 입력으로하는 것은 잘못되었습니다 (함수를 계속 파싱). 당신이 실제 표현을 할 수 있도록 괄호와 expression 내부의 인수를 허용하는 function을 확장 할 경우 필요한 내다가 억제 할 같이

는 상황이 악화 될 - 파서가이 있음을 결정하기 위해 두 번째 =에 모든 방법을 얻을 필요가있다 함수 호출이 아닙니다.

기본 문제는 구문 분석기가 문장의 끝을 찾는 데 도움이되는 도우미 구두점이 없다는 것입니다. 유효한 명령문의 시작 부분 인 텍스트는 유효한 명령문의 중간에 나타날 수도 있기 때문에 명령문 경계를 찾는 것이 어렵습니다.