C# and regex for word substitutions with nested tags

Question

I'm trying to create a small app that takes a base text template with specially tagged word arrays, parses the template contents and outputs a randomly generated text document.

Essentially, what I'm trying to do is take this:

<{Hello|Hi|Howdy}> world.

and turn it into this:

 Hello world.
OR
 Hi world.
OR
 Howdy world.

So far, so good. Googling got me enough to be able to successfully extract the inner text between the <{ and }> into an array, from which I then randomly select a word to replace the full <{Hello|Hi|Howdy}>.

The problem I'm having is parsing a nested set of words wrapped in the same tags.

For example, if I start with this:

<{Hello|Hi|Howdy}> world. <{How's <{life|it going}>?|How are you?}>

I'd like to turn it into this:

 Hello world. How's life?
OR
 Hello world. How's it going?
OR
 Hello world. How are you?

and so on...

Could someone suggest a way to do this fairly simply using c# and regex?

I've looked at http://www.vsj.co.uk/articles/display.asp?id=789 and http://www.m-8.dk/resources/RegEx-balancing-group.aspx, and to be honest, a lot of that goes way over my head, so something simple would be nice. ;-)

Thank you.

Answer 1

There is lex and yacc in the Visual Studio SDK:

These links might help:

http://msdn.microsoft.com/en-us/library/bb165963(VS.80).aspx

http://devhawk.net/2006/09/17/Managed+Lex+And+Yacc.aspx

Depending on how complex your parsing is going to be (considering possible future changes and additions) however you may just want to stick with Regex.

Answer 2

If you have currently have a regex that can correctly parse the values inside your tag into an array (call it A'), then for each value in A', reapply that regex.

You should be able to do this recursively.

Answer 3

This problem is not well suited to for regular expressions. The grammar needed to recognize the expression you described is not a regular grammar.

The expressions described above however can be described by a context-free grammar.

You should be able to parse this efficiently with a LL(1) parser. I would say that the problem is better suited to tokenizing the input using lex and constructing a abstract syntax tree using yacc.

Here's a tutorial on Grammars and parsing with C#

Answer 4

Seems like you're trying to describe and use a Context-Free Grammar rather than a regular expression.

Context-free grammars are strictly more powerful than regular expressions:

• Any language that can be generated using regular expressions can be generated by a context-free grammar.
• There are languages that can be generated by a context-free grammar that cannot be generated by any regular expression.

For C#, I recommend you ANTLR, is a framework for Language Recognition, allows you to construct recognizers, interpreters, compilers, and translators from grammatical descriptions.