bison shift вместо сокращения. С уменьшением/уменьшением ошибок

На моем языке я могу написать

a = 1

b = 2
if true { } else { }
if true { } **Here is the problem**
else {}

Мой грамматик не поддерживает символы новой строки между операторами. else можно использовать только с if. Когда я добавляю optionNL в свое правило

IfExpr:
  IF rval optionalNL codeBlock optionalNL ELSE codeBlock
| IF rval optionalNL codeBlock

Необязательный NL перед else вызывает 3 сокращения/уменьшения. Причина в том, что он может сократить использование второго правила в IfExpr или сократить до exprLoop, где он допускает много новых строк между выражениями.

Независимо от того, что я делаю (я пытался написать %prec перед optionalNL и ELSE), он всегда сводится к exprLoop, в котором случается бизон, чтобы дать мне синтаксическую ошибку в другом. Как мне сказать бизону, чтобы он сместился в этот момент (до optionNL еще) вместо уменьшения? (для exprLoop, вызывающего else ошибку).

пример файла для тестирования

%%
program:
      exprLoop;
exprLoop:
      exprLoop2 expr
    | exprLoop2
exprLoop2:
    | exprLoop2 expr EOS
    | exprLoop2 EOS
    ;   
expr:
      'i' Var optEOS '{' '}'
    | 'i' Var optEOS '{' '}' optEOS 'e' '{' '}'
EOS: '\n'   ;
Var: 'v';
optEOS: | optEOS EOS

%%

//this can be added to the lex file
[iev]                   { return *yytext; }

y.output http://www.pastie.org/707448

Альтернативный .у и вывод. Вы можете видеть, что он смотрит вперед, видит \n и не знает, уменьшить ли правило или продолжить. Я меняю порядок правил, чтобы получить разные результаты. Но он либо всегда ожидает \n, либо всегда ожидает else, поэтому одно правило всегда игнорируется. состояние 15

    9 expr: 'i' Var optEOS '{' '}' .  [$end, '\n']
   10     | 'i' Var optEOS '{' '}' . 'e' '{' '}'
   11     | 'i' Var optEOS '{' '}' . '\n' 'e' '{' '}'

    'e'   shift, and go to state 16
    '\n'  shift, and go to state 17

    '\n'      [reduce using rule 9 (expr)]
    $default  reduce using rule 9 (expr)

Спасибо Кинопико за его ответ

Я изменил его код, чтобы не было конфликтов, а затем работал над тем, чтобы сделать его более гибким. Вот мои файлы

тест.у

%{
#include <stdio.h>
%}

%%

program: expr                                   { printf ("First expr\n"); }
       | program expr                           { printf ("Another expr\n"); }

expr:
      if optEOS                                 { printf ("IF only\n"); }
    | if optEOS else optEOS                     { printf ("IF/ELSE\n"); }

if:   'i' Var optEOS '{' optEOS '}'
else: 'e' optEOS     '{' optEOS '}'
EOS:  '\n'
Var:  'v'
optEOS:
          | EOS optEOS                          { ;}//printf ("many EOS\n"); }
%%

int main(int argc, char **argv)
{
    int i;

    printf("starting\n");

    if(argc < 2) {
        printf("Reading from stdin\n");
        yyparse();
        return 0;
    }
    for(i = 1; i < argc; i++) {
        FILE *f;
        char fn[260];
        sprintf(fn, "./%s", argv[i]);
        f = fopen(fn, "r");
        if(!f) {
            perror(argv[i]);
            return (1);
        }
        printf("Running '%s'\n", argv[i]);
        yyrestart(f);
        yyparse();
        fclose(f);
        printf("done\n");
    }
    return 0;
}

тест.у

%{
#include <stdio.h>
#include "y.tab.h"
%}    
%option noyywrap
%%
[ \t]               { }
\n                  { return *yytext; }
.                   { return *yytext; }
%%
int yyerror ()
{
    printf ("syntax error\n");
    exit (1);
}

тестовый файл, который автоматически запускался после компиляции

i v { } 
i v { }
e { }
i v { }

e { }
i v { 
} e {
 }
i v { }


i v { } i v { } e { }

i v
{ } i v { } e { } i v { } e { 
} i v {
 } e 
{ }

person Community    schedule 19.11.2009    source источник
comment
Вам нужно показать грамматику для exprLoop. Постарайтесь сократить до небольшой полной грамматики, если это возможно.   -  person    schedule 20.11.2009
comment
Я уверен, что человеку, который знает ответ, он не нужен, но я все равно напишу его для целей тестирования.   -  person    schedule 20.11.2009
comment
Вы имели в виду, что в вашем примере кода: не заканчивать exprLoop, expr и optEOS 2. иметь пустую строку в качестве первого правила для exprLoop2?   -  person Simeon Pilgrim    schedule 21.11.2009


Ответы (4)


Я не очень хорошо понимаю вашу проблему, поэтому я начал с нуля:

Это моя грамматика:

%{
#include <stdio.h>
%}

%%

program: expr                                   { printf ("First expr\n") }
       | program EOS                            { printf ("Ate an EOS\n") }
       | program expr                           { printf ("Another expr\n") }

