28 Nov 1997 01:05:39 -0500

Related articles |
---|

Q: regarding regular grammars ... mcr@visi.com (Michael Roach) (1997-11-24) |

Re: Q: regarding regular grammars ... henry@zoo.toronto.edu (Henry Spencer) (1997-11-28) |

Re: Q: regarding regular grammars ... karsten@tdr.dk (Karsten Nyblad) (1997-11-29) |

Re: Q: regarding regular grammars ... jos@and.nl (Jos A. Horsmeier) (1997-11-29) |

Re: Q: regarding regular grammars ... henry@zoo.toronto.edu (Henry Spencer) (1997-11-30) |

Re: Q: regarding regular grammars ... adrian@dcs.rhbnc.ac.uk (1997-12-05) |

From: | Henry Spencer <henry@zoo.toronto.edu> |

Newsgroups: | comp.compilers |

Date: | 28 Nov 1997 01:05:39 -0500 |

Organization: | SP Systems, Toronto |

References: | 97-11-136 |

Keywords: | lex |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.