간단한 모호한 문법 감소-감소 감소/감소 충돌 논리식의 결과 구문 분석 충돌을

Question

다음과 같은 간단한 문법 :

이

%token AND OR 
%token NUMBER VARIABLE 
%% 
logical_expr 
    : logical_expr AND logical_term 
    | logical_expr OR logical_term 
    | logical_term 
    ; 
logical_term 
    : VARIABLE 
    | comparison 
    | '(' logical_expr ')' 
    ; 
comparison 
    : expr '<' expr 
    | expr '>' expr 
    ; 
expr 
    : expr '+' term 
    | expr '-' term 
    | term 
    ; 
term 
    : NUMBER 
    | VARIABLE 
    | '(' expr ')' 
    ; 
%% 

들소에서 상태 보고서가 있습니다

state 2 

    4 logical_term: VARIABLE . 
    13 term: VARIABLE . 

    ')'  reduce using rule 4 (logical_term) 
    ')'  [reduce using rule 13 (term)] 
    '<'  reduce using rule 13 (term) 
    '>'  reduce using rule 13 (term) 
    '+'  reduce using rule 13 (term) 
    '-'  reduce using rule 13 (term) 
    $default reduce using rule 4 (logical_term) 

I을 문제를 짐작하면 "(a) + 1 < 2"를 구문 분석하는 방법을 파악할 수 없다는 것입니다. 이 문법을 어떻게 구별 할 수 있습니까? 가능한가? 그것은 ) 후 다음 토큰에 따라 달라집니다 -

Answer 1

문법과 기본 문제는 (VARIABLE 볼과 다음의 토큰을 ) 때, 파서가이 괄호 expr 또는 logical_expr해야합니다 여부를 알 수 없다는 것입니다. 다음 토큰이 + 인 경우 -, < 또는 >이면 expr이며, AND 또는 OR (또는 EOF)이면 logical_expr입니다.

일반적인 해결책은 문법에서 유형 검사를 시도하지 않는 것입니다. 가능한 한 많은 사전 검토가 필요하며 다단계 문법 또는 이러한 복잡성이 필요할 수 있습니다. 당신이 충돌이 사라질

logical_term 
    : comparison 
    | expr 
    ; 

에 logical_term 규칙을 변경하지만 파서는 a > 3 AND 2 또는 2 + 2 OR 7으로 올바른 입력되지 않은 것들을 받아 들일 경우 경우

. 결과 파스 트리 (또는 생성중인 데이터 구조)의 유형 검사를 수행해야 정확성을 확인할 수 있습니다. 그래도 어쨌든 필요하다면 (변수가 있는지 확인하기 위해 적어도 VARIABLE을 typecheck해야합니다. 숫자 또는 부울, 문맥에 따라 다릅니다.)