CODEWITHSUNDEEP
regexdfa
Hardik Modha
Hardik Modha

Reputation: 12746

Create Syntax tree from given Regular Expressions (For RE to DFA)

I'm learning Automaton Theory and facing some difficulties for converting a RE directly to DFA. This method requires to create syntax tree from the RE. But i am not able to generate.
I am given a regular expression e.g a*b*(a|b)abc

Now i want to generate a syntax tree from this. I don't want program for it but i want to do it manually. Can anyone help me?

Upvotes: 3

Views: 9613

Answers (1)

Lucas Trzesniewski
Lucas Trzesniewski

Reputation: 51420

You need to figure out what are the operations represented by this expression, in which order they apply, and what are their operands.

For instance a* means: "apply the * operator to a". In the expression tree, you'd get a node for the star operator, and an a node for the symbol the operator acts upon.

Similarly, the | denotes an alternation, so it would be a node in the tree, and the child nodes would be the subexpressions of the alternation.

The top-level operation is simply a concatenation, that would be your root node.

Here's the full AST derived from these rules:

a*b*(a|b)abc

--+ CONCAT
  |
  +-+ STAR
  | |
  | +-- a
  |
  +-+ STAR
  | |
  | +-- b
  |
  +-+ OR
  | |
  | +-- a
  | |
  | +-- b
  |
  +-- a
  |
  +-- b
  |
  +-- c

EDIT: You asked for a binary tree, the transformation should be straightforward. I'll leave both trees so you can figure it out:

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

Note that the above tree uses a left-associative concatenation operator.

Upvotes: 2

Related Questions