yacc прекратить делать shift&& lower, когда больше не может получить символ yylex()

Question

Вот мой код:

%{
#include<string.h> 
#include "y.tab.h"
#define DEBUG 0
void yyerror(char* s);
void debug(char* string) {
    if (DEBUG) {
        printf(string);
    }
}
%}  
selector   "selector"[0-9]+
positive   "+"
negtive    "-"
contains   "."
before     "->"
or         "||"
and        "&&"
delim      [ /n/t]  
ws         {delim}*
%%  
{selector} { debug("Lex:SELECTOR\n"); yylval.string = yytext; return     SELECTOR; }  
{positive} { debug("Lex:POSITIVE\n"); return POSITIVE; }  
{negtive}  { debug("Lex:NEGTIVE\n"); return NEGTIVE; }  
{contains} { debug("Lex:BELONGS\n"); return CONTAINS; } 
{before}   { debug("Lex:BEFORE\n"); return BEFORE; }  
{or}       { debug("Lex:OR\n"); return OR; }  
{and}      { debug("Lex:AND\n"); return AND; } 
{ws}       ;
.          { debug("Lex Parser Error"); exit(1); }    
%%

.y:
%{
#include <stdio.h>
#define YYDEBUG 0
int yyparse(void);
void yyerror(char* s);
%}

%union {
    char *string;
}

%token <string> SELECTOR 
%token POSITIVE
%token NEGTIVE
%left CONTAINS
%left BEFORE
%token OR
%token AND

%%
logical_expr : assertion { printf("[reduce] L->A\n"); } 
    | logical_expr AND assertion { printf("[reduce] L->L && A\n");}   
    | logical_expr OR assertion { printf("[reduce] L->L || A\n"); }        
;
assertion : POSITIVE prefix_relation { printf("[reduce] A->+P\n"); }
    | NEGTIVE prefix_relation { printf("[reduce] A->-P\n"); }
;
prefix_relation : prefix_relation BEFORE contain_relation { printf("[reduce] P->P->C\n"); }
    | contain_relation { printf("[reduce] P->C\n");;}
;
contain_relation : contain_relation CONTAINS SELECTOR { printf("[reduce] C->C.S[%s]\n", $3); }
    | SELECTOR { printf("[reduce] C->S[%s]\n", $1); }
;
%%
int main()
{
    return yyparse();
}
void yyerror(char* s)
{
    fprintf(stderr,"%s",s);
}
int yywrap()
{
    return 1;
}

моя входная строка: +selector1.selector2||-selector4->selector4

ожидается, что дерево разбора этого ввода будет:

моя программа, сгенерированная yacc, выдает результат, как показано ниже:

[reduce] C->S[selector1]     // stack: +C
[reduce] C->C.S[selector2]   // stack: +C
[reduce] P->C                // stack: +P
[reduce] A->+P               // stack: A
[reduce] L->A                // stack: L
[reduce] C->S[selector3]     // stack: L||-C
[reduce] P->C                // stack: L||-P
[reduce] C->S[selector4]     // stack: L||-P->C

Похоже, что программа перестает делать shift&& limit после того, как не может получить больше символов из yylex(), но я ожидаю, что это уменьшит оставшиеся символы в стеке, таким образом L||-P->C, так что я могу генерировать все дерево разбора в моем коде.

мой ожидаемый результат:

[reduce] C->S[selector1]     // stack: +C
[reduce] C->C.S[selector2]   // stack: +C
[reduce] P->C                // stack: +P
[reduce] A->+P               // stack: A
[reduce] L->A                // stack: L
[reduce] C->S[selector3]     // stack: L||-C
[reduce] P->C                // stack: L||-P
[reduce] C->S[selector4]     // stack: L||-P->C
[reduce] P->P->C             // stack: L||-P
[reduce] A->-P               // stack: L||A
[reduce] L->L||A             // stack: L

Answer 1

Существует ряд проблем с определением вашего сканера (flex).

1. Ваше гибкое правило по умолчанию просто вызывает exit без каких-либо сообщений об ошибках, (если только DEBUG определено и не равно нулю), поэтому любая лексическая ошибка приведет к тихой остановке программы. Было бы намного лучше позвонить yyerror в этом случае и выдайте видимое сообщение об ошибке.

2. Как указывает EJP в комментарии, ваш delim определение использует /n а также /t вместо \n а также \t, поэтому он не будет соответствовать ни переводу строки, ни вкладке. Новая строка также не будет соответствовать вашему правилу по умолчанию, поэтому она перейдет к сгенерированному по флексам правилу по умолчанию, которое просто выводит несопоставленный символ в stdout, (Лучше включить %option nodefault, что заставит flex выдать сообщение об ошибке, если какой-либо ввод не соответствует ни одному из ваших правил.)

3. Ваш selector наборы правил yylval.string = yytext, Вы не можете сделать это, потому что yytext указывает на внутреннее хранилище сканера, и строка, на которую он указывает, будет изменена в следующий раз yylex называется. Если вы хотите передать соответствующий токен из сканера в анализатор, вы должны сделать копию токена, а затем вам нужно убедиться, что вы free память, выделенная для него, когда вам больше не нужна строка, чтобы избежать утечки памяти.

4. Вы должны знать, что парсеры генерируются bison или же yacc как правило, перед выполнением сокращений необходимо прочитать токен предпросмотра. Следовательно, последняя серия ожидаемых сокращений не будет выполнена, пока сканер не вернет END токен, который он будет делать только при чтении конца файла. Поэтому, если вы тестируете свой анализатор в интерактивном режиме, вы не увидите окончательных сокращений, пока не сообщите об окончании файла, набрав ctrl D (в Unix).

В заключение, оба flex а также bison способны генерировать выходные данные отладки, которые указывают, какие правила соответствуют (flex) и серии сдвигов, сокращений и других действий синтаксического анализатора (bison). Проще и надежнее использовать эти функции, чем пытаться реализовать собственный отладочный вывод.