Computing – BALAFON

IronMeta 1.2 Released

I have released a new version of IronMeta. It makes the syntax closer to the usual OMeta syntax.

I also fixed a bug that caused some redundant evaluation to be done. Performance is still pretty bad, though.

I will be focusing on

You can download the new version at SourceForge, or via Subversion at https://ironmeta.svn.sourceforge.net/svnroot/ironmeta/tags/1.2/.

IronMeta provides a programming language and application for generating pattern matchers on arbitrary streams of objects. It is an implementation of Alessandro Warth’s OMeta system for C# on .NET.

IronMeta, a parser generator for C#

In between the new job and the new baby I have still managed to finish up the project I’ve been working on for myself.

It’s a C# implementation of Alessandro Warth’s OMeta pattern matching meta-language.

The IronMeta system builds parsers that can operate not only on streams of characters, but streams of objects of arbitrary types. The matchers can operate using the semantics of Parsing Expression Grammars or as fully backtracking recursive descent parsers.

IronMeta uses Warth, Douglass and Millstein’s algorithm for handling both direct and indirect left-recursion.

Grammar rules in IronMeta can take parameters, and in fact can match parameters against a pattern, allowing for different rule patterns depending on the number, type and value of parameters passed to them.

IronMeta also allows for higher-order rules, i.e. rules that can take other rules as parameters.

Why Linux (oh, and Open Source too!) is a Big Fat Pile of Steaming Excrement

So at work I get a new computer and have to install Linux on it. I am quickly reminded why I gave up on Linux in disgust lo these many years ago. I’m installing a distro with a cutesy African name (that English-speakers universally mispronounce, making me cringe every time) that is universally received as the ultimate in desktop-friendliness (as much as that means anything in Linux-land).

Now one of the criticisms leveled at, say, Windows, is that there’s often no way to diagnose a problem, and trouble-shooting simply consists of reinstalling pieces until things sort of work again.

So I install from the very latest ISO on the website, and things seem to work OK. However, there’s some update program yammering for my attention, so I check it, and there’s evidently 280 pieces that need updating. That’s quality control for ya. So I run the update, which automagically chooses the slowest possible mirror to use — 30 kilobytes per second, for crying out loud.

Now that the updates are done, the window manager crashes and burns. Luckily, since Linux is so much better than Windows, I can tell exactly what’s causing it to crash. Well, it can’t seem to find a function ISNGBdiugjnooruwojhdwIgHDUWHGUdh in a shared library. Now I actually happen to know what this means. I also happen to know that I can do exactly squat about it, because the vaunted package manager that is supposed to keep all those picky dependencies straight can’t actually be arsed to do its job.

A quick Google finds that lots of other people have encountered this problem, and that the recommended solution starts like this:

apt-get --reinstall ...

Remind me how much better than Windows this is?

And to top it off, when I do run this recommended command, the computer has conveniently forgotten that it ever had a network card, so my download speed is now, let’s see, nothing times nothing, carry the nothing…

This is why I’d far rather run an operating system whose development includes at least some pretense to a QA process, and which I can use to get something resembling work done in less than a week of setup, rather than Linux, which is “Open Source”, meaning a random pile of poorly-coordinated contributions by people working on little bits of things that they happened to feel interested in during their off hours, and thus resembles nothing less than a terrain feature you’ll often find behind a farmer’s barn.

I weep for the thousands of hours I wasted on Linux in my youth before I discovered OpenBSD.

Parsing Expression Grammars and Left Recursion

Parsing Expression Grammars are a form of context-free grammars with ordered choice. This reduces ambiguity in the grammar and makes writing simple recursive-descent parsers (and parser generators) quite easy. With memoization, you can parse in linear time. The resulting parser is called a Packrat Parser.

The only problem is handling left-recursion. If you have grammar rules like this:

Expression = Expression "+" Term | Term

your recursive-descent parser will recurse until it runs out of stack.

I just noticed a paper on detecting and handling left-recursion: Packrat Parsers can Handle Left Recursion. It’s a nifty technique, but it somewhat reduces the simplicity of the resulting program.

For a finger exercise a while ago I wrote a pretty basic packrat parser generator and used it to implement a C preprocessor. Source is here. When my supply of circular tuits increases I’ll have to look at implementing the stuff from the paper.