Re: OpenToken: Handling the empty word token

["Randy Brukardt" <randy@rrsoftware.com>]

"Stephen Leake" <stephen_leake@stephe-leake.org> wrote in message 
news:82ehuibdwt.fsf@stephe-leake.org...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
...
>> I'd be surprised if OpenToken didn't have something similar;
>
> Not quite. Because OpenToken uses Ada types to build the grammar, we
> need an explicit Epsilon token (full code below):

I see. It appears that OpenToken uses an LL-derived parsing scheme. (It 
appears to be a version of recursive descent, which is an LL scheme.] And 
it's important to note that LL parsing cannot include epsilon tokens and 
have problems with left-recursion. LR-derived parsing does not have either 
of these limitations. And note that there is no real workaround to these 
limitations (short of rewriting your grammar); they're inherent in the 
parsing technique.

[Note: I learned all about parsing back in the early 1980's, so (1) I may be 
remembering something wrong, or (2) the state of the art may have changed 
some.]

I would suggest that the OP use a LR-based grammar generator. That won't be 
quite so "pretty" as using "Ada types", but it will work well with almost 
any original grammar that you can throw at it. (I believe that modern parser 
generators use LR(1) tables rather than the LALR(1) tables used in the past; 
LR(1) tables are a lot bigger to generate and we simply didn't have enough 
memory to use that back in the day.)

Hacking an LL-based scheme (such as OpenToken's) to work is pretty much 
doomed to failure. You might get it to work for limited circumstances, but I 
don't think it would work in any general sort of way.

                                         Randy.