Re: Commonality in subset construction and LR set of items construction algorithms

Chris F Clark <cfc@shell01.TheWorld.com> writes:
>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?


I learned it from a textbook (unfortunately I don't remember which
one). I think this is not pointed out in most textbooks, though.


> 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?


I don't know if there is a name for it, but a similar problem (and I
think the algorithm is similar, too) is in constructing tree parsing
automata; I think this was first described by Chase [chase87], but I
would recommend reading the description by Proebsting [proebsting95].


Likewise, there are on-demand versions of all three applications,
e.g., for tree-parsing [ertl+06pldi].


@InProceedings{chase87,
    author = "David R. Chase",
    title = "An Improvement To Bottom-up Tree Pattern Matching",
    booktitle = "Fourteenth Annual {ACM} Symposium on Principles of
Programming Languages",
    year = "1987",
    pages = "168--177",
}


@Article{proebsting95toplas,
    author = "Todd A. Proebsting",
    title = "{BURS} Automata Generation",
    journal = toplas,
    year = "1995",
    volume = "17",
    number = "3",
    pages = "461--486",
    month = may
}


@InProceedings{ertl+06pldi,
    author = {M. Anton Ertl and Kevin Casey and David Gregg},
    title = {Fast and Flexible Instruction Selection with
                                    On-Demand Tree-Parsing Automata},
    booktitle = {ACM SIGPLAN Conference on Programming Language
                                    Design and Implementation (PLDI '06)},
    ISBN = {1-59593-320-4},
    pages = {52--60},
    year = {2006},
    url = {http://www.complang.tuwien.ac.at/papers/ertl+06pldi.ps.gz},
    abstract = {Tree parsing as supported by code generator
                                    generators like BEG, burg, iburg, lburg and ml-burg
                                    is a popular instruction selection method. There are
                                    two existing approaches for implementing tree
                                    parsing: dynamic programming, and tree-parsing
                                    automata; each approach has its advantages and
                                    disadvantages. We propose a new implementation
                                    approach that combines the advantages of both
                                    existing approaches: we start out with dynamic
                                    programming at compile time, but at every step we
                                    generate a state for a tree-parsing automaton, which
                                    is used the next time a tree matching the state is
                                    found, turning the instruction selector into a fast
                                    tree-parsing automaton. We have implemented this
                                    approach in the Gforth code generator. The
                                    implementation required little effort and reduced
                                    the startup time of Gforth by up to a factor of
                                    2.5.}
}


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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