解析具有未定义数量的参数的表达式

Question

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

# 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 -> *德-> * # fg * #

然而，合并文本标记和其他任何内容似乎是有问题的。 我的想法是创建标记令牌 (M)，因此 RPN 看起来像：

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

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

也就是说：

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

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

谢谢你的帮助。

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

Answer 1

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

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

# a * b c d

以下三个表达式中哪一个是规范形式？

1. (a，*(b，c，d))

2. (a, *(b, c), d)

3. (a, *(b), c, d)

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

现在我想起来了，我所知道的编程语言都不支持带有可变数量参数的运算符，而只支持函数/过程，这可能并非纯属偶然。