This is the first post in what will hopefully be a series about how to build an Earley parser. I've been struggling to hammer the grammar for a language I'm working on into a form suitable for use with a PEG (parsing expression grammar) parser. Over the past two weekends I was even trying to add support for handling left-recursive grammar rules into Citrus (a PEG parser), but as it turns out, the currently known methods for enabling left-recursion are not powerful enough to recognize all forms of left-recursive grammars. I officially gave up trying to use a PEG parser for my grammar, it simply isn't flexible enough. I've decided to go whole hog, and start trying to implement a parsing method that I know is flexible enough to recognize the entire class of context free grammars; the Earley parsing algorithm will do just that.

In designing my simple trading simulation language, I’ve been reading up on Haskell a lot lately. For the same reasons that Rich Hickey documents on the Clojure state and identity page, I like the idea of making a simple functional language. I’ve heard that programs written in functional languages are easier to reason about, and I think that that property makes functional code more intuitive to the reader.

My idea is to translate programs written in my simple language into Clojure (compile to Clojure) similarly to how some high level languages translate to C or C++ (e.g. SequenceL). Clojure is expressive enough to represent all of the constructs in my simple language.

One idea I’m stealing from Haskell is to allow functions of two arguments be called using infix notation. For example, given the following definition of the function elementOf? :

elementOf?(e, sequence) = any?(sequence, (item){ e == item } )

elementOf? can be invoked using either of the following notations:

1. elementOf?(1, [1,2,3])
2. 1 elementOf? [1,2,3]

Both invocations will return true.

One cool thing that Haskell and Erlang both support is pattern matching or destructuring. I’m not planning on implementing destructuring anytime soon. Clojure supports destructuring in let bindings, and it has come in handy every one in a while, but it’s not a must have in my language.

Hopefully, people without a CS background will be able to use my language. That’s the idea.

Compilers are a topic in which the phrase "here be dragons" is implied. The classic definitive text on compilers is known as the Dragon Book. I wonder if that was intended.

So, I've decided I'm going to build a simple domain specific language (DSL) for running trading simulations and for stock screening. My former advisor Dr. Rushton told me that he favors general purpose programming languages over DSLs, but I think I can build a DSL that is easy to use while still being very expressive. I began trying to use one of the many PEG parser generators/combinators, but I found out quickly that PEG grammars, like LL grammars, must avoid left-recursive grammar productions. I want to be able to write whatever grammar rule is intuitive for me to write, and avoiding left recursion is not intuitive for me. I recently found out about generalized LR parsers (GLRs) and wanted to implement one, then I read about scannerless GLRs (SGLRs), but there isn't as much information about those as there is about GLRs. I also wanted a simple parser generator/combinator, and I wanted both a Ruby and Javascript implementation. So, I started thinking about how to build a simple bottom up parser, and I have an idea for how to implement one. I believe I can use regular expressions to build all possible parse trees of a given input sentence (i.e. a parse forrest). In the case that more than one parse tree exists for a given sentence, you must have a way to identify which of the parse trees is the "correct" parse tree. In other words, you need a way to prune all parse trees except one from the parse tree forrest. I think I can prune the parse forrest down to one "correct" parse tree as long as the ambiguous grammar rules are assigned a precedence "rank" and as long as rules that have a right-hand-side containing more than one non-terminal indicate which should be parsed first (i.e. some kind of associativity precedence). I'll keep you posted on the details. I'll put the parser up on github.com as soon as I have something to show.