Hi all,
I have regular expressions steering graph traversal given as nested
vector. For example [:p-* [:p-seq :--> :-->]] means that the sequence
(:p-seq) of 2 consecutive outgoing edges may be traversed zero or many
times (:p-*).
Ok, now I want to make these regular expressions, which are
indeterministic finite automatons, deterministic. Therefore, I need to
replace p-* and p-opt operations, but I have no good idea on how to do
at least the latter replacement.
Lets start with the simpler `replace-p-*'. It should replace all
occurences of [:p-* exp] with [:p-alt [] [:p-+ exp]], meaning either you
do nothing, or you traverse exp one or many times (:p-+). Example:
(replace-p-* [:p-* [:p-seq :--> :-->]])
==> [:p-alt [] [:p-+ [:p-seq :--> :-->]]]
Ok, that was not too hard and I think I can do that easily with
clojure.walk/preorder.
But replacing options (:p-opt) is harder, and here, I don't know how to
do it, because one has to refer to constructs in the tree that are
nearer at the root. Any [:p-xxx [:p-opt exp]] for whatever :p-xxx has
to be replaced by an alternative (:p-alt) with the first parth expluding
exp and the other including exp: [:p-alt [:p-xxx] [:p-xxx exp]].
Example:
(replace-p-opt [:p-seq [:p-opt [:p-seq :--> :-->]] [:p-+ [:p-seq :--> :-->]]])
==> [:p-alt [:p-seq [:p-seq :--> :-->] [:p-+ [:p-seq :--> :-->]]]
[:p-seq [:p-opt [:p-seq :--> :-->]] [:p-+ [:p-seq :--> :-->]]]]
Thanks for any pointers!
Bye,
Tassilo
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
