语法与运算符结合性之间的关系

一些编译器书籍/文章/论文谈论语法的设计及其运算符的结合性的关系。我是自上而下的忠实粉丝，尤其是递归下降、解析器，到目前为止我编写的大多数（如果不是全部）编译器都使用以下表达式语法：

Expr   ::= Term { ( "+" | "-" ) Term }
Term   ::= Factor { ( "*" | "/" ) Factor }
Factor ::= INTEGER | "(" Expr ")"

这是该 BNF 的 EBNF 表示：

Expr  ::= Term Expr'
Expr' ::= ( "+" | "-" ) Term Expr' | ε
Term  ::= Factor Term'
Term' ::= ( "*" | "/" ) Factor Term' | ε
Factor = INTEGER | "(" Expr ")"

根据我读到的内容，有些人认为这个语法是“错误的”，因为运算符结合性的变化（这 4 个运算符从左到右）通过向右而不是向左生长的解析树证明。对于通过属性语法实现的解析器，这可能是正确的，因为 l 属性值要求首先创建该值，然后传递给子节点。然而，当使用普通的递归下降解析器实现时，由我决定是先构造这个节点然后传递给子节点（自上而下）还是先创建子节点然后将返回值添加为该节点的子节点（传递在此节点的构造函数中）（自下而上）。这里应该有一些我想念的东西，因为我不同意这种语法是“错误的”并且这种语法已经在许多语言中使用的说法，尤其是。维尔西安的。通常（或全部？）阅读说它促进 LR 解析而不是 LL。

我认为这里的问题是一种语言有一个抽象语法就像：

E ::= E + E | E - E | E * E | E / E | Int | (E)

但这实际上是通过具体语法它用于指定关联性和优先级。因此，如果您正在编写一个递归的体面解析，那么您将在进行过程中隐式地将具体语法写入其中，这很好，尽管将其精确地指定为短语结构语法可能会更好！

如果你的语法是一个成熟的具体语法，那么它有几个问题。首先，您需要添加产生式以“转到下一个级别”，因此稍微放松您的语法：

Expr ::= Term + Term | Term - Term | Term
Term ::= Factor * Factor | Factor / Factor | Factor
Factor ::= INTEGER | (Expr)

否则，无法从起始符号（在本例中为 Expr）开始导出有效的句子。例如，如果没有这些额外的产生式，您将如何导出“1 * 2”？

Expr -> Term
     -> Factor * Factor
     -> 1 * Factor
     -> 1 * 2

我们可以看到其他语法以稍微不同的方式处理这个问题：

Expr -> Term Expr'
     -> Factor Term' Expr'
     -> 1 Term' Expr'
     -> 1 * Factor Term' Expr'
     -> 1 * 2 Term' Expr'
     -> 1 * 2 ε Expr'
     -> 1 * 2 ε ε
      = 1 * 2

但这达到了相同的效果。

您的解析器实际上是非关联的。要查看此内容，请询问如何E + E + E会被解析并发现它不能。任何+首先被消耗，我们得到E一侧和E + E另一方面，但随后我们尝试解析E + E as a Term这是不可能的。同样，考虑从起始符号导出该表达式，这也是不可能的。

Expr -> Term + Term
     -> ? (can't get another + in here)

另一种语法是左关联 ebcase 任意长的字符串E + E + ... + E可以推导出来。

所以无论如何，总而言之，你是对的，在编写 RDP 时，你可以实现任何concrete的版本abstract你喜欢的语法，并且你可能比我更了解它。但是，当尝试生成精确描述 RDP 的语法时，会出现这些问题。希望有帮助！