6
$\begingroup$

Say I have a bunch of regex expressions which are used as filtering rules. (Any special extraction capabilities are unnecessary here, the set of regular expressions I have is only used for filtering down sentences).

Can any pure regex be converted into BNF? (ABNF, EBNF, etc.)

Are there well known algorithms (or existing library implementations) that can perform the conversion?

The language I wish to convert from is actually not the standard language of regular expressions, but one that conditions on word taggings which are provided per word (part-of-speech tags that come along with the text). So it is a variant of regular expressions, which operates at the word level rather than the character level.

Thanks!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Conventional regular expressions as they are commonly found in literature describe exactly the regular languages. Given a regular expression, you can therefore find an equivalent automaton, then find the linear grammar equivalent to such automaton and put it in any form you prefer.

On the other hand, "regular" expressions as they are implemented by most programming languages are not equivalent to the set of regular languages; several implementations allow you to describe languages that aren't even context-free.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Right! I should dig up a good literature reference for distinguishing whether the source language I have at hand deviates from the strict sense of a regular language or not! $\endgroup$
    – matanox
    Commented Dec 28, 2016 at 16:22
2
$\begingroup$

It depends on your type of regular expressions. Classical regular expressions describe regular languages, whereas BNFs describe context-free languages. Since regular languages are context-free, you can convert every regular expression to a BNF. This is covered in courses on automata theory. There are three steps: convert your regular expression to an $\epsilon$-NFA, then convert the $\epsilon$-NFA to an NFA, then convert the NFA to a regular grammar.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks a lot! I should study that area more deeply one day. In the meanwhile, Is there any open-source library that manages these kinds of transformations, that can be used for this and similar transformations?? $\endgroup$
    – matanox
    Commented Dec 28, 2016 at 16:18
  • $\begingroup$ Probably, but I'm not aware of any. You can try your luck on stackoverflow (software recommendation is off-topic here). $\endgroup$
    – Yuval Filmus
    Commented Dec 28, 2016 at 16:20
  • $\begingroup$ Sure, I can probably find it on the web if one exists $\endgroup$
    – matanox
    Commented Dec 28, 2016 at 16:20
  • $\begingroup$ Software recommendations are generally off-topic on SO, as well ("Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow" -- stackoverflow.com/help/on-topic) but such questions sometimes get answered anyway. $\endgroup$
    – rici
    Commented Dec 28, 2016 at 20:34

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.