YACC 생성 파서가 동일한 입력에 대해 서로 다른 출력을 제공합니다.

Question

YACC 및 LEX을 사용하여 문법이 a^nb^n과 일치하면 문자열을 확인하고 싶습니다.

렉스 파일 : 여기에 같은 순서로 내 LEX와 YACC 파일은

%{ 
    #include <stdio.h> 
    #include <y.tab.h> 
    %} 

    %% 
    a {return A;} 
    b {return B;} 
    . {return yytext[0];} 
    \n {return NL;} 
    %% 
    int yywrap(void) { 
     return 1; 
    } 

YACC 파일 :

입력 문자열 :

%{ 
    #include <stdio.h> 
    yyerror() 
    { 
    printf("Rejected\n"); 
    }  
    %} 

    %token A B NL 
    %start T 

    %% 

    T : S NL {printf("accepted\n");} 
    ; 
    S : A S B 
    | A B 
    ; 

    %% 

    main() 
    { 
    yyparse(); 
    } 

문제는 출력은 AABB

출력 : 허용

,

입력 문자열 : AABB

출력 : 두 번째 입력시 동일한 입력 또는 응답을 허용 할 수 있다고 가정하는 모든 입력이 거부

를 거부 하였다. YACC에는 문자열을 파싱 할 때 사용하는 스택이 있다는 것을 알게되었습니다. 그러나 그것에 관한 어떤 문서도 찾을 수 없었습니다. 도와주세요.

Answer 1

yacc 규칙 T은 비 재귀 적입니다. 이는 하나의 행과 만 일치 함을 의미합니다. 다음 수정은 아무 행도 보지 않습니다 (none 포함).

T : T S NL 
    | /* empty */ 
    ; 

연속 된 행이 허용됩니다.

$ printf 'aabb\naabb\n' | ./a.out 
accepted 
accepted 

Answer 2

나는 반복적으로 파서를 실행하여 결과를 재현 할 수없는,하지만 난 같은 실행에 파서에게 여러 문자열을 공급하여 재현 할 수 있습니다. 이 차이를 이해하는 것이 중요합니다 : 하나의 실행 yyparse()이 실행되며, 렉서가 파일 끝을 알리는 지점까지 전체 입력을 구문 분석하려고합니다. @ kdhp의 대답은 파서가 여러 줄을 동일한 실행에서 허용하지 않는 이유를 설명하고 원하는 결과를 얻을 수있는 방법을 제시합니다.

---

다른 방법으로 진실로 여러 번 실행하는 것입니다.이 작업은 파서와 렉서를 조정하여 수행 할 수 있습니다. 렉서는 개행 문자를 볼 때 입력 끝을보고해야하므로 구문 분석기는 개행을 전혀 고려할 필요가 없습니다.

게다가, 두 경우 모두 필요한 렉서는 매우 간단하여 lex (또는 flex)을 생성하는 것은 과도합니다. 적합한 yylex()을 직접 작성하는 것이 훨씬 간단합니다. 또한 직접 작성하면 main()에서 줄 끝과 끝 부분을 구분할 수있는 편리 성을 제공 할 수 있습니다. main() 앞서 문법 파일에 나타날 수있는 모든을 지원하는 렉서 : 편의상

int end_of_input = 0; 

int yylex(void) { 
    int c = getc(); /* no buffering inside the lexer */ 

    if (c < 0) { 
     end_of_input = 1; 
    } 
    return ((c == '\n') ? 0 : c); 
} 

파서 가정이이 경우에하지 말아야 할에 대한 특별한 이유가없는 문자 토큰을 사용합니다.또한, 필요로하는 유일한 규칙은 (지금 시작 기호)가 아닌 터미널 S에 대한 원래의 규칙에이 변종이다 : 그 렉서 및 해당 규칙으로

S : 'a' S 'b' 
    | 'a' 'b' 
    ; 

는 yyparse()의 각 실행은 최대 구문 분석 한 줄 (단, 줄 끝 앞의 구문 분석 오류에서 멈출 수 있음), 전체 줄이 성공적으로 파싱 된 경우에만 0을 반환합니다. 그런 다음 루프에서 실행 :

int main(void) 
{ 
    do { 
     if (yyparse() == 0)) { 
      puts("accepted"); 
     } // else yyerror() already printed "rejected" 
    } while (!end_of_input); 
} 

을 최종 참고로, 구문 분석 오류가 입력 라인의 중간에 어딘가에있을 경우, 위에서 그 라인의 나머지 부분을 소비하지 않는다는 것을 인정한다 (어느 쪽도 당신의 버전을하지 않는다). 오류가 발생하면 main() 또는 구문 분석기의 오류 규칙을 통해 다음 줄의 구문 분석을 계속 진행합니다. 그것은 확실히 할 수 있습니다. 나는 그것을 운동으로 남겨 둡니다.