grammar - 文法がそれを期待しているはずのときに予期しないトークンを生成するBison

Question

私はフォーマット言語用のコンパイラを書いていて、bison ファイルを書いています。私の文法は正しいと思いますが、再帰ルールを追加してからテストソースファイルを読み取ると、終了タグのルールを受け入れるがトークンが予期しないと表示されます...追加する前に再帰ルール（開始タグと終了タグの間のいくつかのタグの場合）は正常に機能しました...詳細は次のとおりです

これがソースファイルです

\begin{document}

\title{test}
\author{test}
\date{21/02/1985}
\pagesetup{35, 80}

\end{document}

これはバイソンファイルです

%{
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    extern int  yylex();
    extern int  yyparse();
    extern FILE *yyin;
    extern FILE *yyout;
    extern int  yylineno;

    void yyerror(const char*);
    int header_status(int,int,int,int,int);

    // counters to check nubmer or document properties used, must all become 1
    int title   = 0;
    int author  = 0;
    int date    = 0;
    int pgsetup = 0;
    int tabsz   = 0;
%}

%union{
    int     iVal;
    char*   sVal;
}

%error-verbose

%start source
%token <sVal> SLASH
%token <sVal> BLOCK_S BLOCK_E
%token <sVal> DOC LIST ENUM
%token <sVal> TITLE AUTHOR DATE PG_SETUP TAB_SZ SECTION PARAGRAPH ITEM LINE
%token <sVal> LBRACE RBRACE LPAREN RPAREN
%token <sVal> DOCUMENT DIMENSIONS DATE_VAL STRING
%token <iVal> NUMBER
%token <sVal> ERROR_UN ERROR_IL WORD

%%

source
    : /* empty */  
    | entry_point doc_properties txt_properties exit_point
        { 
            if ( header_status(title, author, date, pgsetup, tabsz) == 0 )
                printf("\nfail\n"); //YYABORT;
        }
    ;

entry_point
    : SLASH BLOCK_S LBRACE DOC RBRACE 
    ;

doc_properties
    : /* empty */  
    | doc_properties header_properties
    ;

header_properties
    : title_property    { title++; }
    | author_property   { author++; }
    | date_property     { date++; }
    | pg_setup_property { pgsetup++; }
    | tab_sz_property   { tabsz++; }
    ;

txt_properties
    : /* empty */  
    ;

title_property
    : SLASH TITLE LBRACE STRING RBRACE
    ;

author_property
    : SLASH AUTHOR LBRACE STRING RBRACE
    ;

date_property
    : SLASH DATE LBRACE DATE_VAL RBRACE
    ;

pg_setup_property
    : SLASH PG_SETUP LBRACE DIMENSIONS RBRACE
    ;

tab_sz_property
    : SLASH TAB_SZ LPAREN NUMBER RPAREN
    ;

exit_point
    : SLASH BLOCK_E LBRACE DOC RBRACE
    ;


%%

int main (int argc, char* argv[])
{
    if ( argc < 2 || argc > 3)
    {
        fprintf(stdout, "%s: fatal error: needs one or two arguments\n\n\t%s inputFileName [outputFileName]\n\n", argv[0], argv[0]);
    }
    else if ( argc == 2 )
    {
        char* fn = (char *)calloc(strlen(argv[1])+12, sizeof(char));
        strcpy(fn, argv[1]);
        strcat(fn, ".output.txt");
        fprintf(stderr, "%s: using default output naming: <%s>\n\n", argv[0], fn);

        yyin = fopen(argv[1], "r");
        yyout = fopen(fn, "w");     
        yyparse();
        fclose(yyin);
        fclose(yyout);
    }
    else if ( argc == 3 )
    {
        yyin = fopen(argv[1], "r");
        yyout = fopen(argv[2], "w");        
        yyparse();
        fclose(yyin);
        fclose(yyout);
    }
    return 0;
}

void yyerror(const char* str) 
{
    fprintf(stderr,"syntax error[%d]: %s\n",yylineno, str);
}

int header_status(int title, int author, int date, int pgsetup, int tabsz)
{
    if ( title == 1 && author == 1 && date == 1 && pgsetup == 1 && tabsz == 1 )
    {
        return 1;
    }
    else
    {
        if ( title > 1 ) fprintf(stderr,"syntax error: title property was declared more than once\n");
        else if ( title < 1 ) fprintf(stderr,"syntax error: title property was not declared (all document properties must be present)\n");

        if ( author > 1 ) fprintf(stderr,"syntax error: author property was declared more than once\n");
        else if ( author < 1 ) fprintf(stderr,"syntax error: author property was not declared (all document properties must be present)\n");

        if ( date > 1 ) fprintf(stderr,"syntax error: date property was declared more than once\n");
        else if ( date < 1 ) fprintf(stderr,"syntax error: date property was not declared (all document properties must be present)\n");

        if ( pgsetup > 1 ) fprintf(stderr,"syntax error: pagesetup property was declared more than once\n");
        else if ( pgsetup < 1 ) fprintf(stderr,"syntax error: pagesetup property was not declared (all document properties must be present)\n");

        if ( tabsz > 1 ) fprintf(stderr,"syntax error: title tabsize was declared more than once\n");
        else if ( tabsz < 1 ) fprintf(stderr,"syntax error: title tabsize was not declared (all document properties must be present)\n");

        return 0;
    }
}

