有没有办法消除这些 reduce/reduce 冲突？

Question

我正在使用 Bison 和 Flex 开发一种有趣的玩具语言（称为 NOP），但我碰壁了。我正在尝试解析看起来像 name1.name2 和 name1.func1().name2 的序列，但我遇到了很多 reduce/reduce 冲突。我知道 - 为什么 - 得到它们，但我有一段时间想弄清楚该怎么做。

所以我的问题是，这是否是无法“修复”的合法违规行为，或者我的语法是否有误。有问题的作品是 compound_name 和 compound_symbol。在我看来，他们应该分开解析。如果我尝试将它们结合起来，我也会与之发生冲突。在语法上，我试图说明我想做什么，而不是任何“聪明”的东西。

%debug
%defines
%locations

%{
%}
%define parse.error verbose
%locations

%token FPCONST INTCONST UINTCONST STRCONST BOOLCONST
%token SYMBOL
%token AND OR NOT EQ NEQ LTE GTE LT GT
%token ADD_ASSIGN SUB_ASSIGN MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN
%token DICT LIST BOOL STRING FLOAT INT UINT NOTHING

%right ADD_ASSIGN SUB_ASSIGN
%right MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN
%left AND OR
%left EQ NEQ
%left LT GT LTE GTE
%right ':'
%left '+' '-'
%left '*' '/' '%'
%left NEG
%right NOT

%%
program
    : {} all_module {}
    ;

all_module
    : module_list
    ;

module_list
    : module_element {}
    | module_list module_element {}
    ;

module_element
    : compound_symbol {}
    | expression {}
    ;

compound_name
    : SYMBOL {}
    | compound_name '.' SYMBOL {}
    ;

compound_symbol_element
    : compound_name {}
    | func_call {}
    ;

compound_symbol
    : compound_symbol_element {}
    | compound_symbol '.' compound_symbol_element {}
    ;

func_call
    : compound_name '(' expression_list ')' {}
    ;

formatted_string
    : STRCONST {}
    | STRCONST '(' expression_list ')' {}
    ;

type_specifier
    : STRING {}
    | FLOAT  {}
    | INT    {}
    | UINT   {}
    | BOOL   {}
    | NOTHING {}
    ;

constant
    : FPCONST {}
    | INTCONST {}
    | UINTCONST {}
    | BOOLCONST {}
    | NOTHING {}
    ;

expression_factor
    : constant { }
    | compound_symbol { }
    | formatted_string {}
    ;

expression
    : expression_factor {}
    | expression '+' expression {}
    | expression '-' expression {}
    | expression '*' expression {}
    | expression '/' expression {}
    | expression '%' expression {}
    | expression EQ expression {}
    | expression NEQ expression {}
    | expression LT expression {}
    | expression GT expression {}
    | expression LTE expression {}
    | expression GTE expression {}
    | expression AND expression {}
    | expression OR expression {}
    | '-' expression %prec NEG {}
    | NOT expression {  }
    | type_specifier ':' SYMBOL {} // type cast
    | '(' expression ')' {}
    ;

expression_list
    : expression {}
    | expression_list ',' expression {}
    ;

%%

这是一个非常精简的解析器。 “真正的”是大约 600 行。如果我不尝试在变量名中使用函数调用，它就没有冲突（并通过了一系列测试）。如果我不能让 Bison 做我想做的事，我正在考虑将其重写为 Packrat 语法。项目的其余部分在这里：https://github.com/chucktilbury/nop

$ bison -tvdo temp.c temp.y
temp.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]
temp.y: warning: 16 reduce/reduce conflicts [-Wconflicts-rr]

Answer 1

所有 reduce/reduce 冲突的结果是：

module_element
    : expression
    | compound_symbol

这会造成歧义，因为您也有

expression
    : expression_factor
expression_factor
    : compound_symbol

因此解析器无法判断您是否需要减少单元产生式。消除 module_element: compound_symbol 不会改变可以生成的句子集；它只需要在成为 module_element.

之前通过 expression 减少 compound_symbol

与 Chris Dodd points out in a 一样，两个 module_element 可以在没有定界符的情况下连续出现这一事实造成了额外的歧义：语法允许 a - b 被解析为单个 expression（因此 module_element）或两个连续的 expression——a 和 -b——因此两个连续的 module_element。这种歧义导致了四个 shift/reduce 冲突中的三个。

这两个都可能是您简化语法时引入的错误，因为看起来完整语法中的模块元素是定义，而不是表达式。完全删除模块并使用 expression 作为起始符号只会留下一个冲突。

该冲突确实是 compound_symbol 和 compound_name 之间歧义的结果，如您的问题所述。这些作品中出现了问题（缩短了非终端以使打字更容易）：

name: SYMBOL
    | name '.' SYMBOL
symbol
    : element
    | symbol '.' element
element
    : name

这意味着 a 和 a.b 都是 name，因此
element秒。但是 symbol 是 . 分隔的 element 列表，因此 a.b 可以通过两种方式导出：


symbol → element              symbol → symbol . element
       → name                        → element . element
       → a.b                         → name . element
                                     → a . element
                                     → a . name
                                     → a . b

我通过将语法简化为以下方式解决了这个问题：

compound_symbol
    : compound_name
    | compound_name '(' expression_list ')'
compound_name
    : SYMBOL
    | compound_symbol '.' SYMBOL

这摆脱了 func_call 和 compound_symbol_element，据我所知，这没有任何用处。我不知道剩下的非终端名称是否真的捕捉到了任何明智的东西；我认为将 compound_symbol 称为 name_or_call.

更有意义

如果可以使用高阶函数，则可以进一步简化此语法；现有语法禁止 hof()()，大概是因为您没有考虑允许函数 return 函数对象。

但即使是高阶函数，您也可能想要区分函数调用和成员 access/array 下标，因为在许多语言中，函数不能 return 对象 reference 因此函数调用不能出现在赋值运算符的左侧。在其他语言中，例如 C，要求赋值运算符的左侧是引用（“左值”）是在语法之外强制执行的。（并且在 C++ 中，函数调用甚至重载运算符都可以 return 引用，因此需要在类型分析后强制执行限制。）

有没有办法消除这些 reduce/reduce 冲突？

Is there a way to eliminate these reduce/reduce conflicts?

grammar

conflict

bison