LBNF、C函数声明/定义、reduce减少冲突

Question

我试图在 LBNF 中表示 C/C++ 函数声明具有以下（近似）形式（<sym> 表示可选性，[rule] 是零或多个列表):

type ident ( [type <id>] );

虽然函数定义具有以下形式：

type ident ( [type id] ) { [stmt] }

目前，我有以下 LBNF：

entrypoints Program ;
Program.   Program ::= [TopDef] ;

FnDef.     TopDef ::= Type Ident "(" [Arg] ")" Block ;
FnDecl.    TopDef ::= Type Ident "(" [Par] ")" ";" ;
separator nonempty TopDef "" ;

Param.     Par ::= Type ;
NParam.    Par ::= Type Ident ;
separator Par "," ;

Arg.       Arg ::= Type Ident;
separator  Arg "," ;

-- Types ---------------------------------------------------

Int.       Type ::= "int" ;
--- more types...
separator  Type "," ;

这会按预期导致 reduce/reduce 冲突。有没有办法在解析器/词法分析器中解决这个问题？

我可以用下面的语法来解决：

FnDef.     TopDef ::= Type Ident "(" [Arg] ")" Block ;
FnDecl.    TopDef ::= Type Ident "(" [Arg] ")" ";" ;
separator nonempty TopDef "" ;

Arg.       Arg ::= Type Ident;
Arg.       Arg ::= Type;
separator  Arg "," ;

然后在类型检查器中检查函数定义是否具有每个参数的标识符，但这感觉不太令人满意...

这在 C 等语言中通常是如何处理的？

Answer 1

你提到的你觉得不满意的方式实际上是通常完成的方式。

但是你可以生成一个精确的 LALR(1) 文法。这是一个完整的没有冲突的野牛规范：

%token TYPE ID
%%
prog       : 
           | prog decl ';'
decl       : TYPE ID def_list block
           | TYPE ID def_list ';'
           | TYPE ID dec_list ';'
block      : '{' prog '}'
def_list   : '(' ')'
           | '(' type_ids ')'
dec_list   : '(' type_opt_ids ')'
type_opt_id: type_only
           | type_id
type_ids   : type_id
           | type_ids ',' type_id
type_opt_ids
           : type_only
           | type_ids ',' type_only  /* SEE BELOW */
           | type_opt_ids ',' type_opt_id
type_id    : TYPE ID
type_only  : TYPE

关键是要避免强制解析器做出决定。当它传递参数列表时，它可以继续减少 type_opt_ids 只要它不命中匿名参数。如果它命中一个，它会减少一个 type_ids 并继续处理其余参数，无论它们是否是匿名的。最后，定义只允许 type_ids 但声明（明确地）接受任何一个。

为了实现这一点，type_id 和 type_only 的语义类型需要相同，因为 type_ids 和 type_opt_ids 必须是类型。否则，您需要在标有 /* SEE BELOW */

的作品中将 type_ids 转换为 type_opt_ids

（很抱歉没有将其转换为您的形式主义，但我想用 bison 对其进行测试以验证它实际上没有冲突。转换应该很容易。）

请注意，C++ 很乐意允许没有参数名称的函数定义，但 C 不是。另一方面，C 允许没有类型的函数定义，或者在参数名称列表和函数体之间使用类型声明。但这是一个附带问题，真的。

LBNF、C函数声明/定义、reduce减少冲突

LBNF, C function declaration / definition, reduce reduce conflict

c

c++

bnf

context-free-grammar

bnfc