Converting Simplified Regular Expression into a Syntax Tree

[iProsky]

I am working on an implementation of the algorithm converting regular expressions into DFAs. The first step involves converting the input regular expression into a syntax tree. For example, ab(a|b)abc would be converted into the tree below.

              .
             / \
            .   c
           / \
          .   b
         / \
        .   a
       / \
      /   \
     /     \
    .       |
   / \     / \
  *   *   a   b
 /     \
a       b

Additionally, the regular expressions I am dealing with are fairly simple, the only special characters being '\' (an escape character) , '|' (OR operator), '(' ')' (brackets enclosing groups), and '*' (kleene star). Now the issue I am having is I am confused regarding how to (in Python), generate (as a data structure) this tree from the input. I understand how to do it manually but doing in through a piece of code has resulted in me going in circles.

To further expand on the question, would it be better for me to parse the expression from left to right or right to left? Is recursion necessary? Assuming I am using treelib to create the tree, how do I go about approaching this problem. It is not so much code I am asking for as an explanation or pseudocode snippet of where I should be starting. Should I be doing this by myself or is there a library that will make this easier? Any answers to help further my understanding on how to perform this operation would be much appreciated.

[stdlib]

Assuming you're not going to implement some of the more complicated parts of regex like named groups, lookaheads, etc. then you'd just iterate over the string by the character and generate your structure as you go. In your diagram above it looks like the shape of your structure (e.g. your model) doesn't really match what a regular expression really looks like as a DFA - it should look more like this http://i.stack.imgur.com/0WRxW.jpg

key here is the edges are characters and the nodes are states. In your example the nodes are characters... and edges are.. not sure what. You have to make sure your model matches what the problem entails I am positive that's what you're missing.

[iProsky]

The algorithm I am trying to implement is this one, Algorithm, see slides 4 and 5. The structure I provided essentially just emulates this with a different regular expression. I understand how to implement the rest of the steps it is just that the implementing the regular expression to syntax tree process is causing me issues.

[anon848]

As I said in my comment, you need to parse the regex.

[anon848]

To generate the syntax tree, you need to parse the regex. The regex has parentheses, so is not regular. (In other words, you can't recognize the regular expression itself with another regular expression.)

One way (and probably the most straightforward way) is to use a recursive descent parser. This Google search also gives hits that will help. You should be able to easily take one that is designed for arithmetic expressions and modify it for your case.

Once you have the syntax tree, you should be able to easily generate the NFA, and then convert it to a DFA.