通过递归下降从该语法生成​​表达式

Question

我有一个简单的语法。实际上，我使用的语法更复杂，但这是说明我的问题的最小子集。

Expr ::= Value Suffix
       | "(" Expr ")" Suffix

Suffix ::= "->" Expr
         | "<-" Expr
         | Expr
         | epsilon

Value 匹配标识符、字符串、数字等。 Suffix 规则是为了消除左递归。这匹配如下表达式：

a -> b (c -> (d) (e))

也就是说，一个图形，其中 a 既转到 b 又转到 (c -> (d) (e)) 的结果，c 转到 d 和 e。我试图为这些表达式生成一个抽象语法树，但我遇到了困难，因为所有运算符都可以接受任意数量的操作数。我宁愿将生成 AST 的逻辑保留在递归下降解析方法中，因为它避免了重复提取表达式的逻辑。我当前的策略如下：

1. 如果出现Value，则将其推送到输出。

2. 如果出现From或To：

   1. 输出分隔符。

   2. 获取下一个Expr。

   3. 创建一个Link节点。

   4. 将输出中的第一组操作数弹出到 Link 中，直到出现分隔符。

   5. 擦除发现的分隔符。

   6. 将第二组操作数弹出到Link中，直到出现分隔符。

   7. 将Link推送到输出。

如果我在不遵守步骤 2.3–2.7 的情况下运行此操作，我会得到一个值和分隔符的列表。对于上面引用的表达式，a -> b (c -> (d) (e))，输出应该是：

A sep_1 B sep_2 C sep_3 D E

应用 To 规则将产生：

A sep_1 B sep_2 (link from C to {D, E})

随后：

(link from A to {B, (link from C to {D, E})})

需要注意的重要一点是 sep_2，对于分隔第二个 -> 的左侧操作数至关重要，没有出现，因此解析器认为该表达式实际上是编写的：

a -> (b c -> (d) (e))

为了解决这个问题根据我当前的策略，我需要一种在相邻表达式之间生成分隔符的方法，但前提是当前表达式是括在括号中的 From 或 To 表达式。如果可能的话，那么我只是没有看到它，答案应该很简单。但是，如果有更好的方法来解决这个问题，请告诉我！

Answer 1

我没有尝试详细分析它，但是：“From 或 To 表达式用括号括起来”开始听起来很像“上下文相关”，递归下降无法直接处理。为了避免上下文依赖，您可能需要单独产生括号中的 From 或 To 与 From 或 To< /code> 不带括号。

编辑：虽然可能为时已晚，做任何好事，如果我对你想要匹配的内容的理解是正确的，我想我会写得更像这样：

Graph := 
       | List Sep Graph
       ;

Sep := "->"
     | "<-"
     ;

List :=
      | Value List
      ;

Value := Number 
      | Identifier 
      | String 
      | '(' Graph ')'
      ;

很难确定，但我认为这至少应该是接近匹配（仅）您想要的输入，并且应该可以相当容易地生成正确反映输入的 AST。