表达式解析器语法和左关联性

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

我怎样才能使这个语法保持联想？我是新手,请你告诉我哪里可以找到更多信息？我可以用递归下降解析器实现这一点吗？

Answer 1

看看Theodore Norvell的递归下降解析表达式

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

你的问题源于你的语法需要多次改变,一个例子就是

Exrp:Term {[+ - ] Expr} | 术语

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

此外,默认情况下,您将树构建为

  -
 / \
2   +
   / \
  1   1

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

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

     +
    / \
   -   1
  / \
 2   1

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

由于本文有三种方法可以做到这一点,所以我不会在这里进行扩展.另外你提到你是新手,所以你应该得到一本好的编译器书,以了解你将在阅读论文时遇到的细节.这些方法中的大多数都是以通用编程语言实现的,并且可以在互联网上免费获得,但请注意,许多人会按照您的方式执行操作并发布错误的结果.

检查你是否正确的最佳方法是使用多个减法操作序列进行这样的测试:

7-3-2 = 2

如果你得到

7-3-2 = 6或其他

那是错的.