Sat, 25 Aug 2007 15:50:58 GMT

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

From: | anton@mips.complang.tuwien.ac.at (Anton Ertl) |

Newsgroups: | comp.compilers,comp.theory |

Date: | Sat, 25 Aug 2007 15:50:58 GMT |

Organization: | Institut fuer Computersprachen, Technische Universitaet Wien |

References: | 07-08-071 |

Keywords: | parse, theory, bibliography |

Posted-Date: | 25 Aug 2007 12:16:09 EDT |

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/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.