Bison свёртка/свёртка Конфликт с Литейно и Expression Скобки

Question

Я строю грамматику в бизонов, и я сузили мой последний свёртка/свёртка ошибку в следующем тестовом случае:

%{ 
#include <stdio.h> 
#include <string.h> 

extern yydebug; 

void yyerror(const char *str) 
{ 
    fprintf(stderr, "Error: %s\n", str); 
} 

main() 
{ 
    yydebug = 1; 
    yyparse(); 
} 
%} 

%right '=' 
%precedence CAST 
%left '(' 

%token AUTO BOOL BYTE DOUBLE FLOAT INT LONG SHORT SIGNED STRING UNSIGNED VOID 

%token IDENTIFIER 

%start file 

%debug 

%% 

file 
    : %empty 
    | statement file 
    ; 

statement 
    : expression ';' 
    ; 

expression 
    : expression '=' expression 
    | '(' type ')' expression %prec CAST 
    | '(' expression ')' 
    | IDENTIFIER 
    ; 

type 
    : VOID 
    | AUTO 
    | BOOL 
    | BYTE 
    | SHORT 
    | INT 
    | LONG 
    | FLOAT 
    | DOUBLE 
    | SIGNED 
    | UNSIGNED 
    | STRING 
    | IDENTIFIER 
    ; 

Предположительно проблема заключается в том, что он не может определить разницу между типом и выражением, когда он видит (IDENTIFIER) в выражении.

Выход:

fail.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr] 
fail.y:64.5-14: warning: rule useless in parser due to conflicts [-Wother] 
    | IDENTIFIER 
    ^^^^^^^^^^ 

Что я могу сделать, чтобы исправить этот конфликт?

Answer 1

Если грамматика ограничивалась производством, показанным в ОП, было бы относительно легко устранить конфликт, поскольку грамматика недвусмысленная. Единственная проблема заключается в том, что это LR (2), а не LR (1).

Анализ в ОП полностью верен. Когда анализатор видит, например:

(identifier1 ·) 

(где · отмечает текущую точку, так что-токен является )), не представляется возможным, чтобы узнать, является ли это префикс

(identifier1 ·) ; 
(identifier1 ·) = ... 
(identifier1 ·) identifier2 
(identifier1 ·) (... 

в первых двух случаях, identifier1 должна быть уменьшена до expression, так что (expression) впоследствии может быть уменьшена до expression, тогда как в последних двух случаях, identifier1 должна быть уменьшена до type, чтобы впоследствии уменьшить (type) expression до expression. Если синтаксический анализатор может увидеть еще один маркер в будущем, решение может быть принято.

Поскольку для любой грамматики LR (k) существует грамматика LR (1), которая распознает один и тот же язык, очевидно, что решение; общий подход состоит в том, чтобы отложить сокращение до тех пор, пока не будет выделено одноточечное представление. Один из способов сделать это:

cast_or_expr : '(' IDENTIFIER ')' 
       ; 
cast   : cast_or_expr 
       | '(' type ')' 
       ; 
expr_except_id : cast_or_expr 
       | cast expression %prec CAST 
       | '(' expr_except_id ')' 
       | expression '=' expression 
       ; 
expression  : IDENTIFIER 
       | expr_except_id 
       ; 

(. Остальная часть грамматики одинакова для удаления IDENTIFIER из производств за type исключением)

Это прекрасно работает для грамматик, где никакого символа не может быть как префикс, так и инфиксный оператор (например, -) и где оператор не может быть удален (фактически, как при вызове функций). В частности, он не будет работать на C, потому что она оставит неясности:

(t) * a // product or cast? 
(t) (3) // function-call or cast? 

Таковы реальные неоднозначности в грамматике, которые могут быть решены только зная t, является ли имяТип или/имя функции переменной ,

«Обычное» решение для парсеров C состоит в том, чтобы разрешить двусмысленность, разделив таблицу символов между сканером и синтаксическим анализатором; поскольку объявления объявления псевдонима typedef должны появляться перед первым использованием символа в качестве имени в применимой области, его можно заранее узнать перед сканированием маркера, был ли объявлен токен с typedef. Точнее, если typedef не был замечен, можно предположить, что символ не является типом, хотя он может быть полностью необъявлен.

Используя грамматику GLR и семантический предикат, можно ограничить логику синтаксическому анализатору. Некоторые люди считают это более элегантным.