0

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

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

  1. 等价<=>和暗示=>，
  2. 连词&与析取|
  3. 否定-和
  4. 原子。

级别越高，越早被解析。

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

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 个减少/减少冲突，但在递归定义中这些冲突不是不可避免的吗？

4

1 回答 1

3

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

我还通过消除其中一个产品来修复减少/减少冲突NOT。见下文。

（我希望我的 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。这允许规则匹配以括号开头的表达式而不匹配语法。）ANDORrPAREN

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

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

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

在@IraBaxter对Grammar的回答中可以找到一种使用较少单位产生的变体方法，用于不允许外括号的表达式。

边注：

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

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

于 2020-04-15T15:03:44.827 回答