patternMinor
Converting REGEX to BNF grammar
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!
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.
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.