私の問題は

doc_properties
: /* empty */  
| doc_properties header_properties
;

私がそれを空にしてちょうど持っていたとき

\begin{document}
\end{document}

ソースファイルの場合は問題ありませんでした。具体的には、トークンは次のようになります

SLASH BLOCK_S LBRACE DOC RBRACE 
SLASH BLOCK_E LBRACE DOC RBRACE

再帰を使用してルールを追加すると、「最後」に到達すると、トレースはルール (レキシカル) を受け入れたことが示され、「予期しない BLOCK_E」という構文エラーが生成されました。私が考えることができる唯一のことは、それが他のタグを期待しているということですが、再帰では代わりに空を持っているので、なぜ...

また、最終タグを追加したとき

\begin{document}

\title{test}
\author{test}
\date{21/02/1985}
\pagesetup{35, 80}
\tabsize(4)

\end{document}

4 に達すると、lex ファイルのルールを受け入れると表示され、そのルールは

return NUMBER;

しかし、予期しない $undefined と表示され、ルールを受け入れると言ったときに NUMBER を期待しています。率直に言って、それ以外のものを読み取れるとは思いません...

私の質問は最初の部分ですが...

それが助けになるなら、これはflexファイルです

%{
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "UnicTextLang.y.tab.h"

    #define SAVE_S yylval.sVal = strdup(yytext)
    #define SAVE_I yylval.iVal = atoi(yytext)   
%}

