如何递归解析表达式？

Question

我在写一门小语种，真的卡在了表达式解析上。我写了一个 LR 递归下降解析器，它可以工作，但现在我需要解析表达式，我发现它真的很困难。我没有定义语法，但如果它有帮助，即使没有语法，我也有点了解它是如何工作的。目前，我的表达式结构如下所示：

typedef struct s_ExpressionNode {
    Token *value;
    char expressionType;

    struct *s_ExpressionNode lhand;
    char operand;
    struct *s_ExpressionNode rhand;
} ExpressionNode;

我试图让它解析如下内容：

5 + 5 + 2 * (-3 / 2) * age

我正在阅读有关如何解析表达式的 this 文章。我尝试实现的第一个语法但效果不太好，然后我注意到第二个语法，它似乎删除了左递归。但是，我一直在尝试实现它，因为我不明白 P、B 是什么意思，而且 U 是 - 但 - 也适用于 B？我也不确定 expect(end) 是什么意思。

Answer 1

在您链接的文章的 "Recursive-descent recognition" 部分中，E、P、B 和 U 是非终端符号在呈现的表达式语法中。从他们在文中的定义，我推断 "E" 被选为 "expression" 的助记词， "P" 被选为 "primary" 的助记词， "B" 被选为 [=38] 的助记词=]，"U" 对应 "unary (operator)"。鉴于这些特征，应该清楚终端符号“-”可以简化为 U 或 B，具体取决于上下文：

unary:   -1
binary: x-1

文中描述的expect()函数用于在下一个token恰好为指定类型时消费，否则抛出错误。 end 标记被定义为表示输入结束的合成标记。于是

expect(end)

表示期望表达式中不再有要处理的标记，如果不满足该期望，其给定的实现将抛出错误。

所有这些都在文本中，除了选择特定符号 E、P、B 和 U 的原因。如果您在阅读文本时遇到问题，那么您可能需要搜索更简单的内容。

如何递归解析表达式？

How to recursively parse an expression?

c

recursion

parsing