yacc/ocamlyacc의 충돌 감소/감소 해결
문제
나는 연산자 없이(예를 들어 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"( 빼기).뺄셈이 맞습니다.해당 규칙에 찬성하여 갈등을 어떻게 해결합니까?
해결책
불행하게도 제가 생각해 낼 수 있는 유일한 대답은 문법의 복잡성을 높이는 것뿐입니다.
- 나뉘다
expr
~ 안으로simple_expr
그리고expr_with_prefix
- 만 허용
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
, 단항 마이너스가 아닌 이진 마이너스로 구문 분석한 다음 적용하려고 합니다.