对于在 returns 字符串的规则中包含 %empty 的替代方案,正确的操作是什么?
What is the correct action to use for an alternative containing a %empty in a rule that returns a string?
我的 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
的替代项,正确的操作是什么?
您可以 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)
).
我的 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
的替代项,正确的操作是什么?
您可以 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)
).