12

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

这是我的解析器语法：

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

我怎样才能使这个语法左结合？我是这方面的新手，请你告诉我在哪里可以找到更多信息的来源？我可以使用递归下降解析器来实现这一点吗？

4

1 回答 1

13

看看Theodore Norvell的 Recursive Descent 解析表达式

在那里，他给出了解决问题的三种方法。
1.调车场算法。
2.通过分解语法的经典解决方案。
3.优先攀登

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

Exrp: 项 { [+-] Expr} | 学期

注意{ }周围的添加[+-] Expr表明它们应该一起解析并且可以有0个或更多。

同样默认情况下，您将树构建为

  -
 / \
2   +
   / \
  1   1

IE-(2,+(1,1))

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

     +
    / \
   -   1
  / \
 2   1

IE+(-(2,1),1)

由于本文中有三种方法可以做到这一点，因此我不会在此处对其进行扩展。你还提到你是新手，所以你应该得到一本好的编译器书来了解你在阅读这篇论文时会遇到的细节。这些方法中的大多数都是用常见的编程语言实现的，并且可以在 Internet 上免费获得，但请注意，许多人会做你所做的事情并发布错误的结果。

检查您是否正确的最佳方法是使用多个减法运算序列进行这样的测试：

7-3-2 = 2

如果你得到

7-3-2 = 6 或其他

那么这是错误的。

于 2013-12-02T13:22:21.533 回答