A web log. Mostly about computer science-y stuff.
I hope you know a bit about LR parsing, otherwise this blog post won’t make much sense to you. You can read all about it in a previous post of mine . Today I want to discuss the problems with getting your language parsed in LR(1), or even LR( k ). And how an old way to solve those problems is with a more powerful algorithm, that can parse any context-free grammar, no restrictions, no complaints…
I thought I was done with this topic for while, happily planning a new blog post on generalised parsing, but here we are again. This post will be a kind of remix of the two posts on optimising recursive ascent parsing . Why? Well, I wrote those posts directly based on the papers I refer to in there, and they present their optimisations based on code. At the time that felt quite natural, and I…
Welcome back! Previously, on Optimising Recursive Ascent Parsing , we explored the ideas from a 1990 paper called Optimizing Directly Executable LR Parsers by Peter Pfahler . With the paper’s example grammar, and the described optimisations, we managed to optimise away 6 out of 15 states in the parser. But that’s peanuts compared to what we’ll do in this post! We’ll be taking inspiration from…
This is post picks up where we left off with parsing : Recursive Ascent. In the previous post I highlighted how parsing is all about grammars and (push-down) automata (PDA). And that if you follow the logic of how LL parsing has recursive descent, then LR parsing should have recursive ascent . Which it does! In this post we’ll explore a couple more techniques for making the recursive ascent parser…
Sorry if I broke the feed in your RSS reader. I’ve switched away from Jekyll to Zola for generating this blog. And I preserved only the blog post links (through HTML based redirects). I didn’t preserve the exact format of the RSS feed file, or really any of the design of the blog as you can see. I just picked a theme from among the ones on Zola’s list on the site, one that looked simple and didn’t…
This is part 2 of old-school linear time parsing algorithms, which only need to go over the input once, without backtracking or caching. In part 1 we learnt about LL parsing, how to construct the parse tables for it, and how those relate to direct execution of the parser with recursive descent. Since part 1 and part 2 were originally one blog post that I simply cut in half after feedback that it…
Hello again! I’m picking up my series on Automata , with this post that goes into what I had always meant to get to: parsers. We’ll check out the old-school linear time parsing algorithms, which only need to go over the input once, without backtracking or caching. Originally this was one big post, but given the feedback I’ve gotten from (non-)readers, I’ve now split it up into two. In this first…
Once upon a time, I wrote an interpreter for Stratego Core in Rust, which I named strs . Stratego Core is the core language that Stratego is compiled to before the compiler goes further (to Java, or previously to C). A core language is an intermediate representation that is a subset of the surface language. While I optimised that interpreter quite a bit, I noticed that the CTree (Stratego Core…
More than a year ago a friend of mine wanted to learn a bit more about Rust by trying out a project. He had a nice project in mind which suits Rust quite well I think. For fun I joined his effort and created an implementation at the same time as he did, discussing and comparing along the way. In this post I’ll tell you about the project specifics, but the point of the post is more an…
At the end of my last post, three months ago by now, I promised a blog post about the Stratego interpreter that I am writing . In fact I promised it soon, which sadly became “soon”. Life happened, deadlines on top of deadlines with major stress. I made it through in one piece though, so here’s the long promised blog post. I assume you’re already a bit familiar with Rust, most of my blog posts use…
I published my first crate to crates.io ! It’s called aterm , and it’s a library that implements the A nnotated Term format. Currently it can only parse and print the normal textual format, but I’m planning to add the other three formats too at some point. There are also a number of other improvements that I have planned. But I’m going to try to not make this post a brain-dump of meandering…
In this post I’d like to shortly discuss an idea I’ve had a long time ago about type systems and units of measure. The usual pitch about having units in the type system of a programming language starts with a sad story about some space craft crash because different teams used different measures of distance. The competing systems are usually Imperial vs Rebels Metric . Then units in the type system…
I’ve purchased a domain name: jeffsmits.net . This weblog is now on blog.jeffsmits.net . I’ve made sure this blog stays available from the old URLs, but I can’t guarantee that new content will be available there. One of the perks of having a domain name is that you can switch around the back-end that hosts the content. For now the hosting is still GitHub Pages , but that may change at some point…
This is post number four in a series on Automata (in the formal languages / regex / parsing sense). It’s also part two of the “implementation-heavy” stuff, where we go into implementing automata for real and useful things. This one is more of a mix of theory and code, which I hope is more appealing than the previous post which were either one or the other. In part one I naively claimed…
This is post number three in a series on Automata (in the formal languages / regex / parsing sense). This is the promised “implementation-heavy” post, where we go into implementing automata for real and useful things. As always the programming language is Rust. By now I’ve actually had a bit of practice with the language, so hopefully the code will be less naive. Where in the previous…
TL;DR: I’ve ported the tool cargo-benchcmp from Python to Rust and added some functionality. There is more to come which is mostly waiting for review in pull requests . I’ve been messing around with Rust for a while now, and I found a little utility called cargo-benchcmp by the famous BurntSushi (Andrew Gallant) . You may have seen the benchmark comparisons in one of his blogposts already. I found…
This is just a short post about my new terminal setup. I think it’s both pretty and useful. For example, it gives me the current time and info about version control when I’m in a directory with vcs: Skip to the end for terse instructions/commands for mac and linux. Terminal First off, you need a good terminal emulator that can handle 256 colours. Try echo $TERM . If it returns xterm-256color…
Welcome back! This is my second post in a series on Automata. I decided to do another theory post first on context-free languages, and only afterwards start on a more implementation-heavy post about implementing this kind of theory in Rust for practically useful stuff. There is of course still code in this post as well :) I’ll start with a quick refresher, but for more details read the first post…
What do Turing machines and regular expressions have in common? One is a theoretical model of a computer, and can be used to prove that some things cannot be computed. The other is a practical tool for matching strings. And yet they are both based on a simple computational model : a (very constrained) finite state machine (FSM). In this blog post we’ll go over the basics of this type of FSM and…
What This is just an announcement post. I’m going to write some posts about theoretical computer science stuff. The planned ‘stuff’ is: finite automata, regular languages, and context-free languages. The plan is to work up to parsers and parsing algorithms eventually, but let’s see how far I get and quickly I get there first. How To start things off I’m going to use the book Introduction to the…