Every Program There Is, Part Nine

[This is the final part of a series on generating every string in a language. The previous part is here.] We seem to have a bit of a performance problem here. We could slap a profiler on it, and normally I’d recommend just that. But in this case, let’s solve this problem by thinking. Suppose…

3

Every Program There Is, Part Eight

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] OK, first things first. Let’s assume that we have a string that contains a grammar that has already been rewritten into our “nice” form, where there are exactly two terms in every…

1

Every Program There Is, Part Seven

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] Things seem to be going so well. We have a sketch of a recursive solution for enumerating all strings of a particular grammar and it looks like the recursion is well-founded. Let’s…

2

Every Program There Is, Part Six

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] The problem we ran into with our grammar-enumeration technique is that the recursion does not clearly reduce the problem to a smaller problem. We need to find some way to reduce the…

1

Every Program There Is, Part Five

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] Last time: Clearly we have reduced a problem of size k to multiple problems of size less than k-1, and so this is amenable to a recursive solution. Right? Wrong. (The “clearly”…

4

Every Program There Is, Part Four

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] Remember, the point of this exercise was to come up with a device to help me test parts of my compiler. To test binary trees as we saw we can generate all…

9

Every Program There Is, Part Three

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] Suppose we want to write a grammar for a simplified C# class declaration. Let’s say that there are one-character identifiers, a class can be public or internal, and that there are no…

4

Every Program There Is, Part Two

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] Suppose we want to come up with a CFG for numbers with additions. Consider this very simple grammar with only one nonterminal. We’ll say that an expression is either a number, or…

10

Every Program There Is, Part One

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] We can now enumerate every binary tree and every arbitrary tree of a given size, and therefore we can enumerate all of them, period: enumerate all the trees of size one, then…

14