bison - Bison shift/reduce 和 reduce/reduce 冲突

Question

好的，我现在已经尝试重写此 Bison 语法 3 次，并且一直遇到 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, 
                . 
                . 
                . 
 ;

我在让最后三个全部工作时遇到问题。我可以让其中任何一个工作，但不是所有四个。我现在有一个班次/减少和一个减少/减少冲突。我的语法如下：

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
    ;

我认为这些名称是自我记录的（至少您应该能够理解类型）。任何帮助将不胜感激。我有一种感觉，要么简化太多，要么不够简化。

注意：我想出了如何编辑我的帖子并删除了选项并将 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

我想就是这样。

score 3 · Accepted Answer

我有点难以理解你实际上想要做什么，所以我做了一些假设并在下面提供了一些替代方案。我希望它会接近。

基本问题是语法规范中的歧义。其中一个可能只是一个错误：根据您的模板，左手边EQUAL似乎是单个或用括号括起来name的逗号分隔的s 列表。name但是，您的语法允许以逗号分隔的names 列表，列表中的第一个（或唯一一个）项目可能是带括号的名称列表：

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-sideand complex-right-hand-side。

在实践中，这种模糊性并不重要。name EQUALS expression声明作为声明中的唯一CONSTANT声明或作为此类声明列表之一之间没有语义差异。因此，一种可能性是忽略由此产生的减少/减少冲突，可能通过放入%expect 1文件中。但这真的不是很令人愉快。所以我们会尽量消除这个问题。

一种方法是坚持第一个complex-rhs至少有一个numeric-option。但这真的很烦人。首先，我们必须创建另一种子句类型——first-complex-clause或类似的类型——其次，我们必须写出至少存在一个选项的要求。

作为一个更简单的替代方案，我们可以只要求 aclause-list至少有两个clauses，而不仅仅是一个。由于 eachclause也可以匹配complex-clause，限制clause-list不会拒绝任何有效clause的。所以这给了我们非常小的变化：

constant-body  : complex-clause | clause-list
clause-list    : clause ',' clause | clause-list ',' clause

附录

通过对预期语法的更精确描述（尽管仍然缺少一些细节），我修改了上述语法以尝试解析完整的语言。基本原则保持不变：定义由单个complex-clause（包括简单子句案例）或至少两个简单clauses 的列表组成。唯一的区别是定义这两种子句类型的方式。

我还修复了名称列表生成，以便可以省略单个名称（例如。(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 末尾使用定义运行它，我做了一个相当不充分的测试（尽管我;在第二行添加了尾随）。我实际上并没有检查解析树是否正确，但它确实都通过了解析器。

bison - Bison shift/reduce 和 reduce/reduce 冲突

1 回答 1

附录

Related

Reference