Re: Q: regarding regular grammars ...

Michael Roach <mcr@yuck.net> wrote:
>I thought regular expressions were regular grammars, is that assumption
>wrong? And if so, could you explain the differences or point me to some
>references...


Regular expressions are regular grammars, written as "one-liners" by using
more powerful notation than the usual sort of grammar. For example, you
can write "(A|B)C*(D|E)", or you can write:


<phrase> ::= <modifiers> D
<phrase> ::= <modifiers> E
<modifiers> ::= <modifiers> C
<modifiers> ::= <start>
<start> ::= A
<start> ::= B


which is a regular grammar of the strictest sort. The two are equivalent,
although the transformation between them can be tedious.


(One note of caution: "regular expressions" in computing practice have
wandered away from their theoretical roots to some degree, and sometimes
now include constructs which are not "regular" in the theoretical sense.)
--
If NT is the answer, you didn't | Henry Spencer
understand the question. -- Peter Blake | henry@zoo.toronto.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.