March 2012 Archives

The syntax of English is undecidable

English and other natural languages has come up in the course of my work on the Marpa parser. As in the case of Perl, I first posed the question of whether any algorithm running on a Turing machine can parse the target language. This post contains what I hope the reader will find to be a rigorous demonstration that the syntax of the English language is undecidable.

When I say “undecidable”, I mean that term in the strict sense…

A Marpa mailing list

Ruslan Zakirov has started a Google mailing list for discussions about Marpa: -- I am grateful to Ruslan for doing this and plan to follow the mailing list.

On another topic, I will be removing the "bare name" version of Marpa from CPAN shortly. The "bare name" Marpa is a legacy, deprecated version and is simply causing too much confusion, with search engines and elsewhere. The official, stable version of Marpa remains Marpa:…

Making the parsing game safe

I've talked about Marpa as an alternative to other parsers. In this one, I want to talk about Marpa as an alternative for problems where parsing has been avoided.

Because parsing HAS been avoided in the past. And for good reason. If you were drawn by the allure of domain-specific languages, or yielded to the siren call of language-oriented programming, you plunged headlong toward two pitfalls:

  • Your parser might not parse your grammar. Which you might discover at any point in incremental de…

User experiences with Marpa: some observations

user experiences with Marpa, I confess to being a highly biased source. I hope the following observations will be useful nonetheless. (Marpa, for those new to this blog, is a new, powerful and fast parser and parsing algorithm. To learn more, check out its web page.)

Marpa does the job

If you've read user's accounts of work with BNF grammars over the years (I have studied many), you know they follow a familiar pattern. The user has some BNF. He then tries tool X (for X substitute yacc, bison, PEG, recursive d…

About Jeffrey Kegler

user-pic I blog about Perl, with a focus on parsing and Marpa, my parsing algorithm based on Jay Earley's.