"H. S. Teoh" <hst...@quickfur.ath.cx> wrote in message news:mailman.1358.1333576694.4860.digitalmar...@puremagic.com... > On Wed, Apr 04, 2012 at 05:03:39PM -0400, Nick Sabalausky wrote: >> "H. S. Teoh" <hst...@quickfur.ath.cx> wrote in message >> news:mailman.1351.1333549896.4860.digitalmar...@puremagic.com... > [...] >> > Sounds like the word you want is "closure". >> > >> >> Now that you mention it, that *does* seem to make sense: (Warning: >> Little bit of LALR internals here) > [...] > > I'm familiar with LALR internals. :-) > > > [...] >> It would indeed appear that the term "closure" the books used for >> state graph generation is also applicable for the lookahead generation >> algorithm I described in the OP. >> >> I think another part of what made me not realize to call it "closure" >> is that somehow I had the impression of "closure" being a much more >> general, even nebulous term. For example, I knew I'd also heard it >> used in the context of database theory. But, looking that up now, that >> *is* the same damn algorithm, too. >> >> So I guess a /facepalm is in order here ;) > [...] > > Well, the term itself *is* quite general. Mathematically speaking, for > something to be "closed" means that every combination of operations on a > set results in something that is already in the set. It's closed in the > sense that no operation will get you "outside the set". So what's a > closure? Given a set that *isn't* closed (i.e., some operations may take > you "outside the set", so to speak), the "closure" of the set is a > larger set that *is* closed. > > OK, an example is in order. Take the set A={0,1,2} and the operation +. > A is not closed, because although 0+1 and 0+2 are in A, 1+2 is not in A. > To form a closure, then, we take the elements produced by + that aren't > already in A, and add them to A. So for example, we add 3 to A, now 1+2 > is closed. But then 2+2 is not in the set. No problem, we just add that > to the set too. But now the newly added elements 3 and 4 are themselves > not closed under +, because 1+4 isn't in the set, for example. So we > have to add *those* elements as well. (I hope you can see the parallel > here with the algo in your OP -- you're trying to incrementally compute > the closure.) > > Taken to its logical conclusion, we find eventually that in order for A > to be closed under the operation +, we have to add *all* positive > numbers to it. So the closure of A is actually the entire set of natural > numbers. > > Now, this example isn't exactly the best one, because the closure is > infinite, so an incremental algorithm to compute it would never > terminate. However, not all closures are infinite. Closure under grammar > rule applications, like in your OP, is finite. Basically you keep > applying the rules until it doesn't yield anything more that you don't > already have. Then you can stop, because you've found the closure. >
Yea, that makes sense. I've been starting to think of it like: In both everyday english and in math/CS, "closure" is essentially "Everything's taken care of, no loose ends". Not a good technical definition, of course, but a way to help remember an internalize it.