Бизон уменьшить/уменьшить конфликт

Я получаю конфликт уменьшения/уменьшения в следующей грамматике (отрывок)

 declaration : type list_of_id

        list_of_id : ID                             
                   | list_of_id ',' ID              
                   ;

        type : PATH   
             | SCAL 
             ;

        assignment : ID ":=" param
                   | ID ":=" expr

        param :  point relative_param
              | ID relative_param   

        point : '(' expr ',' expr ')'
              | '(' expr  ':' expr ')'

         relative_param : /* empty rule */ 
                        | "--" '+' param
                        | "--" CYCLE relative_param     
                        | "--" param 

        expr : NB                          
             | ID                         ``                               
             | expr '+' expr              
             | expr '-' expr             
             | expr '*' expr                   
             | expr '/' expr                   
             | '(' expr ')'

Я вижу, что когда ввод: foo := bar , есть два возможных вывода:

  1. назначение-> ID ":=" параметр и параметр -> ID
  2. присваивание-> ID ":=" expr и expr-> ID

Я дважды использовал ID в грамматике, потому что переменная может иметь тип path или scal. Как я могу устранить этот конфликт без использования опции glr-parser?

Я попытался разделить идентификатор на две возможности: ID_PATH и ID_SCAL и изменить параметры производства и expr на:

param : point relative_param
        | ID_PATH relative_param
        ;

  expr : NB
       | ID_SCAL
       | expr '+' expr
       | expr '-' expr
       | expr '/' expr
       | '(' expr ')'

но в этом случае, как я могу отличить эти два (ID_SCAL и ID_PATH) в лексере?


context-free-grammar bison
person salmane    schedule 20.04.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Что ж, как вы уже поняли, проблема в том, что ваша грамматика неоднозначна — у нее есть два разных способа разбора входных данных, таких как Foo := Bar. Итак, первое, что вам нужно решить, это то, что это должно быть? а откуда ты знаешь? Если бы вы (человек, читающий код) увидели бы это на языке, который вы пытаетесь разобрать, как бы вы узнали, является ли Bar выражением или параметром без относительного_парама?

Если это зависит от какого-то предыдущего объявления Bar, то именно так вам нужно это решить. Вам нужно сохранить информацию о ранее просмотренных объявлениях в таблице символов, а затем использовать эту таблицу символов в лексере для поиска идентификаторов, которые они распознают, чтобы решить, должен ли лексер возвращать ID_PATH или ID_SCAL.

Если это зависит от предыдущего объявления Foo, вы делаете что-то подобное, но вам нужно изменить грамматику, чтобы она выглядела примерно так:

assignment: ID_PATH ":=" param
          | ID_SCAL ":=" expr
          ;
person Chris Dodd    schedule 20.04.2013
comment
На самом деле назначение: foO := bar зависит от предыдущего объявления бара. Спасибо! @ChisDodd - person salmane; 20.04.2013