Bison shift/reduce 和 reduce/reduce 冲突
Bison shift/reduce and reduce/reduce conflict
OK，这个Bison语法我已经试了三次重写了，一直运行变成shift/reduce和reduce/reduce冲突。我试图解析的语法如下。 {...} 中的项目用于一个或另一个。 [...] 中的项目是可选的。
CONSTANT constant-name constant-class
constant-class = { EQUALS expression numeric-options }
{ EQUALS STRING string string-options }
numeric-options = [ PREFIX prefix-string ]
[ TAG tag-string ]
[ COUNTER #local-name ]
[ TYPENAME type-name ] ;
string-options = [ PREFIX prefix-string ]
[ TAG tag-string ] ;
CONSTANT (constant-name,...) EQUALS expression
[ INCREMENT expression ]
[ PREFIX prefix-string ]
[ TAG tag-string ]
[ COUNTER #local-name ]
[ TYPENAME type-name ];
CONSTANT constant-name EQUALS expression,
.
.
.
;
CONSTANT (constant-name,...) EQUALS expression,
.
.
.
;
我在让最后三个全部工作时遇到问题。我可以让他们中的任何一个工作，但不是全部 4 个。我现在有一个 shift/reduce 和一个 reduce/reduce 冲突。我的语法如下：
constant
: SDL_K_CONSTANT constant_style ';'
;
constant_style
: constant_name constant_class
| constant_list
| constant_set
;
constant_name
: sdl_name
;
constant_class
: SDL_K_EQUALS sdl_decimal
| SDL_K_EQUALS SDL_K_STRING sdl_string
;
constant_names
: constant_name
| constant_names ',' constant_name
| '(' constant_names ')'
;
names_equal
: constant_names SDL_K_EQUALS sdl_decimal
;
constant_list
: names_equal
;
constant_set
: names_equal
| constant_set ',' names_equal
;
我认为名称是自我记录的（至少你应该能够理解类型）。任何帮助将不胜感激。我有一种感觉，我要么简化得太多，要么简化得不够。
注意：我想出了如何编辑 post 并删除了选项，并将 SDL_K_COMMA 和 SDL_K_SEMI 分别更改为“,”和“;”。
谢谢。
下面是一些应该解析的例子：
CONSTANT block_node_size EQUALS 24;
CONSTANT Strcon EQUALS STRING "This is a string constant" PREFIX Jg$
#block_size = 24;
CONSTANT block_node_size EQUALS #block_size;
CONSTANT
xyz EQUALS 10,
alpha EQUALS 0,
noname EQUALS 63;
CONSTANT
(zyx, nameless) EQUALS 10,
(beta) EQUALS 1,
gamma EQUALS 42;
CONSTANT (
bits,
bytes,
words,
longs,
quads,
octas
) EQUALS 0 INCREMENT 1 PREFIX ctx$;
CONSTANT
(bad_block,bad_data,,,,
overlay,rewrite) EQUALS 0 INCREMENT 4;
CONSTANT (pli,c,bliss,macro)
EQUALS 4 INCREMENT 4 PREFIX lang$
COUNTER #lang;
CONSTANT (basic,pascal,fortran)
EQUALS #lang + 4 INCREMENT 4 PREFIX lang$;
希望对您有所帮助。
顺便说一句：这是用于此的 EBNF（某种程度上）：
/*
* Define the CONSTANT construct (Left out Expression).
*/
Str ::= "\"" Printable* "\""
Name ::= "$" | "_" | [A-Za-z] ("$" | "_" | [A-Z0-9a-z])*
Names ::= Name | ("(" Name ("," Name )* ")")
Constant_class ::= "EQUALS" (Expression Numeric_options | "STRING" Str
String_options)
String_options ::= Prefix? Tag?
Numeric_options ::= String_options Counter? Typename? Radix?
Increment_options ::= Increment? Numeric_options
Constant_list ::= Names "EQUALS" Expression Increment_options
Constant_set ::= Names Equals Expression
("," Names "EQUALS" Expression)*
Constant ::= "CONSTANT" (Name Constant_class | Constant_list |
Constant_set) ";"?
Prefix ::= "PREFIX" Str
Tag ::= "TAG" Str
Radix ::= "RADIX" ("DEC" | "OCT" | "HEX")
Counter ::= "COUNTER" Variable
Increment ::= "INCREMENT" Expression
Typename ::= "TYPENAME" Name
我想就是这样了。
我有点难以理解您实际想要做什么，所以我做了一些假设并在下面提供了一些备选方案。我希望它接近。
基本问题是语法规范中的歧义。其中一个可能只是一个错误：根据您的模板，EQUAL 的左侧似乎是单个 name 或 name 的逗号分隔列表s 被括号括起来。但是，您的语法允许 name 的逗号分隔列表，列表中的第一个（或唯一）项可能是带括号的名称列表：
constant_names
: constant_name
| constant_names ',' constant_name
| '(' constant_names ')
这将匹配 a、a, b、(a, b)、(a, b), c 和 (a, b), c, d。但我认为只有第一个和第三个是真正有意的。
无论如何，你有两个作品：
constant_style
: constant_name constant_class
| constant_list
对于第一个，我们有：
constant_class
: SDL_K_EQUALS sdl_decimal
而对于第二个，我们有：
constant_list: names_equal
names_equal
: constant_names SDL_K_EQUALS sdl_decimal
由于constant_name可以匹配单个name，所以有两种不同的方式来匹配answer = 42，难免会导致解析冲突
但是 answer = 42 还有另一种可能的解析：
constant_set
: names_equal
所以让我们从简化所有这些东西开始，然后我们也许可以回到（可能是）您最初的目标。这个想法是分解所有语法相似的东西：
constant-stmt : "CONSTANT" clause-list ';'
clause-list : clause | clause-list ',' clause
clause : left-hand-side "EQUALS" right-hand-side
left-hand-side : name | '(' name-list ')'
name-list : name | name-list ',' name
right-hand-side: expression /* See below */
我希望这一切足够简单易懂。
但我们可以从原文中看出（至少在某些情况下）right-hand-side 的选项比上面代码段中出现的要多得多。将其他语法添加到 right-hand-side 是微不足道的。但是，其意图似乎是这些额外选项仅在有单个子句的情况下可用。在那种情况下，我们可以这样做：
constant-stmt : "CONSTANT" constant-body ';'
constant-body : complex-clause | clause-list
clause-list : clause | clause-list ',' clause
clause : left-hand-side "EQUALS" right-hand-side
right-hand-side: expression
complex-clause : left-hand-side "EQUALS" complex-rhs
complex-rhs : expression numeric-options
| "STRING" string-literal string-options
但不幸的是，这又回到了歧义，因为 numeric-options 可能为空，所以 expression 将同时匹配 right-hand-side 和 complex-right-hand-side。
实际上，这种歧义并不重要。声明 name EQUALS expression 作为 CONSTANT 声明中的唯一声明或作为此类声明的列表之一之间没有语义差异。因此，一种可能性是忽略由此产生的 reduce/reduce 冲突，可能是通过将 %expect 1 放入文件中。但这真的不是很愉快。所以我们会尽量排除这个问题。
一种方法是坚持第一个 complex-rhs 至少有一个 numeric-option。但这真的很烦人。首先，我们必须创建另一种子句类型——first-complex-clause 或类似的类型——其次，我们必须写出至少存在一个选项的要求。
作为一个更简单的替代方案，我们可以只要求一个 clause-list 至少有两个 clause，而不是只有一个。由于每个 clause 也可以匹配 complex-clause，因此对 clause-list 的限制不会拒绝任何有效的 clause。所以这给了我们非常小的变化：
constant-body : complex-clause | clause-list
clause-list : clause ',' clause | clause-list ',' clause
附录
随着对预期语法的更精确描述（尽管仍然缺少一些细节），我修改了上面的语法以尝试解析完整的语言。基本原则保持不变：定义由单个 complex-clause（包括简单子句格）或至少两个简单 clause 的列表组成。唯一的区别是两种子句类型的定义方式。
我还修复了名单生成，以便可以省略个别名称（例如 (bad_block,bad_data,,,,overlay,rewrite)）。如指南中所述，该列表必须至少包含一个名称，这会使语法稍微复杂一些。
我添加了指南中的选项（但没有添加 EBNF 中的额外选项）。我没有尝试处理省略的分号，指南中似乎不允许分号，尽管有一个没有尾随分号的声明示例。 （这可能是一个错字。）据我所知，我添加了 expression 的定义。
我还添加了本地名称赋值语句，因为它在测试文件中并且很容易。
语法如下：
definition : %empty
| definition constant-defn
| definition local-assign
local-assign : LOCAL_NAME '=' expression ';'
constant-defn : "CONSTANT" constant-body ';'
constant-body : complex-clause | clause-list
clause-list : clause ',' clause | clause-list ',' clause
clause : name "EQUALS" expression
| name-list "EQUALS" expression
complex-clause : name "EQUALS" expression numeric-options
| name-list "EQUALS" expression list-options
| name "EQUALS" "STRING" string-literal string-options
| name-list "EQUALS" "STRING" string-literal string-options
name-list : '(' names ')'
names : optional-commas name | names ',' name | names ','
optional-commas : %empty | optional-commas ','
string-options : prefix-option tag-option
numeric-options : string-options counter-option typename-option
list-options : increment-option numeric-options
increment-option: %empty | "INCREMENT" expression
prefix-option : %empty | "PREFIX" prefix-name
tag-option : %empty | "TAG" tag-name
counter-option : %empty | "COUNTER" LOCAL_NAME
typename-option : %empty | "TYPENAME" name
expression : '-' expression %prec UNOP
| expression '*' expression
| expression '/' expression
| expression '+' expression
| expression '-' expression
| expression '@' expression
| expression '&' expression
| expression '!' expression
| '(' expression ')'
| INTEGER
| IDENT
| LOCAL_NAME
name : IDENT | QUOTED_IDENT
prefix-name : IDENT | QUOTED_NULL | QUOTED_IDENT
tag-name : IDENT | QUOTED_NULL | QUOTED_IDENT | QUOTED_TAG
string-literal : QUOTED_NULL | QUOTED_IDENT | QUOTED_TAG | QUOTED_STRING
您会看到我添加了对各种类型的引用字符串的区分，以便可以处理（大部分）引用字符串可能出现的不同上下文。如指南中所述，我没有将最多 4 个字符的带引号的字符串用作整数常量，因为我没有及时注意到它，也因为我无法通过简短阅读来弄清楚是否目的是允许在名称必须被引用的表达式中使用常量（因为名称与关键字冲突）；在那种情况下，在我看来，引号中包含四个或更少字符的名称存在歧义。
如果歧视的工作原理不明显（可能不是），这里是随附的 flex 定义：
id [[:alpha:]$_][[:alnum:]$_]*
%%
[[:space:]]+ ;
CONSTANT { return K_CONSTANT; }
COUNTER { return K_COUNTER; }
EQUALS { return K_EQUALS; }
INCREMENT { return K_INCREMENT; }
PREFIX { return K_PREFIX; }
STRING { return K_STRING; }
TAG { return K_TAG; }
TYPENAME { return K_TYPENAME; }
[#]{id} { yylval.str = strndup(yytext, yyleng); return LOCAL_NAME; }
{id} { yylval.str = strndup(yytext, yyleng); return IDENT; }
["]{id}["] { yylval.str = strndup(yytext+1, yyleng-2); return QUOTED_IDENT; }
["]["] { yylval.str = strndup(yytext+1, yyleng-2); return QUOTED_NULL; }
["][[:alnum:]$_]+["] { yylval.str = strndup(yytext+1, yyleng-2); return QUOTED_TAG; }
["][[:print:]]+["] { yylval.str = strndup(yytext+1, yyleng-2); return QUOTED_STRING; }
[[:digit:]]+ { yylval.dec = strtoul(yytext, 0, 0); return INTEGER; }
. { return *yytext; }
我通过 运行 对 OP 末尾的定义进行了相当不充分的测试（尽管我在第二行添加了尾随 ;）。我实际上并没有检查解析树是否正确，但它确实全部通过了解析器。
OK，这个Bison语法我已经试了三次重写了，一直运行变成shift/reduce和reduce/reduce冲突。我试图解析的语法如下。 {...} 中的项目用于一个或另一个。 [...] 中的项目是可选的。
CONSTANT constant-name constant-class
constant-class = { EQUALS expression numeric-options }
{ EQUALS STRING string string-options }
numeric-options = [ PREFIX prefix-string ]
[ TAG tag-string ]
[ COUNTER #local-name ]
[ TYPENAME type-name ] ;
string-options = [ PREFIX prefix-string ]
[ TAG tag-string ] ;
CONSTANT (constant-name,...) EQUALS expression
[ INCREMENT expression ]
[ PREFIX prefix-string ]
[ TAG tag-string ]
[ COUNTER #local-name ]
[ TYPENAME type-name ];
CONSTANT constant-name EQUALS expression,
.
.
.
;
CONSTANT (constant-name,...) EQUALS expression,
.
.
.
;
我在让最后三个全部工作时遇到问题。我可以让他们中的任何一个工作，但不是全部 4 个。我现在有一个 shift/reduce 和一个 reduce/reduce 冲突。我的语法如下：
constant
: SDL_K_CONSTANT constant_style ';'
;
constant_style
: constant_name constant_class
| constant_list
| constant_set
;
constant_name
: sdl_name
;
constant_class
: SDL_K_EQUALS sdl_decimal
| SDL_K_EQUALS SDL_K_STRING sdl_string
;
constant_names
: constant_name
| constant_names ',' constant_name
| '(' constant_names ')'
;
names_equal
: constant_names SDL_K_EQUALS sdl_decimal
;
constant_list
: names_equal
;
constant_set
: names_equal
| constant_set ',' names_equal
;
我认为名称是自我记录的（至少你应该能够理解类型）。任何帮助将不胜感激。我有一种感觉，我要么简化得太多，要么简化得不够。
注意：我想出了如何编辑 post 并删除了选项，并将 SDL_K_COMMA 和 SDL_K_SEMI 分别更改为“,”和“;”。
谢谢。
下面是一些应该解析的例子：
CONSTANT block_node_size EQUALS 24;
CONSTANT Strcon EQUALS STRING "This is a string constant" PREFIX Jg$
#block_size = 24;
CONSTANT block_node_size EQUALS #block_size;
CONSTANT
xyz EQUALS 10,
alpha EQUALS 0,
noname EQUALS 63;
CONSTANT
(zyx, nameless) EQUALS 10,
(beta) EQUALS 1,
gamma EQUALS 42;
CONSTANT (
bits,
bytes,
words,
longs,
quads,
octas
) EQUALS 0 INCREMENT 1 PREFIX ctx$;
CONSTANT
(bad_block,bad_data,,,,
overlay,rewrite) EQUALS 0 INCREMENT 4;
CONSTANT (pli,c,bliss,macro)
EQUALS 4 INCREMENT 4 PREFIX lang$
COUNTER #lang;
CONSTANT (basic,pascal,fortran)
EQUALS #lang + 4 INCREMENT 4 PREFIX lang$;
希望对您有所帮助。
顺便说一句：这是用于此的 EBNF（某种程度上）：
/*
* Define the CONSTANT construct (Left out Expression).
*/
Str ::= "\"" Printable* "\""
Name ::= "$" | "_" | [A-Za-z] ("$" | "_" | [A-Z0-9a-z])*
Names ::= Name | ("(" Name ("," Name )* ")")
Constant_class ::= "EQUALS" (Expression Numeric_options | "STRING" Str
String_options)
String_options ::= Prefix? Tag?
Numeric_options ::= String_options Counter? Typename? Radix?
Increment_options ::= Increment? Numeric_options
Constant_list ::= Names "EQUALS" Expression Increment_options
Constant_set ::= Names Equals Expression
("," Names "EQUALS" Expression)*
Constant ::= "CONSTANT" (Name Constant_class | Constant_list |
Constant_set) ";"?
Prefix ::= "PREFIX" Str
Tag ::= "TAG" Str
Radix ::= "RADIX" ("DEC" | "OCT" | "HEX")
Counter ::= "COUNTER" Variable
Increment ::= "INCREMENT" Expression
Typename ::= "TYPENAME" Name
我想就是这样了。
我有点难以理解您实际想要做什么，所以我做了一些假设并在下面提供了一些备选方案。我希望它接近。
基本问题是语法规范中的歧义。其中一个可能只是一个错误：根据您的模板，EQUAL 的左侧似乎是单个 name 或 name 的逗号分隔列表s 被括号括起来。但是，您的语法允许 name 的逗号分隔列表，列表中的第一个（或唯一）项可能是带括号的名称列表：
constant_names
: constant_name
| constant_names ',' constant_name
| '(' constant_names ')
这将匹配 a、a, b、(a, b)、(a, b), c 和 (a, b), c, d。但我认为只有第一个和第三个是真正有意的。
无论如何，你有两个作品：
constant_style
: constant_name constant_class
| constant_list
对于第一个，我们有：
constant_class
: SDL_K_EQUALS sdl_decimal
而对于第二个，我们有：
constant_list: names_equal
names_equal
: constant_names SDL_K_EQUALS sdl_decimal
由于constant_name可以匹配单个name，所以有两种不同的方式来匹配answer = 42，难免会导致解析冲突
但是 answer = 42 还有另一种可能的解析：
constant_set
: names_equal
所以让我们从简化所有这些东西开始，然后我们也许可以回到（可能是）您最初的目标。这个想法是分解所有语法相似的东西：
constant-stmt : "CONSTANT" clause-list ';'
clause-list : clause | clause-list ',' clause
clause : left-hand-side "EQUALS" right-hand-side
left-hand-side : name | '(' name-list ')'
name-list : name | name-list ',' name
right-hand-side: expression /* See below */
我希望这一切足够简单易懂。
但我们可以从原文中看出（至少在某些情况下）right-hand-side 的选项比上面代码段中出现的要多得多。将其他语法添加到 right-hand-side 是微不足道的。但是，其意图似乎是这些额外选项仅在有单个子句的情况下可用。在那种情况下，我们可以这样做：
constant-stmt : "CONSTANT" constant-body ';'
constant-body : complex-clause | clause-list
clause-list : clause | clause-list ',' clause
clause : left-hand-side "EQUALS" right-hand-side
right-hand-side: expression
complex-clause : left-hand-side "EQUALS" complex-rhs
complex-rhs : expression numeric-options
| "STRING" string-literal string-options
但不幸的是，这又回到了歧义，因为 numeric-options 可能为空，所以 expression 将同时匹配 right-hand-side 和 complex-right-hand-side。
实际上，这种歧义并不重要。声明 name EQUALS expression 作为 CONSTANT 声明中的唯一声明或作为此类声明的列表之一之间没有语义差异。因此，一种可能性是忽略由此产生的 reduce/reduce 冲突，可能是通过将 %expect 1 放入文件中。但这真的不是很愉快。所以我们会尽量排除这个问题。
一种方法是坚持第一个 complex-rhs 至少有一个 numeric-option。但这真的很烦人。首先，我们必须创建另一种子句类型——first-complex-clause 或类似的类型——其次，我们必须写出至少存在一个选项的要求。
作为一个更简单的替代方案，我们可以只要求一个 clause-list 至少有两个 clause，而不是只有一个。由于每个 clause 也可以匹配 complex-clause，因此对 clause-list 的限制不会拒绝任何有效的 clause。所以这给了我们非常小的变化：
constant-body : complex-clause | clause-list
clause-list : clause ',' clause | clause-list ',' clause
附录
随着对预期语法的更精确描述（尽管仍然缺少一些细节），我修改了上面的语法以尝试解析完整的语言。基本原则保持不变：定义由单个 complex-clause（包括简单子句格）或至少两个简单 clause 的列表组成。唯一的区别是两种子句类型的定义方式。
我还修复了名单生成，以便可以省略个别名称（例如 (bad_block,bad_data,,,,overlay,rewrite)）。如指南中所述，该列表必须至少包含一个名称，这会使语法稍微复杂一些。
我添加了指南中的选项（但没有添加 EBNF 中的额外选项）。我没有尝试处理省略的分号，指南中似乎不允许分号，尽管有一个没有尾随分号的声明示例。 （这可能是一个错字。）据我所知，我添加了 expression 的定义。
我还添加了本地名称赋值语句，因为它在测试文件中并且很容易。
语法如下：
definition : %empty
| definition constant-defn
| definition local-assign
local-assign : LOCAL_NAME '=' expression ';'
constant-defn : "CONSTANT" constant-body ';'
constant-body : complex-clause | clause-list
clause-list : clause ',' clause | clause-list ',' clause
clause : name "EQUALS" expression
| name-list "EQUALS" expression
complex-clause : name "EQUALS" expression numeric-options
| name-list "EQUALS" expression list-options
| name "EQUALS" "STRING" string-literal string-options
| name-list "EQUALS" "STRING" string-literal string-options
name-list : '(' names ')'
names : optional-commas name | names ',' name | names ','
optional-commas : %empty | optional-commas ','
string-options : prefix-option tag-option
numeric-options : string-options counter-option typename-option
list-options : increment-option numeric-options
increment-option: %empty | "INCREMENT" expression
prefix-option : %empty | "PREFIX" prefix-name
tag-option : %empty | "TAG" tag-name
counter-option : %empty | "COUNTER" LOCAL_NAME
typename-option : %empty | "TYPENAME" name
expression : '-' expression %prec UNOP
| expression '*' expression
| expression '/' expression
| expression '+' expression
| expression '-' expression
| expression '@' expression
| expression '&' expression
| expression '!' expression
| '(' expression ')'
| INTEGER
| IDENT
| LOCAL_NAME
name : IDENT | QUOTED_IDENT
prefix-name : IDENT | QUOTED_NULL | QUOTED_IDENT
tag-name : IDENT | QUOTED_NULL | QUOTED_IDENT | QUOTED_TAG
string-literal : QUOTED_NULL | QUOTED_IDENT | QUOTED_TAG | QUOTED_STRING
您会看到我添加了对各种类型的引用字符串的区分，以便可以处理（大部分）引用字符串可能出现的不同上下文。如指南中所述，我没有将最多 4 个字符的带引号的字符串用作整数常量，因为我没有及时注意到它，也因为我无法通过简短阅读来弄清楚是否目的是允许在名称必须被引用的表达式中使用常量（因为名称与关键字冲突）；在那种情况下，在我看来，引号中包含四个或更少字符的名称存在歧义。
如果歧视的工作原理不明显（可能不是），这里是随附的 flex 定义：
id [[:alpha:]$_][[:alnum:]$_]*
%%
[[:space:]]+ ;
CONSTANT { return K_CONSTANT; }
COUNTER { return K_COUNTER; }
EQUALS { return K_EQUALS; }
INCREMENT { return K_INCREMENT; }
PREFIX { return K_PREFIX; }
STRING { return K_STRING; }
TAG { return K_TAG; }
TYPENAME { return K_TYPENAME; }
[#]{id} { yylval.str = strndup(yytext, yyleng); return LOCAL_NAME; }
{id} { yylval.str = strndup(yytext, yyleng); return IDENT; }
["]{id}["] { yylval.str = strndup(yytext+1, yyleng-2); return QUOTED_IDENT; }
["]["] { yylval.str = strndup(yytext+1, yyleng-2); return QUOTED_NULL; }
["][[:alnum:]$_]+["] { yylval.str = strndup(yytext+1, yyleng-2); return QUOTED_TAG; }
["][[:print:]]+["] { yylval.str = strndup(yytext+1, yyleng-2); return QUOTED_STRING; }
[[:digit:]]+ { yylval.dec = strtoul(yytext, 0, 0); return INTEGER; }
. { return *yytext; }
我通过 运行 对 OP 末尾的定义进行了相当不充分的测试（尽管我在第二行添加了尾随 ;）。我实际上并没有检查解析树是否正确，但它确实全部通过了解析器。