Delimiter matching in Perl?

[jducoeur]

Here's a question for the Perl and/or regexp experts in the audience; all help is solicited.

ProWiki has a query language built in. Simplifying greatly, the syntax looks like this:

{? [query terms] : [display results] ?}

This translates roughly as "for each page that matches the given query terms, show the display results, interpolating the properties of the page". That all works nicely, and is at the heart of what ProWiki does.

The problem is, I'd really like to be able to do this recursively. That is, I'd like to be able to construct a query like (to take today's example, one of many):

{?~Faction : %%Name%% -- {?~Character && Faction==%%PAGENAME%% : %%Name%% ?} ?}

That would translate as something like, "For each Faction, display the Faction's Name, and then for each Character in that Faction, display the Character's Name". Basically, nested foreach loops.

That's conceptually straightforward, but I'm stuck on how to parse it. ProWiki, being based on UseMod, uses Perl regex for its parsing. That mostly works fine, but I can't figure out how to get it to work recursively. I need to find the *matching* {? ?} pairs, extracting as plaintext any pairs that might be contained inside them. (The Perl code itself will then deal with the recursion into the plaintext subexpression.)

Can this be done straightforwardly in regex? It seems like a fairly common problem -- it's basically a fancy variant of parenthesis matching -- but I'm not hip enough to regex to see the answer. It's not simply a matter of matching first and last delimiters in the string, since a given page might contain several unrelated top-level expressions; therefore, I need to find the genuinely *matching* delimiters.

I know there are a bunch of Perl gurus out there, so if you can outline the solution to me (even the solution to the basic parenthesis-matching problem would probably show me how to do it), I'd be grateful. Thanks...

Comments

[jducoeur]

Yeah, but single-character really isn't a practical option. We're defining what amounts to a markup language here, so I need something odd enough to not generally appear in the text being marked up.

Really, the big question for the next generation (which is when all of this gets seriously reconsidered) is whether to stick with something like this (a C-ish symbolic language), or go over to the verbose side of the force and do it with XML. I go back and forth on that...

[learnedax.livejournal.com]

Oh, I wasn't saying you should use a single-character delimiter, just providing another reason why the regex could be complicated to maintain - whereas a relatively simple (even actually iterative with pushdown) recursive descent would work fine. OTOH, it does look like you now have enough to push off a final decision on the parsing model.

Personally, I think verbosity would kill adoption. I'm also not sure that XML is a good metaphorical match for a query-and-render blob. Certainly the qualities you need to balance are simplicity and brevity.

[jducoeur]

OTOH, it does look like you now have enough to push off a final decision on the parsing model.

Oh, none of this discussion had anything to do with what the *right* way to do it might be -- the plan is to scrap the whole parse stack for the Querki rewrite. This was mainly a question of whether there was a convenient enough short-term solution to get the functionality I'd like to have right now. (If there hadn't been, I simply would have done without.)

I think it's *very* likely that Querki will be based on a proper recursive-descent parser. But that'll be written from scratch, rather than hacked up from an older wiki.

Personally, I think verbosity would kill adoption.

Could be. The only reason I'm willing to contemplate it is that the intent is to do most query editing with a context-sensitive GUI. But I'll admit that the XML option doesn't thrill me: I'm mainly leaving it on the table to consider the options fairly until I have to make a decision. And it may be unwise to put too much weight behind the GUI idea until that's been proven, which argues for something easier to type.

(Really, the only problem with the current language is that it's not exactly a model of clarity, and neither are most of the similarly-concise options I've come up with...)