Why Sponsor Oils? | blog | oilshell.org

Pratt Parsers Can Be Statically Typed


Today I have one more short note on Pratt parsing, which came up in e-mail.

In trying to explain why Pratt parsing was not well known in 2007, Crockford's TDOP article says:

Another explanation is that his technique is most effective when used in a dynamic, functional programming language.


Pratt's technique wants a dynamic language, but dynamic language communities historically have had no use for the syntax that Pratt's technique conveniently realizes.

I believe this is false, and that the code I posted on Github and sketched in a previous entry proves it false. There's nothing about Pratt's technique that makes it more suited for a dynamic language. Crockford's code makes use of prototypal inheritance, which only appears in dynamic languages, but I explicitly argued against that style.

Although I wrote my demo in Python, it uses a "static" C++- or Java-like object-oriented structure. There are two main classes: Parser and ParserSpec. The inputs are a stream of Token objects and the output is a tree of Node objects. There's nothing inherently dynamic about this.

Further evidence is that you can find multiple implementations of Pratt parsing in C++, Java, and C# on the web, and there's nothing particularly dynamic about them either. They do tend to use virtual dispatch following Crockford's style, but there would be no problem using the style I presented instead.

OK, this will be the last post on Pratt parsing. Tomorrow we'll return to the shell language and show that arrays have a poor design.

Related: Pratt Parsing Index and Updates