禁止 BNFC 语法中不必要的最外层括号

Question

这是 this 我之前提出的关于命题逻辑的 BNFC 文法的问题的延续。根据定义，我用括号工作，但我现在想扩展语法以在没有括号的情况下工作，但是有一个问题：不允许使用不必要的外括号。

比如原子句a应该被允许，但是(a)不应该被识别。句子 (a => b) & c 也应该被允许，但 ((a => b) & c) 则不允许，等等。最后一个例子强调了paretheses 的必要性。优先级为

等价<=>和蕴涵=>,
合取 & 和析取 |
否定-和
原子。

等级越高越早解析

通过递归为不同的运算符设置优先级，我得到了使用不必要的括号的语法：

IFF     .   L     ::=   L   "<=>" L1  ;
IF      .   L     ::=   L   "=>"  L1  ;
AND     .   L1    ::=   L1  "&"   L2  ;
OR      .   L1    ::=   L1  "|"   L2  ;
NOT     .   L2    ::=       "-"   L3  ;
NOT2    .   L2    ::=       "-"   L2  ;
P       .   L3    ::=   Ident         ;

_       .   L     ::=   L1            ;
_       .   L1    ::=   L2            ;
_       .   L2    ::=   L3            ;
_       .   L3    ::=   "(" L ")"     ;

现在的问题是，我如何不允许外括号，这是由最后一条规则L3 ::= "(" L ")";引起的？在表达式中允许括号是绝对必要的，但它也允许在边缘使用括号。我想我需要一些额外的规则来消除歧义，但那会是什么样子呢？

此语法还会导致大约 6 个 reduce/reduce 冲突，但在递归定义中这些冲突不是不可避免的吗？

Answer 1

您可以通过简单地从顶层禁止带括号的形式来做到这一点。这需要以不同的方式编写优先级层次结构，以便通过层次结构传播限制。在下文中，r 后缀表示产生式被“限制”为不是括号形式。

我还通过消除 NOT 作品之一解决了 reduce/reduce 冲突。见下文。

（我希望我的 BNFC 是正确的。我是用 bison 写的，然后尝试转换语法。）

_       .   S     ::=   L0r             ;

IFF     .   L0r   ::=   L0 "<=>" L1     ;
IF      .   L0r   ::=   L0 "=>"  L1     ;

AND     .   L1r   ::=   L1 "&"   L2     ;
OR      .   L1r   ::=   L1 "|"   L2     ;

NOT     .   L2r   ::=       "-"   L2    ;
ID      .   L2r   ::=   Ident           ;                                            

PAREN   .   L3    ::=   "(" L0 ")"      ;

_       .   L0r   ::=   L1r             ;
_       .   L1r   ::=   L2r             ;

_       .   L0    ::=   L0r             ;
_       .   L1    ::=   L1r             ;
_       .   L2    ::=   L2r             ;

_       .   L0    ::=   L3              ;
_       .   L1    ::=   L3              ;
_       .   L2    ::=   L3              ;

(编辑：我通过删除限制更改了 IFF、IF、AND 和 OR 规则 ( r) 来自第一个参数。这允许规则匹配以括号开头的表达式，而不匹配 PAREN 语法。）

如果您还想禁止多余的内部括号（如 ((a & b))），您可以将 PAREN 规则更改为

PAREN   .   L3    ::=   "(" L0r ")"     ;

这将使 L0 规则变得不必要。

可以在 @IraBaxter to 的答案中找到使用较少单位产品的变体方法。

旁注：

This grammar also results in about 6 reduce/reduce conflicts, but aren't those pretty much inevitable in recursive definitions?

不，递归语法可以而且应该是明确的。 Reduce/reduce 冲突并非不可避免，而且几乎总是表明语法存在问题。在这种情况下，它们是一元 NOT 运算符的冗余产生式的结果。有两个不同的非终端都可以接受 "-" L3 显然会导致歧义，而歧义总是会产生解析冲突。

禁止 BNFC 语法中不必要的最外层括号

Disallowing unnecessary outermost brackets in a BNFC-grammar

grammar

parsing

context-free-grammar

bnfc

旁注：