Как я могу заставить Бизона переключиться, чтобы разрешить конфликт?

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

Это моя полная грамматика: http://pastebin.com/yBHLSP0z
А это выходной файл Bison: http://pastebin.com/eAma3gWy
(извините, они на испанском, но я думаю, что они говорят сами за себя)

Дело в том, что я все еще получаю одну ошибку сдвига / уменьшения в состоянии 107 (я ее перевожу): 

state 107

31 factor: ID .
48 concatenacion: ID . OPERADOR_SUMA ID
49              | ID . OPERADOR_SUMA literal_string

OPERADOR_SUMA  shift and go to state 140
OPERADOR_SUMA  [reduce using rule 31 (factor)]
$default       reduce using rule 31 (factor)


Теперь состояние 107 вызывается из состояния 70:

estado 70

   45 asignacion: ID OPERADOR_ASIGNACION . concatenacion
   46           | ID OPERADOR_ASIGNACION . expresion
   47           | ID OPERADOR_ASIGNACION . literal_string

    OPERADOR_RESTA   desplazar e ir al estado 55
    PARENTESIS_ABRE  desplazar e ir al estado 56
    COMILLA          desplazar e ir al estado 67
    ID               desplazar e ir al estado 107

    expresion       ir al estado 108
    termino         ir al estado 61
    factor          ir al estado 62
    concatenacion   ir al estado 109
    literal_string  ir al estado 110
    literal_real    ir al estado 63
    literal_entero  ir al estado 64
    signo           ir al estado 65

Я думаю, что происходит (пожалуйста, поправьте меня, если я ошибаюсь), когда он находит такое правило для "asignacion":

asignacion: ID OPERADOR_ASIGNACION concatenacion | ID OPERADOR_ASIGNACION expresion

он видит, что из "выражения" он может получить токен идентификатора (выражение> терминатор> фактор> ID), создав ID OPERADOR_ASIGNACION ID:

expresion:  
        expresion OPERADOR_SUMA termino
        | expresion OPERADOR_RESTA termino
        | termino
        ;


termino:
        termino OPERADOR_MULTIPLICACION factor
        | termino OPERADOR_DIVISION factor
        | factor
        ;


factor:     
        ID
        | literal_entero
        | literal_real
        | PARENTESIS_ABRE expresion PARENTESIS_CIERRA
        ;

Теперь, когда он достигает конкатенации ID OPERADOR_ASIGNACION и просматривает правила конкатенации, он получает:

concatenacion:
        ID OPERADOR_SUMA ID 
        | ID OPERADOR_SUMA literal_string 
        | literal_string OPERADOR_SUMA ID 
        | literal_string OPERADOR_SUMA literal_string
        ;

Два из них начинаются с «ID». Таким образом, если выбрано какое-либо из этих двух правил, он переходит в состояние, в котором он может получить ID OPERADOR_ASIGNACION ID, только то, что с правилами «конкатенации» ему впоследствии необходимо найти токен «OPERADOR_SUMA». . Но я считаю, что он задыхается, как только видит, что из "конкатенации" и "выражения" можно сформировать выражение ID OPERADOR_ASIGNACION ID.
Если это не совсем то, что происходит, я хотел бы знать, в чем тогда проблема.
И, если я прав, где произошла ошибка, я действительно не знаю, как ее решить.
Пожалуйста, помогите :)

Спасибо!


grammar bison
person patr1c1a    schedule 13.11.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Проблема возникает из-за:

asignacion
    :   ID OPERADOR_ASIGNACION concatenacion
    |   ID OPERADOR_ASIGNACION expresion
    ;

и выбранные альтернативы:

expresion
    :   expresion OPERADOR_SUMA termino
    ;

termino
    :   factor
    ;

factor
    :   ID
    ;

concatenacion
    :   ID OPERADOR_SUMA ID
    ;

Это означает, что когда ваш парсер встречает:

x = y + z

он не может сказать, обрабатывает ли он первую или вторую альтернативу для asignacion.

Это легкая часть. Как исправить? Самым простым исправлением (если оно работает, что я не тестировал) было бы удалить показанное мной правило concatenacion, а в правиле expresion определить, когда вы имеете дело с concatenacion и expresion, поскольку они синтаксически идентичны:

ID OPERADOR_SIGNACION ID OPERADOR_SUM ID

Вы бы посмотрели на типы двух операндов expresion, и если бы они оба были строковыми типами, то вы бы предположили, что это был concatenacion, иначе expresion.

Тем не менее, вы можете просмотреть все правило concatenacion. Я думаю, вам нужно пропустить строки через правило factor, поэтому вы бы добавили еще одну альтернативу factor:

factor
   :   literal_string
   ;

Это будет означать, что вам придется отклонять буквальные строки в других правилах, поэтому требуется более тщательная проверка семантики. Альтернативой является введение отдельного оператора, отличного от +, для обозначения «конкатенации строк». SQL использует ||; некоторые языки использовали ,; вы можете вообще использовать другой токен, например @. Когда вы отойдете от +, у вас будет много вариантов. Можете ли вы даже просто использовать «два соседних строковых выражения означают операцию конкатенации» без оператора между ними?

Если ничего из этого не сработает, вернись ко мне.

person Jonathan Leffler    schedule 13.11.2013
comment
Спасибо! Ты гений! Я действительно не видел двусмысленности! Я просто изменил оператор конкатенации, и он волшебным образом сработал :) - person patr1c1a; 13.11.2013