0

我正在尝试为类 C 语言编写 LBNF/BNFC 语法。在 C 语言中，有许多可能的修饰符，您可能会或可能不会在声明前写入（如inline、const等volatile）。

我正在尝试编写语法以重用代码并使生成的 Haskell AST 易于使用。类型的语法可能如下所示：

rule TypeName ::= "bool" | "int" | "double" | "void" | Id ;

Type. Type ::= TypeQualifier TypeName;

ConstModifier.    TypeModifier ::= "const" ;
VolatileModifier. TypeModifier ::= "volatile" ;
NoModifier.       TypeModifier ::= ;

对于函数声明，它可能如下所示：

Fun. Fun ::= FunModifier Type Id "(" [Param] ")" ";" ;

InlineModifier. FunModifier ::= "inline" ;
NoFunModifier.  FunModifier ::= ;

问题是由于这些可选前缀，我得到了大量的移位/减少，有时甚至减少/减少冲突。避免这些冲突的替代语法可能如下所示：

NotInlinedFun. Fun ::= Type Id "(" [Param] ")" ";" ;
InlinedFun.    Fun ::= "inline" Type Id "(" [Param] ")" ";" ;

或者

NotInlinedFun. Fun ::= FunRest
InlinedFun.    Fun ::= "inline" FunRest;

FunRest.   FunRest ::= Type Id "(" [Param] ")" ";" ;

这导致了这样的 Haskell AST：

data Fun = AFun FunRest | BFun FunRest | CFun FunRest
data FunRest = FunRest Type Id [Param]

而不是更吸引人

data Fun = Fun Modifier Type Id [Param]
data Modifier = A | B | C

您可以看到这如何迅速导致规则组合爆炸或使用不愉快的 Haskell AST。

我怎样才能最好地避免这些冲突？

4

1 回答 1

1

当你在 a 之前什么都看不到时int，你不知道什么是没有变量修饰符还是没有函数修饰符，正是因为你还不知道是int指变量还是 a 的返回值功能。因此，如果解析器只使用一个前瞻标记，您必须避免强迫它做出决定。

无中生有地制造一个非终结符是一种强制解析器决定正在检查哪种无的形式，因此也必须避免这种情况。但这不是唯一的例子。例如，如果您包含static，您会发现尝试将其分类为变量修饰符或函数修饰符会导致相同的（减少/减少）冲突。

但无论如何，真正的 C 语法更微妙。例如，以下是合法的：

static inline const int* extract(int arg);

这是这样的：

/* The second const is irrelevant to this discussion. */
volatile const unsigned char* const reg = 0x01A4;

所以一个声明可以有很多限定符，而不仅仅是零或一。在某些情况下，重复会产生影响：

long long very_wide;

在其他情况下，它不会：

inline inline int f(void);

虽然这些约束可以表示为上下文无关语法，但我从未见过这样做过；正如你所说，指数爆炸是无法控制的。正如 C 标准中描述的那样，实际的 C 语法并没有尝试这个壮举；它只是允许声明包含可能重复的声明说明符的任意顺序（参见第 6.7 节），然后强制语义分析区分正确和不正确的序列。

于 2019-05-01T01:14:33.703 回答