Create a syntax tree from given regular expressions (for RE in DFA)
I am studying Automaton Theory and am having some difficulty converting RE directly to DFA. This method requires the creation of a syntax tree from RE. But I cannot generate. I am getting a regex like a*b*(a|b)abc
Now I want to generate a syntax tree. I don't need a program, but I want to do it manually. Can anyone help me?
source to share
You need to figure out what operations are represented by this expression, in what order they are applied, and what their operands are.
For example, a*
means: "apply operator *
to a
". In the expression tree, you will get a node for the star operator and a a
node for the symbol that the operator acts on.
Likewise, |
denotes interleaving, so it will have a node and child nodes will be interleaved subexpressions.
The top level operation is just a concatenation that will be your root node.
Here's the complete AST derived from these rules:
a*b*(a|b)abc
--+ CONCAT
|
+-+ STAR
| |
| +-- a
|
+-+ STAR
| |
| +-- b
|
+-+ OR
| |
| +-- a
| |
| +-- b
|
+-- a
|
+-- b
|
+-- c
EDIT: you requested a binary tree, the conversion should be simple. I'll leave both trees so you can understand:
.
/ \
. c
/ \
. b
/ \
. a
/ \
/ \
/ \
. |
/ \ / \
* * a b
/ \
a b
Note that the above tree uses the left associative concatenation operator.
source to share