代码之家 › 专栏 › 技术社区 › Jon Purdy

用递归下降法从该语法生成表达式

recursive-descent graph language-agnostic parsing

0

Jon Purdy · 技术社区 · 14 年前

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

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的逻辑,因为它避免了重复提取表达式的逻辑。我目前的策略如下:

如果A 价值 出现,将其推到输出。
如果A From 或 To 出现:
1. 输出一个分隔符。
2. 接下一个 Expr .
3. 创建 Link 节点。
4. 将第一组操作数从输出中弹出到 链接 直到出现分隔符。
5. 清除发现的分隔符。
6. 将第二组操作数弹出到 链接 直到一个分隔符。
7. 推动 链接 输出。

如果我在不遵循步骤2.3-2.7的情况下运行这个过程,我会得到一个值和分隔符的列表。对于上面引用的表达式, a -> b (c -> (d) (e)) ,输出应为:

A sep_1 B sep_2 C sep_3 D E

应用 到 然后规则将产生:

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

为了用我当前的策略解决这个问题,我需要一种在相邻表达式之间生成分隔符的方法,但前提是当前表达式是 从 或 到 用括号括起来的表达式。如果可能的话,那我就是看不到,答案应该很简单。但是,如果有更好的方法来解决这个问题,请告诉我!

1 回复 | 直到 14 年前

1

Jerry Coffin 14 年前

我没有详细分析过,但是:“ From 或 To 表达 用括号括起来 “开始听起来很像”上下文相关“,递归下降不能直接处理。为了避免上下文依赖,您可能需要为 从 或 到 在括号中vs.a 从 或 到 没有帕伦斯。

编辑:虽然现在做任何好事都为时已晚,但如果我对你想要匹配的内容的理解是正确的,我想我会这样写:

Graph := 
       | List Sep Graph
       ;

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

List :=
      | Value List
      ;

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

很难确定,但我认为这至少应该接近(仅)匹配您想要的输入,并且应该使生成正确反映输入的AST变得相当容易。