23 Apr 2007 08:52:46 -0400

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: | Mike Burrell <mburrel@uwo.ca.easynews.com> |

Newsgroups: | comp.compilers |

Date: | 23 Apr 2007 08:52:46 -0400 |

Organization: | University of Western Ontario |

References: | 07-04-077 |

Keywords: | parse |

Posted-Date: | 23 Apr 2007 08:52:46 EDT |

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. Perhaps you

meant grammars in general, in which case it would be true: any set that

can be generated by a computer can be generated by a grammar.

*> My question is: looking at the program that generates a set, can we*

*> deduce the context free grammar that generates it? There are some*

*> rules for my problem? If not, there are clear rules to write the*

*> grammar for a set?*

For any program, you should be able to generate a grammar for it.

Generating a pretty grammar is another story haha. The general method

for doing this is to simulate each operation of the program as a rule

in the grammar. If you're simulating something with very few

instructions, such as a small Turing machine, it might not be so bad.

If you're taking on a program written on a modern ISA with all of its

thousands of instructions, well, good luck :)

Mike

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.