June 2010 Archives

Parsing Perl 2: Down the Garden Path

The Garden Path

In Perl 5.10, the following code is a syntax error:

{42;{1,2,3;4}}
If you try it, what you'll see is something like this:
syntax error at (eval 25) line 1, near ";4"
syntax error at (eval 25) line 1, near "}}

TPP is based on an algorithm called LALR. (To avoid confusion when discussing various programs which parse Perl, I will call the one that comes with the Perl distribution the Tradition Perl Parser, or TPP.) If you look at perly.y, you will find a real achie…

Jay Earley's Idea

Truth == Simplicity?

In other posts, I talked about improvements to Jay Earley's parsing algorithm -- some from Joop Leo, some from Aycock and Horspool, some of mine . Here I'd like to talk about Jay Earley's original algorithm. A common belief of great scientists is that, if an idea is basic and true, it is in essence also simple, and therefore it must have a simple explanation.

Finding the simple explanation might be far from simple. But a simple explanation there ought to be. I like to look for those simple explanations. W…

Parsing with Ruby Slippers

PPI, perly.y and Marpa

Recently I've been combining the two main approaches to parsing Perl. One of these is the PPI module. The other is the parser in the actual Perl distribution. This is usually what is meant when someone speaks simply of "the Perl parser". That can be confusing in this context, so I will call the parser in the distribution, the Traditional Perl Parser (TPP).

I used the grammar in the TPP (it's in perly.y). But I threw out TPP's lexer (/users/jeffrey_kegler/2010/06/index.html

Marpa is now O(n) for Right Recursions

There's news with the latest version of Marpa (0.102000). (Marpa already handled left-recursion in linear time.)

This means that Marpa is now O(n) for all LR-regular grammars. LR-regular means LR with infinite lookahead using regular expressions. That a big class of grammars. It obv…

About Jeffrey Kegler

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