Сдвиг / уменьшение конфликтов с помощью Sablecc

Question

Я должен написать файл .grammar для MiniPython, используя Sablecc. Я получаю эти сдвиги / уменьшение конфликтов:

shift/reduce conflict in state [stack: TIf PTpower *] on TMult in {
     [ PMltp = * TMult PTopower Mltp ] (shift)
     [ PMlpt = * ] followed by TMult (reduce)
}

shift/reduce conflict in state [stack: TIf PTopower *] on TDiv in {
     [ PMltp = * TDiv PTopower Mltp ] (shift)
     [ PMltp = * ] followed by TDiv (reduce)
}

Некоторые из токенов:

id = letter (letter | digit)*;
digit = ['0' .. '9'];
letter = ['a' .. 'z']|['A' .. 'Z'];
pow = '**';
mult = '*';
div = '/';
plus = '+';
minus = '-';
assert = 'assert';
l_par = '(';
r_par = ')';
l_bra = '[';
r_bra = ']';

Часть моего файла .grammar:

expression = multiplication exprsn;

exprsn =   {addition} plus multiplication exprsn
         | {subtraction} minus multiplication exprsn
         | {empty};

topower = something tpwr;

tpwr =   {topower} pow something tpwr
       | {empty};

multiplication = topower mltp;

mltp =   {multiplication} mult topower mltp
       | {division} div topower mltp
       | {empty};

something =   {id} id
            | {parexp} l_par expression r_par
            | {fcall} functioncall
            | {value} value
            | {list} id l_bra expression r_bra
            | {other} l_bra value comval* r_bra
            | {assert} assert expression comexpr?;

comexpr = comma expression;

Это грамматика после того, как я попытался устранить левую рекурсию. Я заметил, что если я удаляю правило assert из производства something, я не получаю никаких конфликтов. Кроме того, удаление правил {empty} из правил exprsn, tpwr и mltp не дает мне никаких конфликтов, но я не думаю, что это правильный способ решения этой проблемы.

Буду признателен за любые советы.

ОБНОВЛЕНИЕ: Вот вся грамматика перед удалением левой рекурсии, как и было запрошено:

Package minipython;

Helpers
    digit = ['0' .. '9'];
    letter = ['a' .. 'z']|['A' .. 'Z']; 
    cr = 13; 
    lf = 10;
    all = [0..127]; 
    eol = lf | cr | cr lf ;
    not_eol = [all - [cr + lf]]; 

Tokens
    tab = 9;
    plus = '+';
    dot = '.';
    pow = '**';
    minus = '-';
    mult = '*';
    div = '/';
    eq = '=';
    minuseq = '-=';
    diveq = '/=';
    exclam = '!';
    def = 'def';
    equal = '==';
    nequal = '!=';
    l_par = '(';
    r_par = ')';
    l_bra = '[';
    r_bra = ']';
    comma= ',';
    qmark = '?';
    gqmark = ';';
    assert = 'assert';
    if = 'if';
    while = 'while';
    for = 'for';
    in = 'in';
    print = 'print';
    return = 'return';
    importkn = 'import';
    as = 'as';
    from = 'from';
    less = '<';
    great = '>';
    true = 'true';
    semi = ':';
    false = 'false';
    quote = '"';
    blank = (' ' | lf | cr);
    line_comment = '#' not_eol* eol; 
    number = digit+ | (digit+ '.' digit+);
    id = letter (letter | digit)*;
    string = '"'not_eol* '"';
    cstring = ''' letter ''';

Ignored Tokens
    blank, line_comment;

Productions
program = commands*;

commands =   {stmt} statement
           | {func} function;

function = def id l_par argument? r_par semi statement;

argument = id eqval? ceidv*;

eqval = eq value;

ceidv = comma id eqval?;

statement =   {if} tab* if comparison semi statement
            | {while} tab* while comparison semi statement
            | {for} tab* for [id1]:id in [id2]:id semi statement
            | {return} tab* return expression
            | {print} tab* print expression comexpr*
            | {assign} tab* id eq expression
            | {minassign} tab* id minuseq expression
            | {divassign} tab* id diveq expression
            | {list} tab* id l_bra [ex1]:expression r_bra eq [ex2]:expression
            | {fcall} tab* functioncall
            | {import} import;

comexpr = comma expression;

expression =   {multiplication} multiplication
             | {addition} expression plus multiplication
             | {subtraction} expression minus multiplication;

topower =   {smth} something
          | {power} topower pow something;

something =   {id} id
            | {parexp} l_par expression r_par
            | {fcall} functioncall
            | {value} value
            | {list} id l_bra expression r_bra
            | {assert} assert expression comexpr?
            | {other} l_bra value comval* r_bra;

comval = comma value;   

multiplication =   {power} topower
                 | {multiplication} multiplication mult topower
                 | {division} multiplication div topower;

import =   {import} importkn module asid? comod*
         | {from} from module importkn id asid? comid*;

asid = as id;

comod = comma module asid?;

comid = comma id asid?;

module = idot* id;

idot = id dot;

comparison =   {true} true
             | {false} false
             | {greater} [ex1]:expression great [ex2]:expression
             | {lesser} [ex1]:expression less [ex2]:expression
             | {equals} [ex1]:expression equal [ex2]:expression
             | {nequals} [ex1]:expression nequal [ex2]:expression;

functioncall = id l_par arglist? r_par;

arglist = expression comexpr*;

value =   {fcall} id dot functioncall
        | {numb} number
        | {str} string
        | {cstr} cstring;

Конфликт сдвига / уменьшения теперь:

shift/reduce conflict in state [stack: TIf PTopower *] on TPow in {
     [ PMultiplication - PTopower * ] followed by TPow (reduce),
     [ PTopower = PTopower * TPow PSomething ] (shift)
}

Answer 1

(Примечание: этот ответ был взят из исходной грамматики, а не из попытки удалить левую рекурсию, что имеет дополнительные проблемы. Нет необходимости удалять левую рекурсию из грамматики, предоставляемой LALR (1 ) генератор парсеров типа SableCC.)

Действительно, основной проблемой является производство:

something = {assert} assert expression comexpr?

Эта постановка любопытна, отчасти потому, что имя нетерминала («что-то») не дает никакого намека на то, что это такое, а главным образом потому, что обычно можно ожидать, что assert expression будет утверждением, а не частью выражение. И something явно получено из expression:

expression = multiplication
multiplication = topower
topower = something

Но производство assert заканчивается expression. Это приводит к двусмысленности, так как

assert 4 + 3

может быть проанализирован как: (некоторые шаги для краткости опущены):

expression = expression     plus    multiplication
                |             |           |
                V             |           |
            something         |           |
                |             |           |
                V             |           |
          assert expression   |           |
             |        |       |           |
             |        V       V           V
          assert      4       +           3

Или, более естественно, как:

expression =          something
                          |
                          V
             assert                expression
                |                      |
                |                      V
                |          expression plus multiplication
                |               |       |        |
                |               V       V        V
             assert             4       +        3

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

Не видя определения языка, который вы пытаетесь проанализировать, я не могу дать конкретного предложения о том, как это исправить, но я бы хотел сделать assert оператором и переименовать something к чему-то более описательному («термин» встречается часто, хотя я обычно использую «атом»).