parsing - Bison/YACC vs. Lemon vs. 标准输入

Question

我正在尝试将计算器从 Bison 转换为 Lemon。

我遇到了一个涉及标准输入的意外问题，其中这两个程序的行为完全不同。野牛版按 [Enter] 后立即打印结果。随着柠檬版，结果延迟到我输入新的表达式并按 [Enter]。

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

与 Bison 版本的简单 session

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

柠檬版的简单 session

注意结果是如何只在输入 a 后返回的第二个表达式并按下 [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;
}

小伙子:

%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

Answer 1

如果只有一个可能的归约 Action 而没有可能的移位 Action ，则 Bison LALR(1) 解析器将立即归约。 (这并不意味着所有的前瞻标记都具有相同的减少操作。有些可能是错误的，但无论如何都会发生减少。)

Lemon 没有实现这个优化。它总是需要一个前瞻 token 。 (但是，它也执行表压缩 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 的前瞻优化更好，据我所知，它并不能保证在所有情况下都能正常工作。