3

我想知道 Perl 中有哪些方法可以遍历作为字符串给出的递归结构（例如二叉树）。

更具体地说：

这是一棵树，为简单起见是解析树并且非常短。想象它是没有花哨的制表符和空格的字符串。

tree(Sentence, 
  tree(NounPhrase,
    leaf(Determiner, "a"),
    leaf(Noun, "man", "singular")
  ), 
  tree(VerbPhrase,
    leaf(Verb, "walks", "present", "3rd person")
  )
)

现在我想访问根的两个直接子节点，但我不能简单地使用正则表达式来做到这一点。

m/tree \( \w+ , (group1) , (group2) \) /x

我想正确捕获 group1 和 group2，即 group1 和 group2 具有偶数个左括号和右括号。

这似乎是一项相当复杂的任务，想知道它的常见/最简单的解决方案是什么？

例如，prolog 很容易消化这个任务。

4

3 回答 3

2

我会尝试创建 2 个函数：sub tree{}和sub leaf{}

他们每个人都会返回一个标记为字符串的术语，例如leaf(Determiner, "a")会返回<Determiner>a</Determiner>

然后只需执行您要处理的文件。输出将是一个类似 DOM 的结构，您可以使用任何 DOM 解析器XML::DOM进行解析，例如

于 2012-10-06T04:50:00.447 回答
0

Ok, thanks, so the answer is "Simply, it is not possible only with RegEx".

于 2012-10-06T11:59:31.907 回答
0

如果您知道预期有多少孩子，正如您的示例正则表达式所暗示的那样，那么这相当容易，这样的事情就足够了：

my @children = m{ tree\(  \w+?, ( (?:tree|leaf)\(.+\) ), ( (?:tree|leaf)\(.+\) ) \) }x;

如果你不这样做，这似乎更有可能，那么它确实不简单，但它是可能的。在他关于正则表达式的书中，Jeffrey Friedl 建议使用他所谓的动态正则表达式构造来构建递归模式以匹配嵌套对。

# first, strip your string
s{ ^ tree\( \w+ , (.+) \) $ }{$1}x;

# then, define the recursive pattern to match paired parentheses
my $recursion;
$recursion = qr{ (?> [^()]+ | \( (??{ $recursion }) \) )* }x;

# finally, match!
my @children = m{ ( (?: tree | leaf ) \( $recursion \) ) ,?}gx;

在 perlre 中，这称为延迟正则子表达式，并被记录为实验性功能.

于 2013-12-10T17:20:43.723 回答