Compilers - cycle free grammar ?

Author

cycle free grammar ?

ctx2002@gmail.com

2007-08-07, 7:16 pm

hi all:

I am currently learning how to write a compiler , i am using a book
called Compilers Principles , techniques, and tools.

in this book , there is an exercise asking write a algorithm to
convert a grammar into a equivalent cycle - free grammar.

for example:

convert grammar s->ss|(s)|e to a cycle free grammar.

any one know how to do that?

i have searched google, have not found any thing yet.

regards

SM Ryan

2007-08-07, 7:16 pm

ctx2002@gmail.com wrote:
# hi all:
#
# I am currently learning how to write a compiler , i am using a book
# called Compilers Principles , techniques, and tools.
#
# in this book , there is an exercise asking write a algorithm to
# convert a grammar into a equivalent cycle - free grammar.

In Aho and Ullman _The Theory of Parsing, Translation, and Compiling_,
Volume 1, they have a number of grammar transformation algorithms
including this one. I don't have a copy at hand, but it's in there.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
Mention something out of a Charleton Heston movie, and suddenly
everybody's a theology scholar.

Max Hailperin

2007-08-09, 8:10 am

ctx2002@gmail.com writes:
> I am currently learning how to write a compiler , i am using a book
> called Compilers Principles , techniques, and tools.
>
> in this book , there is an exercise asking write a algorithm to
> convert a grammar into a equivalent cycle - free grammar.
>
> for example:
>
> convert grammar s->ss|(s)|e to a cycle free grammar.
>
> any one know how to do that?

If you first make the grammar epsilon-free (which is the prior
exercise, if memory serves me), then the only kinds of cycles that can
remain are those based on productions of the form A -> B. That may be
enough of a hint to let you figure out the algorithm on your own. If
not, a second hint would be to look at algorithms for finding the
strongly connected components of directed graphs. -max

Sponsored Links