Перевод if then else в грамматике компилятора

...
IF LP assignment-expression RP marker statement {
    backpatch($3.tlist,$5.instr);
    $$.nextList = mergeList($3.flist,$6.nextList);
}
|IF LP assignment-expression RP marker statement ELSE Next statement {
    backpatch($3.tlist,$5.instr);
    backpatch($3.flist,$8.instr);
    YYSTYPE::BackpatchList *temp = mergeList($6.nextList,$8.nextList);
    $$.nextList = mergeList(temp,$9.nextList);
} 
...

Выражение присваивания - это любое выражение присваивания, которое возможно с помощью операторов C =, +=, -=, *=, /=.

LP = (
RP = )

marker и Next являются EMPTY правилом

Проблема с приведенным выше правилом грамматики и его реализацией заключается в том, что оно не может сгенерировать правильный код, если выражение равно

bool a;
if(a){
  printf("hi");
}
else{
  prinf("die");
}

Ожидается, что выражение-присваивание должно содержать relop или OR или AND до generate correct code. Поскольку в этом случае мы делаем сравнение для relop, тот же случай применяется к OR и AND.

Но поскольку в приведенном выше коде ничего из этого не содержится, поэтому он не может сгенерировать правильный код. Правильный код можно сгенерировать, используя следующее правило, но это приводит к two reduce-reduce conflict.

  ...
  IF LP assignment-expression {
     if($3.flist == NULL && $3.tlist == NULL)
       ...
      } RP marker statement {
            ...
  }
  |IF LP assignment-expression{
    if($3.flist == NULL && $3.tlist == NULL)
    ...
    } RP marker statement ELSE Next statement {
      ...
  } 
  ...

Какую модификацию нужно внести в правило грамматики, чтобы оно работало должным образом?

Я попробовал IF ELSE грамматическое правило отсюда, а также из книги дракона но не может это решить. Полную грамматику можно найти здесь Github


c compiler-construction lr lex bison
person sonus21    schedule 09.04.2015    source источник
comment
Я использовал flex bison несколько лет назад и помню такие ситуации. Я думаю, что решение состоит в том, чтобы использовать начальные условия в лексере для введения различных правил. Синтаксис с моим старым флекс-бизоном немного отличается. Надеюсь, это поможет.   -  person Mel Viso Martinez    schedule 09.04.2015

Ответы (2)


arrow_upward
1
arrow_downward

Чтобы вставить действие среднего правила, вам нужно использовать левый фактор; в противном случае синтаксический анализатор, созданный bison, не сможет решить, какой из двух MRA уменьшить. (Хотя они предположительно идентичны, бизон этого не знает.)

if_prefix: "if" '(' expression ')' { $$ = $3; /* Normalize the flist */ }
if: if_prefix marker statement { ... }
  | if_prefix marker statement "else" Next statement { ... }

(Вы можете оставить фактор по-другому, это всего лишь одно предложение.)

person rici    schedule 09.04.2015

arrow_upward
1
arrow_downward

Похоже, в вашей грамматике неверное определение expression.

Выражение присваивания - это только одно из многих нетерминалов, которые должны иметь возможность сводиться к выражению. Для конструкции if / then / else вам обычно необходимо разрешить любое выражение между скобками. Ваш первый пример, как вы указываете, вполне допустим на C, но не содержит присваивания.

В вашей грамматике есть такая строка:

/*Expression list**/
expression:
assignment-expression{}
|expression COMMA assignment-expression{}
;

Однако выражение должно иметь больше, чем выражения присваивания. Не будучи хорошо знаком с yacc / bison, я предполагаю, что вам нужно изменить это на что-то вроде следующего:

/*Expression **/
expression:
assignment-expression{}
|logical-OR-expression{}
|logical-AND-expression{}
|inclusive-OR-expression{}
|exclusive-OR-expression{}
|inclusive-AND-expression{}
|equality-expression{}
|relational-expression{}
|additive-expression{}
|multiplicative-expression{}
|exponentiation-expression{}
|unary-expression{}
|postfix-expression{}
|primary-expression{}
|expression COMMA expression{}
;

Я не могу подтвердить, что это сработает для вас, и это может быть несовершенно, но, надеюсь, вы поняли идею. Каждый другой тип выражения должен иметь возможность сводиться к выражению. У вас есть что-то очень похожее на statement ранее в вашей грамматике, так что, надеюсь, это должно иметь смысл.

Было бы полезно прочитать или просмотреть несколько руководств по как работают грамматики LR.

person seanmk    schedule 09.04.2015
comment
Я взял грамматику из программирования C Денниса Ричи. - person sonus21; 09.04.2015
comment
Однако передо мной нет K&R. Если вы хотите получить более подробный ответ, можете ли вы дополнить свой вопрос более подходящей грамматикой? Например, все правила, которые сводятся к assignment_expression? - person seanmk; 09.04.2015
comment
Правильно, мне не нужно видеть всю грамматику. Давайте начнем с правил, в которых в левой части стоит assignment_expression. - person seanmk; 09.04.2015
comment
github.com/sonun/. - person sonus21; 09.04.2015
comment
Нет ничего особенного в вашем новом грамматическом правиле для expression, если вы посмотрите на выражение присваивания из-за правила, которое автоматически получает все эти выражения. - person sonus21; 10.04.2015
comment
@sonukumar Извините, но я не вижу этого в грамматике. Возможно, я просто не знаком с точным синтаксисом Bison, поэтому, возможно, я ищу не в том месте. - person seanmk; 10.04.2015
comment
Что происходит E->E+T | T ; T-> ID | ( E ) | NUM ; В этом случае E автоматические ворота ID и NUM и выражения в скобках. Подобно этому, если вы внимательно посмотрите на правило грамматики, вы обнаружите, что оно содержит все упомянутые вами правила грамматики. - person sonus21; 10.04.2015