3

電卓をバイソンからレモンに変換しようとしています。

2 つのプログラムの動作がまったく異なる、標準入力に関する予期しない問題に遭遇しました。Bison バージョンでは、[Enter] を押すとすぐに結果が出力されます。Lemon バージョンでは、新しい式を入力して [Enter] を押すまで結果が表示されません。

この問題を説明するために、小さな Bison と Lemon の文法と Flex スキャナーを作成しました。これは Windows 7 で、Lemon、Bison 2.41、および gcc (tdm64-2) 4.8.1 の 2014 年 7 月バージョンを使用しています。

Bison バージョンでの簡単なセッション

バイソン版セッション

単純な式の後で [Enter] を押すと、結果がどのように返されるかに注目してください。

レモンバージョンの簡単なセッション

レモンバージョンセッション

2 番目の式を入力して [Enter] を押した後にのみ結果が返されることに注意してください (ctrl Z は、cmd.exe の入力の終わりを示します)。

私は何を間違えましたか？

Bison/Flex バージョン ソース

badd.l:

%{
    #include "y.tab.h"
    #include <stdlib.h>
%}

%%
[0-9]+      {yylval = atoi(yytext); return INTEGER;}
[+]         return PLUS;
[\n]        return NL;
[ \t]       ;       /* skip whitespace */
.           {printf("Unknown character '%c'\n", yytext[0]); return 0;}
%%

int yywrap(void) {
    return 1;
}

badd.y:

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

%token INTEGER PLUS NL
%left PLUS MINUS

%%

prog:   prog expr NL                { printf("%d\n", $2); }
        |
        ;
expr:   INTEGER                     { $$ = $1; }
        | expr PLUS expr            { $$ = $1 + $3; }
        ;
%%

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

int main(void) {
    yyparse();
    return 0;
}

ビルドするには:

bison -y -d badd.y
flex badd.l
gcc y.tab.c lex.yy.c -o badd.exe

Lemon/Flex版ソース

ladd.l

%{
    #include "ladd.h"
    #include <stdlib.h>
    extern int yylval;
%}

%%
[0-9]+      {yylval = atoi(yytext); return INTEGER;}
[+]         return PLUS;
[\n]        return NL;
[ \t]       ;       /* skip whitespace */
.           {printf("Unknown character '%c'\n", yytext[0]); return 0;}
%%

int yywrap(void) {
    return 1;
}

ladd.y:

%include { #include <assert.h> }
%syntax_error { printf("Lemon syntax error\n"); }
%token_type {int}
%left PLUS MINUS .

start   ::= prog .

prog    ::= prog expr(a) NL .           { printf("%d\n", a); }
prog    ::= .

expr(a) ::= INTEGER(b) .                { a = b; }
expr(a) ::= expr(b) PLUS expr(c) .      { a = b + c; }

main.c:

#include <stdio.h>
#include <stdlib.h>

void *ParseAlloc(void *(*mallocProc)(size_t));
void ParseFree(void *p, void (*freeProc)(void*));
void Parse(void *yyp, int yymajor, int foo);

int yylex(void);
int yylval;

int main(void) {
   void *pParser;
   int tok;

   pParser = ParseAlloc(malloc);

   while ((tok = yylex()) != 0) {
      Parse(pParser, tok, yylval);
   }
   Parse(pParser, 0, 0);
   ParseFree(pParser, free );

   return 0;
}

ビルドするには:

lemon ladd.y
flex ladd.l
gcc main.c ladd.c lex.yy.c -o ladd.exe
4

1 に答える 1

8

Bison LALR(1) パーサーは、可能な還元アクションが 1 つしかなく、可能なシフト アクションがない場合、すぐに還元します。(これは、すべての先読みトークンが同じ削減アクションを持つという意味ではありません。一部はエラーになる可能性がありますが、いずれにせよ削減は行われます。)

Lemon はこの最適化を実装していません。常に先読みトークンが必要です。(ただし、テーブル圧縮 IIRC も行うため、先読みトークンが入力の形式が正しくないことを示している場合でも、削減を行う場合があります。これは、LALR(1) 解析の機能です。)

この問題を解決するための鍵は、式の値を出力するリダクションが改行を先読みトークンとして実行されるようにすることです。Yacc や Bison では、ルールの途中のアクションでこれを行うことができますが、Lemon はこれらを実装していないため、アクションをトリガーするには、次のようなユニット ルールを追加する必要があります。

start   ::= prog .

prog    ::= prog print NL .
prog    ::= .

print   ::= expr(a) .         { printf("%d\n", a); }

exprここで、 toからの縮print約は、式の値を出力するためだけのものです。

ちなみに、このソリューションは Yacc や Bison でも問題なく動作します。私の知る限り、すべての状況で動作することが保証されているわけではありません。

于 2014-07-19T05:26:32.580 に答える