Re: rules to generate a context free grammar

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

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