yacc/ocamlyacc의 충돌 감소/감소 해결

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

  •  09-06-2019
  •  | 
  •  

문제

나는 연산자 없이(예를 들어 Ocaml이나 Haskell에서) 함수 적용과 이진 및 단항 연산자의 일반적인 분류를 지원하는 ocamlyacc(일반 yacc와 거의 동일)에서 문법을 구문 분석하려고 합니다.뺄셈과 부정 모두에 사용할 수 있는 '-' 연산자와 축소/감소 충돌이 발생합니다.다음은 제가 사용하고 있는 문법 샘플입니다:

%token <int> INT
%token <string> ID
%token MINUS

%start expr
%type <expr> expr

%nonassoc INT ID
%left MINUS
%left APPLY

%%

expr: INT
    { ExprInt $1 }
| ID
    { ExprId $1 }
| expr MINUS expr
    { ExprSub($1, $3) }
| MINUS expr
    { ExprNeg $2 }
| expr expr %prec APPLY
    { ExprApply($1, $2) };

문제는 "a - b"와 같은 표현을 얻을 때 파서는 이것이 "a (-b)"(b의 부정, 그 뒤에 응용 프로그램이 옴)로 줄여야 하는지 아니면 "a - b"( 빼기).뺄셈이 맞습니다.해당 규칙에 찬성하여 갈등을 어떻게 해결합니까?

도움이 되었습니까?

해결책

불행하게도 제가 생각해 낼 수 있는 유일한 대답은 문법의 복잡성을 높이는 것뿐입니다.

  1. 나뉘다 expr ~ 안으로 simple_expr 그리고 expr_with_prefix
  2. 만 허용 simple_expr 또는 (expr_with_prefix) 적용에서

첫 번째 단계는 감소/감소 충돌을 이동/감소 충돌로 바꾸지만 괄호가 이를 해결합니다.

'a b c'에도 동일한 문제가 발생합니다.그거야? a(b(c)) 또는 (a(b))(c)?너도 헤어져야 해 applied_expression 그리고 필수 (applied_expression) 문법에서.

이렇게 하면 될 것 같지만 확실하지 않습니다.

expr := INT
      | parenthesized_expr
      | expr MINUS expr

parenthesized_expr := ( expr )
                    | ( applied_expr )
                    | ( expr_with_prefix )

applied_expr := expr expr

expr_with_prefix := MINUS expr

다른 팁

글쎄, 가장 간단한 대답은 그것을 무시하고 기본 축소/감소 해상도가 이를 처리하도록 하는 것입니다. 즉, 문법에서 처음 나타나는 규칙을 축소하는 것입니다.이 경우에는 감소한다는 의미입니다. expr MINUS expr 우선적으로 MINUS expr, 정확히 당신이 원하는 것입니다.본 후 a-b, 단항 마이너스가 아닌 이진 마이너스로 구문 분석한 다음 적용하려고 합니다.

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