对于在 returns 字符串的规则中包含 %empty 的替代方案，正确的操作是什么？

Question

我的 Bison 文件中的每个非终端——文档、消息、消息——returns一个字符串：

%union
{
  char *strval;
}

%type <strval> document messages message

我的输入文件包含零条或多条消息，每条消息后跟一个换行符 (EOL)：

messages: message EOL messages      { $$ = strcat(, ); }
 | %empty                           { $$ = ???; }
;

我不知道对 %empty 部分使用什么操作。我尝试了很多东西。我尝试返回空字符串：

{ $$ = ''; }

导致此错误消息：

message.y: In function 'yyparse':
message.y:25:56: error: empty character constant
   25 |  | %empty                           { $$ = ''; }

我尝试返回一个 space 字符：

{ $$ = ' '; }

导致此错误消息：

message.y: In function 'yyparse':
message.y:25:54: warning: assignment to 'char *' from 'int' makes pointer from integer without a cast [-Wint-conversion]
   25 |  | %empty                           { $$ = ''; }

我尝试转换为字符：

{ $$ = char(' '); }

导致此错误消息：

message.y: In function 'yyparse':
message.y:26:56: error: expected expression before 'char'
   25 |  | %empty                           { $$ = ''; }

哎呀！我没主意了。对于在 returns 字符串的规则中包含 %empty 的替代项，正确的操作是什么？

Answer 1

您可以 return 空字符串 ("") 或 NULL.

我推荐 NULL，因为我不喜欢将字符串文字赋予类型 char*，因为它们往往指向常见编译策略中的只读内存（即重新定位到部分中）在运行时映射到只读页面）。所以理想的类型是 const char* 但这与你的代码的其余部分不一致。另一种策略是堆分配一个空字符串 (strdup(""))，但这感觉很浪费（并且需要随后释放，即使它是一个中介，其内容将被串联操作复制）。所以我会选择 NULL 和一些逻辑来测试它。

您经常会看到将令牌的基础值显式复制到堆中的解析器操作代码。

您的代码看起来很可疑，因为它使用 strcat 将结果写入第一个参数（目标）的末尾，而 return 是第一个参数。因此，您需要知道参数足够大（通过分配一个足够大的新堆分配来存储两者，然后复制第一个字符串的内容，然后 strcat'ing 第二个到最后） .

这种模式在 LR 解析中经常出现。考虑以下语法，它解析一个可能为空的整数列表：

L -> ε.
L -> int L.

在C语言中，如果使用链表，一般将空表识别为NULL。所以动作变成（伪代码）：

L -> ε { $$ = NULL; }
L -> int L {
  struct list* l = malloc(sizeof(struct list));
  l->value = ; // store value
  l->next = ; // store the tail of the list
  $$ = l;
}

列表数据结构是反向构建的（因为LR是自下而上进行归约的）。不同之处在于您的代码不会通过先前减少的结果（ L -> int L 生产右侧的非终结符 L 间接存储在它正在构建的内容中，它连接它。

我建议您执行以下操作（引入 message 的假定定义）：

// copies string contents to heap
message: IDENT { $$ = strdup(); }

messages: message EOL messages {
  if ( == NULL) {
    // no concatenation required
    $$ = ;
  } else {
    // allocate space for both
    char* both = realloc(, strlen() + strlen() + 1);
    $$ = strcat(both, );
    free();
  }
}
| %empty { 
  $$ = NULL;
}
;

这应该符合您的预期。它为连接的字符串创建一个新的分配，将已经减少的连接 (</code>) 复制到新分配的末尾（以 <code> 为前缀），然后释放已经减少的连接 (</code>).</p> <p>这是减少步骤的概念化：</p> <pre><code>foo EOL (bar EOL (baz EOL ε))

=>

foo EOL (bar EOL (baz EOL ε))
=>
foo EOL (bar EOL "baz")
=>
foo EOL "barbaz"
=>
"foobarbaz"

尽管从我使用括号可以看出嵌套，但这与 LR 堆栈在解析期间的显示方式非常接近（不包括 epsilon 规则的显式外观；减少 - 产生 NULL - 将如果当前前瞻属于 FOLLOW(messages)).

对于在 returns 字符串的规则中包含 %empty 的替代方案，正确的操作是什么？

What is the correct action to use for an alternative containing a %empty in a rule that returns a string?

bison

flex-lexer

yacc

lex