Bison : 줄이기/줄이기 충돌을 수정하는 방법

Question

다음은 내 문제를 설명하는 Bison 문법입니다. 실제로 사용하는 문법은 더 복잡합니다. 입력

%glr-parser 
%% 
s : e | p '=' s; 
p : fp | p ',' fp; 
fp : 'x'; 
e : te | e ';' te; 
te : fe | te ',' fe; 
fe : 'x'; 

몇 가지 예는 다음과 같습니다

x 
x = x 
x,x = x,x 
x,x = x;x 
x,x,x = x,x;x,x 
x = x,x = x;x 

무엇 난 후 것은 오른쪽에 그와 다르게 구문 분석하는 '='의 왼쪽에있는 X의의입니다. 그러나 '='부호의 오른쪽에 나타날 수있는 합법적 인 표현은 ';'때문에 왼쪽에있는 것보다 큽니다.

들소 (입력 파일이 test.y했다) 메시지를 인쇄합니다

test.y: conflicts: 1 reduce/reduce. 

이 문제를 해결 몇 가지 방법이 있어야합니다. C에서는 비슷한 상황이 발생합니다. 아래 프로그램은 아무런 오류없이 gcc를 통과합니다. 기호 -이 경우는 'PX'와 'X'는 그들이 '='의 왼쪽 또는 오른쪽으로 표시할지 여부에 따라 다르게 취급받을에서

int main(void) { 
    int x; 
    int *px; 
    x; 
    *px; 
    *px = x = 1; 
} 

.

Answer 1

%glr-parser을 사용 중이므로 축소/축소 충돌을 "수정"할 필요가 없습니다. Bison은 단지 하나만 있다고 알려주므로 문법이 모호 할 수 있으므로 %dprec 또는 %merge 지시어로 모호성 해결을 추가해야 할 수도 있습니다. 그러나 귀하의 경우 문법이 모호하지 않으므로 아무 것도 할 필요가 없습니다.

충돌은 오류가 아니며, 문법이 LALR (1)이 아니라는 것을 나타냅니다.

Answer 2

감소-감소 문법에 충돌 상황에서 오는 :

... = ... x , 

이 시점에서, 파서는 x는 fe 또는 fp 여부를 결정해야하고, 그것은 하나의 심볼 내다으로 알 수 없다 . 실제로 어떤 한정된 선견자로도 알 수 없다면 =, ; 또는 끝 부분을 만나지 않고도 그 지점 다음에 오는 x ,의 반복을 여러 번 가질 수 있습니다. 그 중 어떤 것이 대답을 나타낼 것입니다.

이것은 단일 기호 미리보기로 해결할 수있는 C 문제와 완전히 동일하지 않습니다. 그러나 C 예제는 SLR (1) 문법이 LALR (1) 문법보다 강력하지 않은 이유에 대한 고전적인 예입니다.이 문법은 용 책에서 그 목적으로 사용되었지만 유사하게 문제가되는 문법은 LALR (1) 및 LR (1);

def: param_spec return_spec ','; 

param_spec: type | name_list ':' type; 

return_spec: type | name ':' type; 

type: "id"; 
name: "id"; 
name_list: name | name ',' name_list; 

(. 들소 매뉴얼 (1) 문법하는 GLR 문법을 사용하는 것이 항상 가능하지만 LALR이 문제를 해결하는 방법을 설명합니다)

: 그것은 들소 매뉴얼 ( here)에서 찾을 수 있습니다

GLR 문법을 사용하지 않고 이러한 충돌을 해결하려면 파서가 조기에 결정을 내리지 않도록해야합니다.

예를 들어, lvalues와 rvalues간에 구문 적으로 구별하는 것이 일반적이며 일부 언어는 계속 그렇게합니다. 그러나 C와 C++은 그렇지 않습니다. 이것은 Lvalue로 작용할 수있는 함수의 정의를 허용하기 때문에 C++에서 매우 강력한 기능으로 밝혀졌습니다.

C에서는 문법을 조금 단순화하는 것으로 생각합니다. C 문법은 단항 연산자의 결과를 대입 연산자의 왼쪽에 나타낼 수 있지만 단항 연산자는 실제로는 lvalues ​​(*v, v[expr]) 및 r 값 (sizeof v, f(expr)). 문법은 두 가지 단항 연산자를 구별 할 수 있지만 실제로는 수정 가능 lvalues가 할당 연산자의 왼쪽에 나타날 수있는 실제 제한을 해결할 수 없습니다.

C++에서는 할당 연산자의 왼쪽에 임의의 표현식을 사용할 수 있습니다 (일부는 괄호로 묶어야 함). 결과적으로, 다음은 완전히 합법적이다 : 비 터미널 모두 유도의 동일한 세트를 생성하기 때문에 귀하의 경우에는

(predicate(x) ? *some_pointer : some_variable) = 42; 

, 당신은, 구문 p와 te을 대체하여 충돌을 해결할 수 있습니다. 왼쪽식이 오른쪽 식의 엄격한 하위 집합이라는 전체 문법의 경우가 아니면 예외는 아닙니다. 전체 문법에서는 3 가지 유형의 표현 (왼쪽, 오른쪽, 일반)으로 끝날 수 있으며, 이는 문법을 상당히 복잡하게 만들 수 있으며 의미 론적 분석을위한 해결책을 남기는 것이 더 쉬울 수도 있습니다 (심지어는 C++의 경우 놀라 울 정도로 유용함).