HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Converting REGEX to BNF grammar

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
convertingregexgrammarbnf

Problem

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!

Solution

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.

Context

StackExchange Computer Science Q#67979, answer score: 3

Revisions (0)

No revisions yet.