Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| rules to generate a context free grammar alinsoar@voila.fr (A Soare) (2007-04-23) |
| Re: rules to generate a context free grammar mburrel@uwo.ca.easynews.com (Mike Burrell) (2007-04-23) |
| Re: rules to generate a context free grammar cdsmith@twu.net (Chris Smith) (2007-04-29) |
| From: | Chris Smith <cdsmith@twu.net> |
| Newsgroups: | comp.compilers |
| Date: | 29 Apr 2007 09:18:58 -0400 |
| Organization: | Altopia Corp. - Usenet Access - www.altopia.com |
| References: | 07-04-077 07-04-096 |
| Keywords: | parse, theory |
| Posted-Date: | 29 Apr 2007 09:18:58 EDT |
Mike Burrell <mburrel@uwo.ca.easynews.com> wrote:
> On 2007-04-23 07:48:12 -0400, A Soare <alinsoar@voila.fr> said:
> > I know that every set that can be generated by a computer can also be
> > generated by a context free grammar.
>
> That's not true. The set { a^n b^n c^n | n > 0 } for example, can be
> generated by a computer, but not by a context-free grammar.
Well, technically speaking, it is true. If a computer has k bits of
total memory (including all registers, main memory, etc.), then it is a
DFA with 2^k states. Therefore, any set that can be generated by a
computer can also be generated by a right-linear grammar (aka, regular,
or type 3 in the Chomsky hierarchy), and thus certainly by a context-
free one. :)
> For any program, you should be able to generate a grammar for it.
> Generating a pretty grammar is another story haha.
And, of course, this goes even more for the grammars I'm talking about.
--
Chris Smith
Return to the
comp.compilers page.
Search the
comp.compilers archives again.