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…
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…
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
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…