Packrat parsing is a relatively new approach to parsing code introduced by Bryan Ford in his 2002 Masterâ€™s thesis. Packrat parsers are capable of very efficiently parsing a class of grammars called Parsing Expression Grammars (PEGs). I covered PEGs in more depth in my previous post, PEGs and the Structure of Languages, so if youâ€™re new to the topic, I recommend you begin there. The packrat parser is based on earlier work on recursive descent parsers, dating back to the 70s, but focused specifically on Parsing Expression Grammars. In this post, Iâ€™ll attempt to demystify packrat parsers by walking through a complete packrat parser implementation that fits in a few dozen lines of Javascript code.

Continue readingâ€¦

When I first began working on my programming language Nomsu, one of the first challenges I faced was how to get the computer to see code written in my language as more than just a long sequence of letters. Code has *structure*, and finding that structure is called parsing. After spending a long time digging through different approaches to the problem, one lesser-known (though increasingly popular) approach called Parsing Expression Grammars became my favorite, and allowed me to make my own programming language. This post will explain what Parsing Expression Grammars (PEGs) are, and a bit of background on the problem they solve. There are some very good PEG libraries available (I first found out about PEGs through the Lua library LPEG), and in a follow-up post, Iâ€™ll even explain how to implement a PEG parser from scratch. Hopefully, after reading this post, youâ€™ll have enough understanding to try defining your own language (programming or otherwise) with a Parsing Expression Grammar.

Continue readingâ€¦

C can be a very fun language to program in, if you can set up your project well. A lot of what I know about managing C projects was learned the hard way by experimentation and studying other peopleâ€™s code. This post is meant to be the guide I never had to organizing and polishing nontrivial C projects, as well as setting up Makefiles for building them and manpages for documentation.

Continue readingâ€¦

Iâ€™d like to present a handful of programming concepts that I find incredibly useful, all of which can be implemented in under 20 lines of code. These techniques can be used in a wide range of contexts, but here, Iâ€™ll show how they can all build off of each other to produce a full physics engine in just 75 lines of code.

Continue readingâ€¦

Noise functions are a way to produce continuous pseudorandom values across one or more dimensions. The simplest example is a one-dimensional noise function that makes the y-value wobble up and down smoothly, but unpredictably, as you move along the x-axis. Itâ€™s also possible to produce 2-dimensional noise, where the amplitude of the noise depends on the x,y coordinates youâ€™re sampling.

Continue readingâ€¦

Contour lines, also known as isolines, are lines drawn along along paths of constant elevation. They are often used when drawing maps to indicate the slopes of hills and mountains.

But they can also be used to visualize functions that map (x,y) values to z values, or to find the boundaries of implicit surfaces. One of the common algorithms for finding contour lines is Marching Squares. The algorithm assumes that you have a set of elevation data points spaced out at regular intervals on a grid, and generates contour lines for each square of the grid. A simpler algorithm exists, called Meandering Triangles, and it divides the data points into triangles, rather than squares, to reduce the number of cases the algorithm has to handle. Here, Iâ€™ll give a full explanation of how the Meandering Triangles algorithm works, with some examples to show it in action.

Continue readingâ€¦

Consider this problem: You have a list of items and a list of their weights. You want to randomly choose an item, with probability proportional to the itemâ€™s weight. For these examples, the algorithms will take a list of weights and return the index of the randomly selected item.

Continue readingâ€¦