Browse by Tags

Tagged Content List
  • Blog Post: 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 we’re trying...
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: 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” was...
  • Blog Post: 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 trees of size one, then all...
  • Blog Post: 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...
  • Blog Post: 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 a...
  • Blog Post: 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 all the...
Page 1 of 1 (9 items)