3

我正在尝试将计算器从 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] 后才返回结果（ctrl Z 表示 cmd.exe 的输入结束）。

我做错了什么？

Bison/Flex 版本源码

坏的.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;
}

坏的.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 版源码

小伙子

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

1 回答 1

8

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

Lemon 没有实现这种优化。它总是需要一个前瞻令牌。（但是，它也执行表压缩 IIRC，因此即使前瞻标记表明输入格式不正确，它也可以进行缩减。这是 LALR(1) 解析的一个特性。）

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

start   ::= prog .

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

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

在这里，从exprto的缩减print仅仅是为了打印表达式的值。

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

于 2014-07-19T05:26:32.580 回答