0

I need to split an expression (String) in pieces and call a recursive function from it's components. The expression is something like: (a or b), or ((a and b) or c), or ((a and b) or (c or d)) (or any other expression, no matter how many brackets it has. The operators and, or represents two functions ( Reunion and Intersection ).

For "((a and b) or (c or d))" I must call Union( F( "(a and b") ) , F( "(c or d)" ) ). F ( "(a and b)" ) will be Intersection("a","b") ... and so on.

I managed to split two-components expressions ( "a and b" ), but I can't handle bigger ones.

Thanks in advance!

8
  • Are you sure it's Reunion? Sounds like a prank :) Oct 26, 2012 at 20:36
  • 2
    Regex is not good at parsing nested brackets. You should not use it.
    – Rohit Jain
    Oct 26, 2012 at 20:37
  • then what would you suggest me to use? Oct 26, 2012 at 20:37
  • You are probably supposed to use recursion. You can certainly use regexp to get parts of one level.
    – hyde
    Oct 26, 2012 at 20:38
  • 3
    A recursive descent parser, of course. In this case, a trivial one. Oct 26, 2012 at 20:38

1 Answer 1

1

Answer to your question lies in authomata theory. Its about grammars and language classification.

It goes like this. There are regular grammars, and they can be covered by the reqular expression engine which implementation is a well-known java regex package for example.

The issue is that the language you've described is not a regular one. So, you can't use a regular expression engine here, its just not powerful enough. It falls into category of context free languages that can be described by context-free grammar (broader than regular group of languages).

If you want some theory background on this, you're welcome to read the following articles from Wikipedia :)

Regular grammar

Context free grammar

In any case you can at least use some kind of recursive parsers as what was suggested, or as a bare minimum to take a look on "pushdown automata".

Automata is a technique that can resolve grammars. For regular grammars its enough to build a regular automata, for resolving the context free grammars you should build a pushdown automata.

Again for the theoretical background and examples see the following article

Hope this helps

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.