我通过 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
表达式。它报告:
Starting parse
Entering state 0
Reading a token: Next token is token OP ()
Shifting token OP ()
Entering state 1
Reading a token: Next token is token BAR ()
syntax error, unexpected BAR, expecting FOO
Error: popping token OP ()
Stack now 0
Cleanup: discarding lookahead token BAR ()
Stack now 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
但我无法理解此类状态的含义/语法。我的语法/解析器有什么问题?
最佳答案
Bison 默认生成 LALR(1) 解析器。 LALR(1) 代表 look ahead 1 token left to right parser。
你的语法不是 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
关于c - 生成的 Bison 解析器的意外行为,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56358948/