WS      [ \t\n\r]
TAG     [a-zA-Z_][a-zA-Z0-9\-_]+
WORD    [a-zA-Z0-9`~!@#$%\^&*()\-_=+[\]{}\\|;:'",<.>/?]
NUMBER  ([1-9])|([1-9][0-9])|([1-3][0-9][0-9])
DIMEN   {NUMBER}{WS}*,{WS}*{NUMBER}
DAY     (0[1-9])|([12][0-9])|(3[01])
MONTH   (0[1-9])|(1[0-2])
YEAR    (19|20)[0-9]{2}
DATE    {DAY}\/{MONTH}\/{YEAR}

%option yylineno
%option noyywrap
%option noinput
%option nounput
%option debug

%x PROPERTY
%x VALUE
%x BLOCK
%x NUMBER

%%

^\\|{WS}\\                  { BEGIN(PROPERTY); /* fprintf(stdout, "FLEX> BEGINING PROPERTY [%d]: %s|\n", yylineno, yytext); */ SAVE_S; return SLASH; }
{WS}?\{                     { BEGIN(VALUE); /* fprintf(stdout, "FLEX> READING PROPERTY VALUE [%d]: %s|\n", yylineno, yytext); */ SAVE_S; return LBRACE; }
{WS}?\(                     { BEGIN(NUMBER); /* fprintf(stdout, "FLEX> READING NUMBER VALUE [%d]: %s|\n", yylineno, yytext); */ SAVE_S; return LPAREN; }
{WS}                        { /* fprintf(stdout, "FLEX> EATING WHITESPACE(i)\n"); */ }
[^ \t\n\r\{(\\][^ \t\n\r]+  { fprintf(stderr, "lexical error[%d]: hingeless word: %s\n", yylineno, yytext); SAVE_S; return WORD; }
.                           { fprintf(stderr, "lexical error[%d]: illegal character detected: %s\n", yylineno, yytext); SAVE_S; return ERROR_IL; }

<PROPERTY>begin             { BEGIN(BLOCK); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return BLOCK_S; }
<PROPERTY>end               { BEGIN(BLOCK); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return BLOCK_E; }

<PROPERTY>title             { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return TITLE; }
<PROPERTY>author            { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return AUTHOR; }
<PROPERTY>date              { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return DATE; }
<PROPERTY>pagesetup         { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return PG_SETUP; }
<PROPERTY>tabsize           { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return TAB_SZ; }

<PROPERTY>section           { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return SECTION; }
<PROPERTY>paragraph         { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return PARAGRAPH; }
<PROPERTY>item              { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return ITEM; }
<PROPERTY>newline           { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> \n\t%s\n\n", yytext); */ SAVE_S; return LINE; }

<PROPERTY>{TAG}             { BEGIN(INITIAL); fprintf(stderr, "lexical error[%d]: |%s| undefined property: expecting property\n", yylineno, yytext); SAVE_S; return ERROR_UN; }
<PROPERTY>{WS}              { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> EATING WHITESPACE(p)\n"); */ }
<PROPERTY>[^ \t\n\r\{(]+    { BEGIN(INITIAL); fprintf(stderr, "lexical error[%d]: |%s| undefined property: illegal character detected\n", yylineno, yytext); SAVE_S; return ERROR_IL; }
<PROPERTY>.                 { fprintf(stderr, "lexical error[%d]: illegal character detected: %s\n", yylineno, yytext); SAVE_S; return ERROR_IL; }

<VALUE>{WS}*{DIMEN}{WS}*    { /* fprintf(stdout, "FLEX> \n\tdims: %s\n\n", yytext); */ SAVE_S; return DIMENSIONS; }
<VALUE>{WS}*{DATE}{WS}*     { /* fprintf(stdout, "FLEX> \n\tdate: %s\n\n", yytext); */ SAVE_S; return DATE_VAL; }
<VALUE>[^}]*                { /* fprintf(stdout, "FLEX> \n\tstrg: %s\n\n", yytext); */ SAVE_S; return STRING; }
<VALUE>\}                   { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> FINISHED READING PROPERTY VALUE [%d]: %s|\n", yylineno, yytext); */ SAVE_S; return RBRACE; }
<VALUE>.                    { fprintf(stderr, "lexical error[%d]: illegal character detected: %s\n", yylineno, yytext); SAVE_S; return ERROR_IL; }

<NUMBER>{WS}*{NUMBER}{WS}*  { /* fprintf(stdout, "FLEX> \n\tnumb: %s\n\n", yytext); */ SAVE_I; return NUMBER; }
<NUMBER>[^)]*               { fprintf(stderr, "lexical error[%d]: |%s| illegal value: expecting number(1-399)\n", yylineno, yytext); SAVE_S; return STRING; }
<NUMBER>\)                  { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> FINISHED READING NUMBER VALUE [%d]: %s|\n", yylineno, yytext); */ SAVE_S; return RPAREN; }
<NUMBER>.                   { fprintf(stderr, "lexical error[%d]: illegal character detected: %s\n", yylineno, yytext); SAVE_S; return ERROR_IL; }

<BLOCK>{WS}?\{              { /* fprintf(stdout, "FLEX> READING BLOCK TYPE [%d]: %s|\n", yylineno, yytext); */ SAVE_S; return LBRACE; }
<BLOCK>{WS}*document{WS}*   { /* fprintf(stdout, "FLEX> \n\tresv: %s\n\n", yytext); */ SAVE_S; return DOC; }
<BLOCK>{WS}*itemize{WS}*    { /* fprintf(stdout, "FLEX> \n\tresv: %s\n\n", yytext); */ SAVE_S; return LIST; }
<BLOCK>{WS}*enumerate{WS}*  { /* fprintf(stdout, "FLEX> \n\tresv: %s\n\n", yytext); */ SAVE_S; return ENUM; }
<BLOCK>[^{}]*               { fprintf(stderr, "lexical error[%d]: |%s| undefined block type: expecting block type\n", yylineno, yytext); SAVE_S; return ERROR_UN; }
<BLOCK>\}                   { BEGIN(INITIAL); /* fprintf(stdout, "FLEX> FINISHED READING BLOCK TYPE [%d]: %s|\n", yylineno, yytext); */ SAVE_S; return RBRACE;}
<BLOCK>.                    { fprintf(stderr, "lexical error[%d]: illegal character detected: %s\n", yylineno, yytext); SAVE_S; return ERROR_IL; }

%%

score 3 · Accepted Answer

あなたが抱えている基本的な問題は、パーサーがどこでdoc_properties終了するかを判断するために 2 つのトークンの先読みを必要とすることです。これは'\'、プロパティ文字列とは別のトークンとして認識するためです。そのためSLASH BLOCK_S、次の入力トークンがである入力を確認した後、空を削減する必要があるか ( の後にa が予想される)、またはルール内にシフトSLASHする必要があるかがわからないためです。ヘッダープロパティの一致の予測。txt_propertiesBLOCK_ESLASHheader_properties

これに対処するものはたくさんあります。おそらく最も簡単な方法は、SLASHトークンを完全に削除することです。これは、プロパティ文字列をいつ検索するかをレクサーに伝える役割を果たしているだけだからです。最初の lex アクションのステートメントを取り除きreturn SLASH;(したがって、トークンを返さず、そのトークンを返すためにの後にプロパティを探し続けます)、文法に現れるすべての場所\を削除します。SLASH

もう 1 つの可能性は、イプシロンルールを取り除くために文法を分解することです (シフト/リデュースの競合につながる初期のリダクションが必要になるため)。イプシロンルールがない場合、パーサーは、RHS で同一のプレフィックスを持つ複数のルールを同時に認識する複合状態に移行できます (この機能は、LL に対する LR 解析の利点です)。これを行うには、次のようなルールがあります。

source: /* empty */
      | entry_point exit_point
      | entry_point doc_properties exit_point
      | entry_point txt_properties exit_point
      | entry_point doc_properties txt_properties exit_point
      ;

変更doc_propertiesさtxt_propertiesれ、0 以上ではなく 1 以上を認識するようになります。

doc_properties: header_property
              | doc_properties header_property
              ;

grammar - 文法がそれを期待しているはずのときに予期しないトークンを生成するBison

1 に答える 1

Related

Reference