TXR：编写递归模式匹配指令

Question

我无法理解如何在 TXR 中编写递归模式匹配函数。下面我尝试定义一个用于识别文件路径的递归指令。我知道在这种情况下我可以用正则表达式 ([a-z]+\/)+[a-z]+ 表示此语法，但我为我的实际代码设置了一个更复杂的规则，将从中受益。当存在正斜杠时，是什么导致此指令失败？

@(define location)@\
@  (cases)@\
@/[a-z]+/@\
@  (or)@\
@/[a-z]+//@(location)@\
@  (end)@\
@(end)
@(repeat)
@(cases)
@{location (location)}
@  (output)
@location is a valid location.
@  (end)
@(or)
@location
@  (output)
@location is not a valid location.
@  (end)
@(end)
@(end)

示例有效输入：

this/is/valid
this/is/also/valid
this
a/b/c

Answer 1

（当然，您几乎可以肯定地知道 location 正在匹配一种我们可以用正则表达式进行修改的常规语言：/[a-z]+(\/[a-z]+)*/。我假设这只是一个 "recursion hello world" 为更复杂的事情做热身。）

关于 cases 的事情是它使用从上到下的短路求值。第二种情况无法匹配，因为第一种情况与其前缀匹配。它不像正则表达式分支运算符，其中子表达式的顺序无关紧要。

如果我简单地交换这两种情况，该示例对我有用。

同样有效的（在这种特殊情况下）是将 cases 更改为 some。 some 指令不会在第一次匹配时停止。

使用 some 并不是解决这种 cases 排序问题的灵丹妙药，因为有时您需要绕过一个 case 来终止递归（例如，避免左递归时达到某些条件）或避免性能下降（指数时间）。我想起一个大学教授的笑话："you've heard of divide and conquer; this is multiply and surrender".

some 也有属性后面的子句 "see" 绑定了前面成功匹配的子句。这可能会干扰它作为 cases 排序问题的解决方案。也就是说，后面的子句可能会因为变量冲突而匹配失败。 some 的 :resolve 功能在这种情况下可能有用，也可能没有用。

TXR：编写递归模式匹配指令

TXR: writing recursive pattern matching directives

recursion

grammar

text-processing

txr