0

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

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出现 a，将其推送到输出。

  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))

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

4

1 回答 1

1

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

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

Graph := 
       | List Sep Graph
       ;

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

List :=
      | Value List
      ;

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

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

于 2010-09-24T15:22:44.557 回答