基本 PHP 像使用 flex 和 bizon 的解释器。 Reduce/reduce 和 shift/reduce 冲突

Question

我正在编写一个类似于 PHP 的解释器，但在 shift/reduce 和 reduce/reduce 冲突方面遇到了一些问题。有人可以帮助我理解 shift/reduce 和 reduce/reduce 冲突。

我必须编写和解释 ship/echo 无值的表达式并评估以 "magic" @ 字符开头的表达式，例如@if(cond) ... @end;。所以 "if" 必须被回显而 @if(cond) 应该被解释

问题：scriptlang.y 包含 21 个 shift/reduce 冲突和 2 个 reduce/reduce 冲突。

%union {
    char* sval;
}
%token <sval> IDENTIFIER
%token <sval> RBRACKET
%token <sval> LBRACKET
%token <sval> KWSWITCH
%token <sval> KWIF
%token <sval> MAGICESC
%token MAGIC
%token ENDSTM

%type <sval> filechar

%start script

%%
script:
   commands
;
commands:   
    /* empty */
    | command 
    | commands command
;
command:
    filechar {
        analyser_echo(,"filechar",analyser_canEcho);
    }
    | magic_command {}
;
filechar:
    IDENTIFIER
    | LBRACKET
    | RBRACKET
    | KWSWITCH
    | KWIF
    | MAGICESC
;
magic_command:
    MAGIC valuation
    | MAGIC alternative
;
valuation:
    LBRACKET IDENTIFIER RBRACKET {
        fprintf(yyout, "<val>");
    }
;
alternative:
    switch_alternative
    | if_alternative
;
switch_alternative:
    switch_block end_stm
;
switch_block:
    switch_stm
    | switch_stm commands
;
switch_stm:
    KWSWITCH LBRACKET IDENTIFIER RBRACKET {}
;
if_alternative:
    if_block end_stm
;
if_block:
    if_stm
    | if_stm commands
;
if_stm:
    KWIF LBRACKET IDENTIFIER RBRACKET {}
;
end_stm:
    ENDSTM
;
%%

弹性文件内容：

"@@" {
    yylval.sval = "@"; 
    return MAGICESC;
}
"@" {
    return MAGIC;
}
"(" {
    yylval.sval = yytext; 
    return LBRACKET;
}
")" {
    yylval.sval = yytext; 
    return RBRACKET;
}
"@end;" { 
    return ENDSTM;
}
"if" {
    yylval.sval = yytext; 
    return KWIF;
}
"switch" {
    yylval.sval = yytext; 
    return KWSWITCH;
}
[a-zA-Z][_a-zA-Z0-9]* {
    yylval.sval = yytext; 
    return IDENTIFIER;
}
\n|. {
    if(analyser_canEcho>0){
        ECHO;
    }
}
%%

Answer 1

导致冲突的基本问题是您对 commands 的处理。你的意图是定义commands为零个或多个command，写法如下：

commands: %empty
        | commands command

如果你想坚持至少有一个命令，你会写：

commands: command
        | commands command

混合使用这两种形式是行不通的，因为解析器不知道是开始一系列 command 什么都不用 (%empty) 还是只用一个 command。您应该尝试准确理解为什么这会导致歧义；您会在此站点上找到许多类似问题的示例。例如，参见 this question。

这会产生 21 个 shift/reduce 冲突。 reduce/reduce 冲突是好奇产生的结果：

switch_block: switch_stm commands
if_block: if_stm commands

if 和 switch 语句是 commands 序列中的单个 command 元素； switch 或 if 语句之后的内容将是 commands 中的下一个 command。定义 switch_block 以包含以下命令完全是模棱两可的：实际上，它是说下一个 command 可能仍然是 switch_block 的一部分，或者它可能是 command继 switch_block.

上面，我专门解决了你问的问题：你语法中的解析table冲突。你的语法和词汇规范还有其他各种问题，我强烈建议你研究你得到的关于 bison/flex、and/or 的任何材料，阅读 bison and flex 手册。

作为您阅读手册或其他材料的指南，我建议您至少关注两件事：

语义值的处理。句法关键字永远不需要有自己的表示作为语义值；实际上，句法关键字根本不需要语义值。如果一个标记确实要求它的语义值是它的表示，你需要记住 yytext 是一个指向你不拥有的私有数据缓冲区的指针，它会在没有警告的情况下被修改。因此需要复制。
像您的 PHP 变体这样的嵌入式语言涉及两种不同的词汇上下文。您有一个外部的、本质上未解释的上下文，以及一个包含在 @ 和 @end; 之间的嵌入式上下文。 (F)lex 提供 开始条件 来帮助处理这种嵌入。手册中有一些示例，此站点周围还有更多示例。

基本 PHP 像使用 flex 和 bizon 的解释器。 Reduce/reduce 和 shift/reduce 冲突

Basic PHP like interpreter using flex and bizon. Reduce/reduce and shift/reduce conflicts

bison

flex-lexer