表达式解析器文法和左结合性

Question

我一直在尝试创建一个带有变量的表达式解析器，并将它们简化为二次方程式的形式。

这是我的解析器语法：

Exercise : Expr '=' Expr
Expr : Term [+-] Expr | Term
Term : Factor [*/] Term | Factor
Factor: Atom [^] Factor | Atom
Atom: Number | Identified | [- sqrt] Atom | '(' Expr ')'

我使用自顶向下递归分析器进行解析。假设我想解析这个表达式：

" 2 - 1 + 1 = 0"

但结果是0，分析器创建了错误的树形结构：

  -
 / \
2   +
   / \
  1   1

我该如何使这个语法是左结合的？我是新手，请问有哪些资源可以提供更多信息给我？我可以用递归下降解析器来实现吗？

- Martin Bodocky

Answer 1

请参阅Theodore Norvell的《递归下降解析表达式》（Parsing Expressions by Recursive Descent）链接，他在其中提供了三种解决问题的方法：
1. Shunting yard算法
2. 通过重组语法的经典解法
3. 优先级爬升算法

你们的问题源于语法需要进行多次更改，例如：

Expr: Term { [+-] Expr} | Term

请注意在[+-] Expr周围添加了{ }，这表示它们应该一起解析，并且可以有0个或多个。
此外，默认情况下，您正在构建如下树形结构

  -
 / \
2   +
   / \
  1   1

也就是说，-(2,+(1,1))

当您应该为与左关联运算符具有相同优先级的运算符构建树时

     +
    / \
   -   1
  / \
 2   1

即 +(-(2,1),1)

由于在论文中有三种方法，我不会在这里进行详细介绍。此外，你提到你是新手，因此你应该阅读一本好的编译器书籍以了解你在阅读论文时可能遇到的细节。大多数这些方法都已经实现在常见的编程语言中并且可以免费在互联网上获得，但要注意许多人会像你一样发布错误的结果。

检查是否正确的最佳方法是使用以下测试，使用多个减法操作序列：

7-3-2 = 2

如果你得到

7-3-2 = 6 或其他结果

那么就是错误的。

- Guy Coder

---

你能跟我分享一些好的例子吗？我已经用Haskell实现了这个功能。根据这个教程 https://www.fpcomplete.com/school/starting-with-haskell/basics-of-haskell/8_Parser，作者提到语法有问题，但是我认为通过优先级调整，已经修复了它。我需要实现加减乘除的左结合性和乘方、负数和平方根的右结合性。我需要一些在任何编程语言中的示例。 - Martin Bodocky

我更新了我的Github示例以处理结合性。 - Guy Coder

@Apalala 很好的发现。 - Guy Coder