Commonality in subset construction and LR set of items construction algorithms

Chris F Clark <cfc@shell01.TheWorld.com>
Fri, 24 Aug 2007 16:27:24 -0400

          From comp.compilers

Related articles
Commonality in subset construction and LR set of items construction al cfc@shell01.TheWorld.com (Chris F Clark) (2007-08-24)
Re: Commonality in subset construction and LR set of items constructio anton@mips.complang.tuwien.ac.at (2007-08-25)
Re: Commonality in subset construction and LR set of items constructio schmitz@i3s.unice.fr (Sylvain Schmitz) (2007-08-25)
Re: Commonality in subset construction and LR set of items constructio DrDiettrich1@aol.com (Hans-Peter Diettrich) (2007-08-26)
Re: Commonality in subset construction and LR set of items constructio torbenm@app-6.diku.dk (2007-08-27)
| List of all articles for this month |

From: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers,comp.theory
Date: Fri, 24 Aug 2007 16:27:24 -0400
Organization: The World Public Access UNIX, Brookline, MA
Keywords: parse, theory, question
Posted-Date: 25 Aug 2007 10:38:03 EDT

Recently the similarities between the subset construction algorithm to
transform an NFA into a DFA and the LR set of items construction
algorithm have been repeatedly thrust upon me, so much so that I have
a hard time as seeing them as anything but one algorithm.


Is this similarity a well known fact that I just somehow didn't learn
or forgot? Do the algorithms share some common root? In fact, is
there a common basic algorithm underlying both of these algorithms
that unifies them (and perhaps a bunch of other algorithms that I'm
not even aware of)? If so, what is that algorithm called and what are
some other examples of its application?


If this is something that I should know, please correct my deficiency
now....


Thanks,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)


Post a followup to this message

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