Bison에서 단항 마이너스에 우선 순위를 사용하면 시프트/축소 충돌이 해결되지 않습니다.

Question

단항 마이너스 피연산자를 사용하는 아주 간단한 문법을 ​​고안하고 있습니다. 그러나 나는 shift/reduce 충돌을 얻는다. Bison 매뉴얼과 다른 곳에서는 새로운 토큰을 정의하고 이진 빼기 피연산자보다 더 높은 우선 순위를 부여한 다음 규칙에 "% prec TOKEN"을 사용하는 것이 좋습니다.

나는 해봤지만 여전히 경고를 받는다. 왜?

나는 바이슨 (GNU Bison) 2.4.1을 사용하고 있습니다. 문법은 다음과 같습니다.

%{ 
#include <string> 
extern "C" int yylex(void); 
%} 

%union { 
    std::string token; 
} 

%token <token> T_IDENTIFIER T_NUMBER 
%token T_EQUAL T_LPAREN T_RPAREN 

%right T_EQUAL 
%left T_PLUS T_MINUS 
%left T_MUL T_DIV 
%left UNARY 

%start program 

%% 

program : statements expr 
; 

statements : '\n' 
      | statements line 
; 

line : assignment 
    | expr 
; 

assignment : T_IDENTIFIER T_EQUAL expr 
; 

expr : T_NUMBER 
    | T_IDENTIFIER 
    | expr T_PLUS expr 
    | expr T_MINUS expr 
    | expr T_MUL expr 
    | expr T_DIV expr 
    | T_MINUS expr %prec UNARY 
    | T_LPAREN expr T_RPAREN 
; 

Answer 1

%prec :

program : statements expr 
; 

규칙은 같은 것을해야한다. 그것은 Bison에게 - a * b이있는 상황에서 - (a * b) 대신 (- a) * b으로 구문 분석하려고한다고 말합니다. 즉, T_MUL 규칙보다 UNARY 규칙을 선호합니다. 두 경우 모두 UNARY 규칙이 결국 적용될 것이라는 확신을 가질 수 있으며 입력이 단항 인수로 축소되는 순서에 관한 질문 일뿐입니다.

문법에 따라 크게 다릅니다. line 비 - 터미널의 모든 시퀀스는 sequence을 구성 할 것이고 line 비단 호가 끝 부분에서 끝나야한다고 말할 것도 없습니다. 실제로 표현식은 line 일 수 있습니다. 따라서 여기에 기본적으로 a - b을 파싱하는 두 가지 방법이 있습니다. 이진 빼기가있는 한 줄 또는 두 줄로, 두 번째 줄은 단항 마이너스로 시작하십시오. 이 규칙 중 어느 것이 적용될 지 결정할 것이 없으므로 규칙 기반 우선 순위는 아직 여기에서 작동하지 않습니다.

귀하의 솔루션은 모든 line에 실제로 끝자리 기호 또는 줄 끝 기호가 오는 것을 요구하여 줄 분리를 수정하고 있습니다.

실제로 문법에 따라 줄 끝과 관련하여 표시되는 경우 T_MINUS으로 시작할 수없고 시작할 수없는 두 개의 별도 비 터미널이 필요합니다. 나무 위로 이것을 전파해야합니다 : 첫 번째 line은 단항 마이너스로 시작할 수 있지만 후속 단락은 안됩니다. 괄호 안에는 마이너스로 시작하는 것이 좋습니다.

Answer 2

expr 규칙은 % prec UNARY없이 사용 가능합니다. 전환/감소 충돌은 다음 규칙에서 발생합니다.

statements : '\n' 
      | statements line 
; 

규칙은 생각과 다릅니다. 예를 들어, 당신은 쓸 수 있습니다 :

a + b c + d 

나는이 유효한 입력 있어야하지 생각합니다.

그러나 또한 프로그램의 규칙은 매우 제정신되지 않습니다 : 당신이 여기에 희망을 수있는만큼하지 않습니다

program: lines; 

lines: line | lines line; 

line: statement "\n" | "\n"; 

statement: assignment | expr;