Home‎ > ‎

Home Page - 2002-08-22

posted 28 Nov 2008, 19:49 by S V Ramu   [ updated 29 Nov 2008, 03:34 ]
Regular Expressions and Compilers [Read this article]

RE BNF FSM ...regular expressions are really very expressive. But still they are very simple at their core. Most of its meta characters ( * + | {} [] () . ? ) are there only to simply few routine things ... But what is the minimum requirement for a regular expression? A Regular Expression just requires three things: The * (Kleene star), | (pipe) and the basic string concatenations. There could be some variations on the above symbolism, but off late, all implementations keep Perl as the de facto standard for RE symbols and capabilities.

...The first time I read that a restricted form of BNF is in fact the Regular Expression itself, I was hooked. Here are two meta language that I've used a bit before, and both in the context of defining a string of characters. And here is some statement connecting them both. The crux is that I all along believed that RE and BNF is serving different ends (BNF for languages, and RE for strings), and hence are incomparable. In fact these two are different, and yes, BNF is more powerful than RE. But it is also true that both do have the spirit of a compiler in them. After all both match strings. The fact that, a restricted form of BNF = RE, only puts things in perspective. But how?