Уменьшить/уменьшить конфликт в грамматике

Question

Давайте представим, я хочу, чтобы иметь возможность анализировать значения, как это (каждая строка представляет собой отдельный пример):

x 
(x) 
((((x)))) 
x = x 
(((x))) = x 
(x) = ((x)) 

Я написал эту грамматику YACC:

%% 
Line: Binding | Expr 
Binding: Pattern '=' Expr 
Expr: Id | '(' Expr ')' 
Pattern: Id | '(' Pattern ')' 
Id: 'x' 

Но я получаю свёртка/свёртка конфликт:

$ bison example.y 
example.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr] 

Любой намек на то, как ее решить? Я использую GNU bison 3.0.2

Answer 1

Ваша грамматика не LR(k) для любого k. Поэтому вам либо нужно исправить грамматику, либо использовать GLR parser.

Пусть вход начинается с:

(((((((((((((x 

До здесь, нет никаких проблем, потому что каждый персонаж был перенесен на стек парсер.

Но что теперь? На следующем этапе x должен быть уменьшен, а внешний вид - ). Если в будущем есть =, x - Pattern. В противном случае это Expr.

Вы можете исправить грамматику:

• избавлении от Pattern и изменения Binding к Expr | Expr '=' Expr;

• избавившись от всех определений Expr и заменяя их Expr: Pattern

Вторая альтернатива, вероятно, лучше в l ong run, потому что вполне вероятно, что в полной грамматике, которую вы представляете (или развиваете), Pattern является подмножеством Expr, а не идентичным Expr. Факторинг Expr в единицу продукции для Pattern и альтернативы без шаблонов позволит вам проанализировать грамматику с помощью парсера LALR(1) (если остальная часть грамматики соответствует).

Или вы можете использовать грамматику GLR, как указано выше.

Answer 2

Уменьшение/уменьшение конфликтов часто означает, что в грамматике есть фундаментальная проблема.

Первым шагом в разрешении является получение выходного файла (bison -v example.y производит example.output). Bison 2.3 говорит (частично):

state 7 

    4 Expr: Id . 
    6 Pattern: Id . 

    '='  reduce using rule 6 (Pattern) 
    ')'  reduce using rule 4 (Expr) 
    ')'  [reduce using rule 6 (Pattern)] 
    $default reduce using rule 4 (Expr) 

Конфликт ясен; после того, как грамматика читает x (и уменьшает ее до Id) и ), она не знает, следует ли уменьшить выражение как Expr или как Pattern. Это создает проблему.

Я думаю, вы должны переписать грамматику без одного из Expr и Pattern:

%% 
Line: Binding | Expr 
Binding: Expr '=' Expr 
Expr: Id | '(' Expr ')' 
Id: 'x'