From: Aredridel <aredridel@...>
Date: 2005-03-01T15:57:56+09:00
Subject: Re: Parsers vs. Homemade "Parsing" via REs

> My impression is that some or many wikis (this is my impression of TWiki)
> don't use a "real parser" (like YACC or whatever), but instead simply search
> and replace in the text using (many) Regular Expressions.  Conceptually, that
> seems an easy approach (less learning on my part, but probably tedious
> creation of many REs (or borrowing from TWiki's Perl).

I've written a wiki, though in PHP, not Ruby (yet; I'm porting)

The parser is basically recursive-descent, hand-coded, with an
insanely complex regex tokenizer.

Parsing human text with a strict parser (like racc/yacc) is Really
Hard -- the LALR(1) algorithm has too many limits to do it justice. 
Even fitting it into a GLR shaped box is hard, though I'm trying to in
my rewrite.

Your best bet is probably to use a hand-coded Recursive Descent
parser,  where you drag in big blobs of text, divvy it up into
successively smaller pieces, calling the parser for each recursion,
with fewer and fewer options remaining. The parsing might go like so:

With the input paragraph:

_/hi/, there_

and the markup objects "Bold" and "italic" and "plain"

your parser might match a single token: "bold text"

Then you strip the _ _, and you have 

/hi/, there

Your parser would recognize two tokens: "italic text" (hi), and plain
(", there")

It'd strip each: plain(hi), and then nothing further would match.

Your structure in memory would look like this:

Bold(Italic("hi")."there")

Which is then pretty trivial to mark up as HTML.

The funky cases come in things not easily tokenized: lists,
particularly, are a pain. My current parser does ugly things like
guess whether something is list-like, hands the whole blob to a
listifier routine, which then throws out any plaintext bits for
rendering. Ugly, but works.

A GLR parser, on the other hand, instead of breaking things down,
builds them up -- with rules like "_", anything, "_" is bold, you'd
break your stream down into tokens like so:

Literal(_) Literal(/) Text(hi) Literal(/) Text(, there) Literal(_)

And then with the rules "_", anything, "_" -> bold
"/", anything, "/" -> italic
italic*|bold*|plain* -> anything 
else -> plain

The parser could then reduce that to the same above structure. Problem
is, that takes many tokens of look-ahead, so the parser could get
slow.

an LALR(1) parser is just like above, except that the rules can only
use one token of look-ahead to figure out what to do. Obviously, for
the enormous variety in human text, that's a huge limit.

Hope that makes some sense.

Ari

P.S. Why not search and replace? Assume "/" means italic and "-" means
bold. Then parse this:

http://www.amazon.com/exec/obidos/tg/browse/-/3348291/ref%3Dbr%5Fbx%5Fc%5F2%5F2/002-2563138-3700849/-/foo/002-2563138-3700849

And try not to get <a href='....<em> <strong>....' ...