1
$\begingroup$

I am interested in solving the problem of building a binary tree based on a regular expression containing letters of the Latin alphabet, parentheses, alternative, iteration and option (question mark). Associativity is taken into account, i.e. expressions of the form abc(a|b|) are correct. It is immediately demonstrated that the alternative may have empty arguments. Priorities are also taken into account: iteration has the highest priority, concatenation comes second, and the alternative is the weakest. I.e., a|ba|bca is read as (a)|(ba)|(b(c)a).

It is necessary to build a (binary) regular expression parsing tree that preserves its semantics. Node labels are concatenation, alternative (we resolve the option to alternative), iteration (iteration has only one child), empty label or letter (leaf labels).

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 1. Please proof-read the typeset question, then edit it to fix the errors. Put regular expressions in ..., otherwise Markdown interprets the * as an attempt to start/stop use of italics. $\endgroup$
    – D.W. ♦
    Commented Jul 21 at 23:28
  • 2
    $\begingroup$ 2. What is your question? I don't see a question here. We are a question-and-answer site, so we require you to articulate a specific question. It would also help to explain why this is relevant to others. Our mission is to build an archive of knowledge that will be useful to others, so we prefer questions that will be useful to many people. $\endgroup$
    – D.W. ♦
    Commented Jul 21 at 23:28
  • $\begingroup$ 3. Please make sure that the body of your post contains all relevant information. Don't put critical information in the title and omit it from the body. Your question should make sense if we read everything except for the title. If there is some requirement related to SMT solvers, please specify that carefully. Please edit your question to improve it based on this feedback. $\endgroup$
    – D.W. ♦
    Commented Jul 21 at 23:29

1 Answer 1

Reset to default
0
$\begingroup$

I am not sure what you mean by using SMT Solvers. However, the things you mentioned can be implemented using the standard lexing and parsing libraries. I used PLY once to lex and parse regular expressions and translate them to equivalent SMT-LIB regular expression syntax (Repo).

Hope this helps!
--SG

Improve this answer
$\endgroup$

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.