时间戳

首页 > 解决方案 > 生成的野牛解析器的意外行为

c - 生成的野牛解析器的意外行为

问题描述

我通过 Flex/Bison 创建了解析器，它在解析过程中意外失败。这是显示问题的简化示例

词法分析器.l：

%{
#include "Parser.h"
%}
%option noyywrap nodefault

%%
"foo"               {   return FOO;                          }
"bar"               {   return BAR;                          }
"("                 {   return OP;                           }
")"                 {   return CP;                           }
[ \t\n]+            {   /*    DO NOTHING  */                 }
.                   {   YY_FATAL_ERROR("unknown character"); }
%%

和 Parser.y（启用跟踪和详细信息）：

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

%debug
%verbose
%error-verbose
%token FOO BAR OP CP

%%
program_expr :   foo_expr bar_expr   {}
;
foo_expr :   /*  NOTHING  */  {}
    |   OP FOO CP           {}
;
bar_expr :   /*  NOTHING  */  {}
    |   OP BAR CP           {}
;
%%

int main(int argc, char** argv)
{
    yydebug = 1;
    yyparse();
    return 0;
}

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

但是如果我指定输入，生成的解析器将失败(bar)- 在这种情况下，解析树应该包含foo为空的表达式。它报告：

开始解析

进入状态 0

读取一个token：下一个token是token OP()

移位令牌 OP()

进入状态 1

读取一个token：下一个token是token BAR()

语法错误，意外的 BAR，期待 FOO

错误：弹出令牌 OP ()

现在堆叠 0

清理：丢弃前瞻令牌 BAR()

现在堆叠 0

这是生成的描述中的一段文本shift/reduce automata：

state 0
    0 $accept: . program_expr $end
    OP  shift, and go to state 1
    OP        [reduce using rule 2 (foo_expr)]
    $default  reduce using rule 2 (foo_expr)
    program_expr  go to state 2
    foo_expr      go to state 3


state 1
    3 foo_expr: OP . FOO CP
    FOO  shift, and go to state 4
state 2
    0 $accept: program_expr . $end
    $end  shift, and go to state 5
state 3
    1 program_expr: foo_expr . bar_expr
    OP  shift, and go to state 6
    $default  reduce using rule 4 (bar_expr)
    bar_expr  go to state 7

但我无法理解这些状态的含义/语法。我的语法/解析器有什么问题？

标签： ccompiler-constructiongrammarbisoncontext-free-grammar

解决方案

Bison 默认生成 LALR(1) 解析器。LALR(1) 代表从左到右的前瞻 1 标记解析器。

您的语法不是 LALR(1)。在 OP 上，不清楚是期待 foo 还是 bar。那是减少/减少冲突。

看这里： https ://en.wikipedia.org/wiki/LALR_parser

但通常 Bison 可以生成 LR 解析器。这里至少有一个 wiki 条目声称： https ://en.wikipedia.org/wiki/GNU_Bison

您的案例是“神秘冲突”：https ://www.gnu.org/software/bison/manual/html_node/Mysterious-Conflicts.html#Mysterious-Conflicts

推荐阅读