Неожиданное поведение сгенерированного парсера бизонов - PullRequest
Новая
       52

Неожиданное поведение сгенерированного парсера бизонов

2 голосов
/ 29 мая 2019

Я создал парсер через Flex / Bison, который неожиданно завершился неудачей при разборе.Вот упрощенный пример, который показывает проблему

Lexer.l: 

%{
#include "Parser.h"
%}
%option noyywrap nodefault

%%
"foo"               {   return FOO;                          }
"bar"               {   return BAR;                          }
"("                 {   return OP;                           }
")"                 {   return CP;                           }
[ \t\n]+            {   /*    DO NOTHING  */                 }
.                   {   YY_FATAL_ERROR("unknown character"); }
%%

И Parser.y (с включенной трассировкой и многословием): 

%{
#include <stdio.h>
int yylex();
void yyerror (char const *s);
%}

%debug
%verbose
%error-verbose
%token FOO BAR OP CP

%%
program_expr :   foo_expr bar_expr   {}
;
foo_expr :   /*  NOTHING  */  {}
    |   OP FOO CP           {}
;
bar_expr :   /*  NOTHING  */  {}
    |   OP BAR CP           {}
;
%%

int main(int argc, char** argv)
{
    yydebug = 1;
    yyparse();
    return 0;
}

void yyerror (char const *s) {  fprintf(stderr, "%s\n", s); }

Но сгенерированный парсерпотерпит неудачу, если я укажу ввод типа (bar) - дерево разбора в этом случае должно содержать выражение foo, которое является пустым.Он сообщает:

Начальный анализ

Состояние входа 0

Чтение токена: Следующий токен является токеном OP ()

Сдвиг токена OP ()

Состояние входа 1

Чтение токена: следующий токен - токен BAR ()

синтаксическая ошибка, непредвиденный BAR, ожидание FOO

Ошибка: выталкиваниеТокен OP ()

Стек сейчас 0

Очистка: отбрасывание лексемы с меткой упреждения BAR ()

Стек сейчас 0

Вот фрагмент текстаиз сгенерированного описания shift/reduce automata: 

state 0
    0 $accept: . program_expr $end
    OP  shift, and go to state 1
    OP        [reduce using rule 2 (foo_expr)]
    $default  reduce using rule 2 (foo_expr)
    program_expr  go to state 2
    foo_expr      go to state 3


state 1
    3 foo_expr: OP . FOO CP
    FOO  shift, and go to state 4
state 2
    0 $accept: program_expr . $end
    $end  shift, and go to state 5
state 3
    1 program_expr: foo_expr . bar_expr
    OP  shift, and go to state 6
    $default  reduce using rule 4 (bar_expr)
    bar_expr  go to state 7

Но я не могу понять значение / синтаксис таких состояний.В чем проблема с моей грамматикой / парсером?

Ответы [ 2 ]

3 голосов
/ 29 мая 2019

Если вы хотите принять только (bar) в качестве ввода, вы можете использовать следующее: 

program_expr :   foo_expr bar_expr   {}
    |            bar_expr            {}
;

вместо этого: 

program_expr :   foo_expr bar_expr   {}
;

Тестовый вывод: 

> echo "(bar)" | ./Parser 
Starting parse
Entering state 0
Reading a token: Next token is token OP ()
Shifting token OP ()
Entering state 1
Reading a token: Next token is token BAR ()
Shifting token BAR ()
Entering state 6
Reading a token: Next token is token CP ()
Shifting token CP ()
Entering state 11
Reducing stack by rule 6 (line 20):
   $1 = token OP ()
   $2 = token BAR ()
   $3 = token CP ()
-> $$ = nterm bar_expr ()
Stack now 0
Entering state 4
Reducing stack by rule 2 (line 14):
   $1 = nterm bar_expr ()
-> $$ = nterm program_expr ()
Stack now 0
Entering state 2
Reading a token: Now at end of input.
....
3 голосов
/ 29 мая 2019

Bison генерирует по умолчанию LALR (1) парсеры.LALR (1) расшифровывается как маркер просмотра вперед 1 слева направо.

Ваши грамматики не LALR (1).На OP не понятно, ожидать ли foo или бара.Это конфликт уменьшения / уменьшения.

Смотрите здесь: https://en.wikipedia.org/wiki/LALR_parser

Но обычно Bison может генерировать LR-парсер.По крайней мере, запись в вики утверждает, что: https://en.wikipedia.org/wiki/GNU_Bison

Ваш случай "таинственный конфликт": https://www.gnu.org/software/bison/manual/html_node/Mysterious-Conflicts.html#Mysterious-Conflicts

...