Bison/YACC对Lemon与标准输入的比较

Question

我想把一个计算器从Bison转换成Lemon。

我遇到了一个意外的问题，涉及标准输入，其中两个程序的行为非常不同。Bison版本在按Enter后立即打印结果。对于Lemon版本，结果会被延迟，直到我键入一个新表达式并按Enter键。

我创建了微型Bison和Lemon语法以及Flex扫描仪来说明这个问题。这是在Windows 7上，使用了2014年7月版本的Lemon、Bison 2.41和gcc (tdm64-2) 4.8.1。

Bison版本的简单会话

​

​

注意在简单表达式之后按Enter后返回结果的方式。

Lemon版本的简单会话

​

​

注意结果是如何只在输入第二个表达式并按下Enter之后才返回的。

我做错了什么？

Bison/Flex版本源

巴德尔：

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

巴迪：

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

柠檬/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;
}

拉迪：

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

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

Answer 1

如果只有一个可能的还原动作而没有可能的移位操作，Bison (1)解析器将立即减少。(这并不意味着所有前瞻性令牌都具有相同的还原操作。有些可能是错误，但无论如何都会减少。)

柠檬没有实现这种优化。它总是需要一个前瞻性令牌。(然而，它也做表压缩IIRC，所以它也可以做一个缩减，即使前瞻性令牌表明输入不是良好的格式。这是LALR(1)解析的一个特性。

解决这个问题的关键是确保以换行符作为向前看令牌来执行打印表达式值的缩减。在Yacc或Bison中，您可以使用中间规则操作来实现这些操作，但是Lemon没有实现这些操作，因此您需要添加一个单元规则来触发该操作，如下所示：

start   ::= prog .

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

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

在这里，从expr减少到print只是为了打印表达式的值。

顺便说一句，这个解决方案在Yacc或Bison中也能很好的工作。它可以说比依赖Bison的前瞻性优化更好，据我所知，这并不能保证在任何情况下都能工作。