From: John Carter <john.carter@...>
Date: 2004-02-12T10:40:03+09:00
Subject: Re: Simple parsing of sloppy HTML - LittleLexersame

On Thu, 12 Feb 2004, Clifford Heath wrote:

> John Carter wrote:
> > http://littlelexer.rubyforge.org/
>
> Cute, but it's not a parser, it's a composite lexer.
> A regular expression engine cannot *parse* context-free grammars (like
> most programming languages), even if you can layer them like this.


Yes and no.

It's a while since I did the theory courses so forgive me if my
details as to whether something is LR or LL is wrong....

Note 1: If I remember correctly even a full "parser generator" like yacc/Bison
cannot recognize an arbitrary CFG. They only recognize a limited subset
like LL(1)

Thus LittleLexer is a parser in the same sense that yacc/Bison are,
but the subset of CFG's it can recognize is more limited.

Note 2: The fundamental limitation on regex's as a parser is they
don't cope with nested structures.

So as a mental exercise I was trying to visualize how I would get
LittleLexer to chew on that simplest and best poster child example of
a "nested" language, s-expressions. (Lisp like expressions)

The answer is quite simple in that case, have a lexer pass, no surprise.
And then have a pass that recognizes unbracketed regions.
%r{\([^\(\)]*\)} maps to 'f'

eg.

(+ (- 30 20) 10)

Feed it to the lexer and it outputs...
'(+(-dd)d)', ['(','+','(','-','30','20',')','10',')']

Feed it to the parser and it produces....

'(+fd)', ['(','+','(-dd)','d',')']

Feed it back into exactly the same little lexer instance and you have...
'f', '['(+fd)']

Now there is an option on the LittleLexer scan method that allows you
to pass in the resulting token list from the previous pass so what you
get is a AST (Abstract Syntax Tree) of the s-expression. Voila!
LittleLexer parsed a language that is not a regular expression.

The LispParser as a proof of concept is easy to do. What I want to do
for version 2 of LitteLexer is generalize the notion of handling
nested structures like that. But since the whole thing is a "late
night, can't sleep" project, I'm stilling mulling over what I mean by
"nested structure".

For example consider Ruby if/else expressions...

if a
  dostuff
  if b
   do_more_stuff
  else
   dothing
  end
end

Would map to something like....
if => 'i'
statement => 's'
else => 'l'
end => 'e'
expression => 'x'

So that would be...
'ixsixslsee'

So we could have a regex that recognized "atomic" if/else statements...
[/ixs+(ls)?e/, 's']

For example, a LL(1) parser must be able to decide what path it is
going down by one token of look ahead. In a sense this iterative
approach I'm using is a bit better off. I can use the entire string to
decide whether I have an atomic item or a nested item.

So why doesn't Bison and the like do this? Because it is slow, the
whole art and science of compiler compiler's evolved in days of very
slow computers trying to do far more than they had power for.

On the other hand it is not too slow as Ruby's regex engine is really
very good and I'm only manipulating strings and pointers which are
typically an order of magnitude smaller than the original file.





John Carter                             Phone : (64)(3) 358 6639
Tait Electronics                        Fax   : (64)(3) 359 4632
PO Box 1645 Christchurch                Email : john.carter@tait.co.nz
New Zealand

Note to all marketers. If you want to sell things to me, buy Google words.

I refuse on principle to buy anything sold by spam or popup and I
never follow any links found in a spam. I do however use Google and
will often follow the neat non-irritating Google Word ads that are of
interest to me.