解决 C 风格块语句中可选换行符的 shift-reduce 冲突

Question

我想为 C 中块语句的简化版本创建一个语法规则，它匹配括号中的语句列表，在开头和结尾有可选的换行符。这种语言的语句以换行符结束。

可选的换行符使块语句可以跨越多行和单行。即，

{ statement }

和

{
    statement
}

应该支持

目前我的规则如下：

BlockStmt:
    '{' OptionalNewlines BlockStmtList OptionalNewlines '}';


OptionalNewlines:
        OptionalNewlines '\n'
    |   %empty;

还支持空块，它们基本上是只有换行符且没有语句的块。这是可能的，因为 BlockStmtList 可以减少到 %empty。

然而，对于只有换行符的空块，这会导致 shift-reduce 冲突，因为换行符可以通过非终结符的开头和结尾 OptionalNewlines 匹配。

在只有换行符的空块的情况下，我如何告诉 yacc 优先考虑 OptionalNewlines 之一？

Answer 1

除非你对块中间的空行有问题——这是我们很多人喜欢做的——简单的解决方案是只允许空语句（即只包含换行符。如果你这样做，你可以不用担心可选的换行符，只需使用

BlockStmt: '{' BlockStmtList '}';

这无疑是最简单的。但如果它不适合您，请继续阅读。

一般来说，您不能有一个可选列表序列，其中两个列表具有相同的元素。这会导致歧义：如果您的语法允许 a* b* a*（为简单起见使用 Kleene *）并且输入是 a，则无法知道空的 a* 是在之前还是之后空 b*。 “可选”元素在很多情况下都是有问题的；通常需要使用非可选元素将空的非终结符扩展为多个规则：

BlockStmt: '{' '}'
         | '{' NewLineList '}'
         | '{' NewLineList StmtList OptionalNewLineList '}'
         | '{' StmtList OptionalNewLineList '}'

解决 C 风格块语句中可选换行符的 shift-reduce 冲突

Solve shift-reduce conlict for optional newlines in C-style block statement

parsing

yacc

bison