сдвиг / уменьшение конфликтов YACC - PullRequest
Новая
       13

сдвиг / уменьшение конфликтов YACC

1 голос
/ 14 ноября 2009

см. Следующий код для yacc. если я уберу фактор производства: '!' expr, конфликт синтаксического анализа исчезает. что здесь происходит? 

%{
#include <stdio.h>
#include <ctype.h>

%}


%token TRUE
%token FALSE


%%
line    : line expr '\n'    {   printf("%d\n", $2); }
    | line '\n'
|
;
expr    :   expr "or" term  {   printf("expr : expr or term\n"); $$ = $1 | $3; }
|   term        {   printf("expr : term\n");     }
;
term    :   term "and" factor   {   printf("term : term and factor\n"); $$ = $1 & $3; }
|   factor      {   printf("term : factor\n");  }
;
factor  :   '(' expr ')'    {   printf("factor : (expr)\n"); $$ = $2; }
|   '!' expr    {   printf("factor : !expr\n"); $$ = !$2;   }
|   TRUE        {   printf("factor : TRUE\n");  }
|   FALSE       {   printf("factor : FALSE\n"); }
;
%%

#include "lex.yy.c"

int main(int argc, char** argv)
{
while (yyparse() == 0) {
    }

    return 0;
}

Ответы [ 2 ]

2 голосов
/ 14 ноября 2009

Мне кажется, что конфликт, вероятно, возникает, потому что когда анализатор видит «!», Он сталкивается с проблемами при переписывании «expr». Игнорируя другие произведения для «фактора», обратите особое внимание на эти два произведения: 

expr    : expr "or" term  { printf("expr : expr or term\n"); $$ = $1 | $3; }
        | term            { printf("expr : term\n"); }
        ;

factor  : '!' expr        { printf("factor : !expr\n"); $$ = !$2; }

Поскольку expr является рекурсивным, когда анализатор видит '!', Он знает, что отрицание применяется к следующему выражению, но если вы напишите "! TRUE OR TRUE", это отрицание применяется только к первому значению true или вся дизъюнкция?

РЕДАКТИРОВАТЬ: Другими словами, он не может решить, нужно ли ему сдвигать "или" или уменьшать "expr".

Установка параметра командной строки -v в yacc приведет к созданию файла .output, в котором есть все полезные свойства, включая диагностическую информацию для конфликтов сдвига / уменьшения. Он покажет вам все состояния DFA и места, где возникают конфликты, а иногда покажет, почему.

Размещение отрицаний в собственном производстве логически «между» «термином» и «фактором» должно помочь.

1 голос
/ 14 ноября 2009

Если вы измените factor: ! expr на factor: ! factor, конфликты исчезнут.

Анализируя только первый конфликт, проблема в том, что term может уменьшиться до expr или стать более сложным term. Без ! это решение может быть принято только с одним символом предвкушения.

Обратите внимание, что конфликты сдвига / уменьшения не обязательно являются ошибками. Конфликт разрешается путем смены, что вполне может быть тем, что вы хотите. Большинство реальных производственных грамматик содержат ряд конфликтов сдвига / уменьшения.

...