Làm cách nào để sửa YACC shift/giảm xung đột từ toán tử tăng sau?

Question

Tôi đang viết một ngữ pháp trong YACC (thực sự là Bison), và tôi đang gặp vấn đề về ca/​​giảm. Nó kết quả từ bao gồm các toán tử tăng và tăng hậu tố. Dưới đây là một phiên bản cắt giảm của ngữ pháp:

%token NUMBER ID INC DEC 

%left  '+' '-' 
%left  '*' '/' 
%right  PREINC 
%left  POSTINC 

%% 

expr: NUMBER 
|  ID 
|  expr '+' expr 
|  expr '-' expr 
|  expr '*' expr 
|  expr '/' expr 
|  INC expr %prec PREINC 
|  DEC expr %prec PREINC 
|  expr INC %prec POSTINC 
|  expr DEC %prec POSTINC 
|  '(' expr ')' 
; 

%% 

Bison nói với tôi có 12 ca/​​giảm xung đột, nhưng nếu tôi nhận xét ra các dòng cho increment postfix và sụt lần, nó hoạt động tốt. Có ai biết cách khắc phục xung đột này không? Tại thời điểm này, tôi đang xem xét việc chuyển sang trình tạo phân tích cú pháp LL (k), điều này làm cho nó dễ dàng hơn nhiều, nhưng các ngữ pháp LALR luôn có vẻ tự nhiên hơn nhiều khi viết. Tôi cũng đang xem xét GLR, nhưng tôi không biết về bất kỳ trình tạo phân tích cú pháp C/C++ GLR nào tốt.

Answer 1

Bison/Yacc có thể tạo trình phân tích cú pháp GLR nếu bạn chỉ định %glr-parser trong phần tùy chọn.

Answer 2

Tôi muốn xác định thêm mục. Bạn không nên cần% left,% right,% prec stuff.

simple_expr: NUMBER 
| INC simple_expr 
| DEC simple_expr 
| '(' expr ')' 
; 

term: simple_expr 
| term '*' simple_expr 
| term '/' simple_expr 
; 

expr: term 
| expr '+' term 
| expr '-' term 
; 

Phát xung quanh với phương pháp này.

Answer 3

Hãy thử điều này:

%token NUMBER ID INC DEC 

%left  '+' '-' 
%left  '*' '/' 
%nonassoc '++' '--' 
%left  '(' 
%% 

expr: NUMBER 
|  ID 
|  expr '+' expr 
|  expr '-' expr 
|  expr '*' expr 
|  expr '/' expr 
|  '++' expr 
|  '--' expr 
|  expr '++' 
|  expr '--' 
|  '(' expr ')' 
; 

%% 

Điều quan trọng là phải tuyên bố khai thác postfix như phi kết. Nếu không, bạn sẽ có thể

++var++-- 

Các ngoặc cũng cần phải nhận được một ưu tiên để giảm thiểu sự thay đổi/giảm cảnh báo

Answer 4

preincrement và postincrement nhà khai thác có nonassoc để xác định rằng trong phần ưu tiên và trong các quy tắc làm các ưu tiên của các toán tử cao bằng cách sử dụng %prec

Answer 5

vấn đề cơ bản này là bạn không có một ưu tiên cho INC và DEC thẻ, vì vậy nó không biết làm thế nào để giải quyết sự mơ hồ liên quan đến một lookahead của INC hoặc DEC. Nếu bạn thêm

%right INC DEC 

vào cuối danh sách ưu tiên (bạn muốn unaries là ưu tiên cao hơn và postfix cao hơn tiền tố), nó sẽ sửa chữa nó, và bạn thậm chí có thể thoát khỏi tất cả những thứ PREINC/POSTINC , vì nó không liên quan.