expr:
      ifeos                                     { printf ("IF only\n"); }
    | ifelse                                    { printf ("IF/ELSE\n"); }

ifelse: ifeos else
      | if else

ifeos: if EOS
     | ifeos EOS

if:   'i' Var optEOS '{' '}'
else: 'e' '{' '}'
EOS:  '\n'
Var:  'v'
optEOS:
          | EOS optEOS                          { printf ("many EOS\n") }
%%

Вот лексер:

%{
#include <stdio.h>
#include "1763243.tab.h"
%}    
%option noyywrap
%%
[iev\{\}\n]                  { return *yytext; }
\x20                         { }
%%
int yyerror ()
{
    printf ("syntax error\n");
    exit (1);
}
int main () {
    yyparse ();
}

Вот некоторый тестовый ввод:

i v { } 
i v { }
e { }
i v { }

e { }
i v { } e { }
i v { }

Вот результат:

IF only
First expr
IF/ELSE
Another expr
Ate an EOS
IF/ELSE
Another expr
Ate an EOS
IF/ELSE
Another expr
Ate an EOS
IF only
Another expr

Остается конфликт сдвига/уменьшения.

person Community    schedule 21.11.2009
comment
Используя ваш код, я все еще получаю конфликты. Вы уверены, что не получите ни одного? Какую версию ты используешь? я использую 2.3 (бизон -V) - person ; 21.11.2009
comment
Есть один сдвиг, уменьшающий конфликт, но проблема, которую вы описываете, не возникает. - person ; 22.11.2009
comment
попробуйте написать только i v { } или i v { } i v { } e { }, так как e не игнорируется, это может ожидаться каждый раз. - person ; 22.11.2009
comment
i v { } i v { } e { } не разрешено, возможно, вам нужен \n там. - person ; 22.11.2009
comment
Я вижу, что ты сделал. Вместо того, чтобы принудительно использовать EOS между выражениями, вы меняете его так, чтобы EOS находился в конце выражения и был фиктивным для нескольких пустых строк. Я устранил ваш конфликт, проверьте мой вопрос на наличие изменений. Спасибо! я не смог бы решить это без тебя! - person ; 22.11.2009
comment
я исправил грамматику, заставив else работать с }[\n\t ]*else и создав разделы для вещей, которые заканчиваются на }, и вещей, которые требуют ; или новой строки, сработало очень хорошо. - person ; 28.12.2009

Согласно «Lex & Yacc», разрешение по умолчанию для сокращения/уменьшения является первым определенным правилом, поэтому, как вы говорите, exprLoop выигрывает, поэтому я предполагаю, что оно определено первым.

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

Дальнейшее чтение (стр. 237) показывает, что вам нужно больше смотреть вперед, что недоступно для стандартного yacc/bison. Но у Bison есть GLR режим, который может быть полезен.

person Simeon Pilgrim    schedule 21.11.2009
comment
Я сдался, я собираюсь использовать режим GLR. Я попытался изменить порядок, как вы предложили, но вы правы, это не решило проблему. Вместо того, чтобы всегда предполагать, что ничего другого нет, он видит \n и всегда смещается и предполагает, что еще есть. Написание %glr-parser полностью устраняет проблему. Мой тест прошел без проблем. Я собираюсь удалить его и продолжить кодирование, пока все не станет стабильным. Затем измените его на анализатор glr и разрешите определенные конфликты. - person ; 21.11.2009

Одна вещь, которую вы можете сделать, это полностью разобрать новые строки, используя для них правило lex. Таким образом, не имеет значения, где находятся новые строки. Это то, что делает C/C++... новые строки в значительной степени игнорируются.

person Polaris878    schedule 21.11.2009
comment
новые строки отдельные операторы. Так что они мне нужны. Я думаю ';' тоже должны отделиться. - person ; 21.11.2009

Проблема в том, что:

IfExpr:
  IF rval optionalNL codeBlock optionalNL ELSE codeBlock
| IF rval optionalNL codeBlock

требует просмотра с двумя токенами после кодового блока, чтобы увидеть «еще» после новой строки, если это то, что есть. Этого можно избежать, продублировав optionNL в обоих правилах if:

IfExpr:
  IF rval optionalNL codeBlock optionalNL ELSE codeBlock
| IF rval optionalNL codeBlock optionalNL

Теперь синтаксическому анализатору не нужно выбирать между двумя правилами до тех пор, пока не будет проанализирован необязательный NL, что позволит ему увидеть ELSE (или его отсутствие) в предварительном просмотре с одним токеном.

Потенциальным недостатком здесь является то, что второе правило if (но не первое) теперь будет поглощать все завершающие символы новой строки, поэтому, если ваша грамматика для программ требует новой строки между каждым оператором, она не найдет ее после ifs без else и это уже было потребляется.

person Chris Dodd    schedule 22.11.2009
comment
на самом деле, если вы это сделаете, вы получите ту же ошибку. Вот мой y.output после внесения изменений в исходный .y выше pastie.org/710270 my optionNL на самом деле 0 или больше. Он задыхается, увидев 1 \n и увидев \n, он не знает, что нужно свести к exprLoop2 или к else/ - person ; 22.11.2009