сдвиг зубров вместо уменьшения. С уменьшением / уменьшением ошибок - PullRequest
Новая
       42

сдвиг зубров вместо уменьшения. С уменьшением / уменьшением ошибок

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

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

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, прежде чем остальное вызывает 3 уменьшения / уменьшения. Причина в том, что он может уменьшить использование второго правила в IfExpr или уменьшить до exprLoop, где он допускает много новых строк между выражениями.

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

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

%%
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

Альтернатива .y и вывод. Вы можете видеть, что он смотрит вперед, видя \ n, и не знает, как уменьшить правило или продолжать. Я меняю порядок следования правил, чтобы получить разные результаты. Но он всегда ожидает \ n или всегда ожидает другое, поэтому одно правило всегда игнорируется. состояние 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)

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

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

test.y 

%{
#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;
}

test.y 

%{
#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 
{ }

Ответы [ 4 ]

5 голосов
/ 21 ноября 2009

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

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

%{
#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

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

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

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

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

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

0 голосов
/ 22 ноября 2009

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

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

требуется просмотр с двумя токенами после кодового блока, чтобы увидеть 'else' после новой строки, если это то, что есть. Вы можете избежать этого, дублируя необязательный NL в обоих правилах: 

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

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

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

0 голосов
/ 21 ноября 2009

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

...