Re: rules to generate a context free grammar

Chris Smith <cdsmith@twu.net>
29 Apr 2007 09:18:58 -0400

          From comp.compilers

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)
| List of all articles for this month |

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



Post a followup to this message

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