2

我正在尝试将自制语言中的字符串解析为一种树，例如：

# a * b1 b2 -> c * d1 d2 -> e # f1 f2 * g

应该导致：

# a
  * b1 b2
    -> c
  * d1 d2
    -> e
# f1 f2
  * g

#、* 和 -> 是符号。a、b1 等是文本。

从那一刻起，我只知道评估表达式的 rpn 方法，我目前的解决方案如下。如果我在每个符号之后只允许一个文本标记，我可以很容易地将表达式首先转换为 RPN 表示法（b = b1 b2；d = d1 d2；f = f1 f2）并从这里解析它：

abc -> * de -> * # fg * #

然而，合并文本标记和其他任何东西似乎是有问题的。我的想法是创建标记令牌（M），所以 RPN 看起来像：

a M b2 b1 M c -> * M d2 d1 M e -> * # f2 f1 M g * #

这也是可解析的，似乎可以解决问题。

那说：

  1. 有没有人有类似的经验并且可以说它是或不是未来可行的解决方案？
  2. 是否有更好的方法来解析具有未定义的运算符数量的表达式？
  3. 你能指点我一些好的资源吗？

笔记。是的，我知道这个例子非常类似于 Lisp 前缀表示法，也许要走的路是添加一些括号，但我在这里没有任何经验。但是，源文本不得包含任何人工括号，而且我不确定如何处理潜在的中缀混合，如 # a * b -> [if value1 = value2] c -> d。

谢谢你的帮助。

编辑：似乎我正在寻找的是带有可变数量参数的后缀表示法的来源。

4

1 回答 1

3

我无法完全理解您的问题，但您似乎想要的是语法定义和解析器生成器。我建议您看一下ANTLR，它应该非常简单，可以为您的原始语法或 RPN 定义语法。

编辑：（在进行自我批评并努力理解问题细节之后。）实际上，您的示例中的语言语法并不清楚。但是，在我看来，前缀/后缀表示法的优点（即您既不需要括号也不需要优先级感知解析器）源于您每次遇到运算符时都知道参数的数量，因此您确切知道要读取多少个元素（对于前缀表示法）或从堆栈中弹出多少个元素（对于后缀表示法）。OTOH，我相信拥有可以具有可变数量参数的运算符使得前缀/后缀符号不仅难以解析，而且完全模棱两可。以下面的表达式为例：

# a * b c d

以下哪三个是规范形式？

  1. （A B C D））

  2. （A B C D）

  3. （A B C D）

如果不了解更多关于运营商的信息，则无法分辨。当然，您可以定义某种贪婪的运算符，例如 * 比 # 更贪婪，因此它会吞噬所有参数。但这会超出前缀符号的目的，因为您根本无法写下上述三个变体中的第二个变体；并非没有额外的句法元素。

现在我想起来了，我所知道的编程语言都不支持具有可变数量参数的运算符，只有functions/procedures ，这可能不是绝对的机会。

于 2009-03-18T11:12:25.957 回答