How do I parse a string representing a recursive data structure using Perl regular expressions?

Question

I wonder what methods are in Perl for traversing a recursive structure (e.g. binary tree) which is given as a string.

More concretely:

Here is a tree, for simplicity is parse tree and very short. imagine it is string without fancy tabbing and spaces.

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

Now I want to access two direct child nodes of the root, but I cannot do this with regular expressions simply.

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

I would like to capture group1 and group2 correctly, i.e. group1 and group2 having even number of opening and closing parentheses.

It seems quite complicated task and wonder what is the common/simplest solution to it?

For example, prolog will easily digest this task.

Answer 1

I would try by creating 2 functions: sub tree{} and sub leaf{}

each of them would return a tagged term as a string, for example leaf(Determiner, "a") would return <Determiner>a</Determiner>

then simply execute the file you want to process. The output would be a DOM like structure which you can parse with any DOM parser like XML::DOM for example