Re: OpenToken: Handling the empty word token

[Stephen Leake <stephen_leake@stephe-leake.org>]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "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.

I'm also on somewhat shakey ground on parser theory, but I did read (and
understand :) "the red dragon book"
(http://en.wikipedia.org/wiki/Principles_of_Compiler_Design), when I
took over OpenToken and fixed some major bugs.

The parser is an LALR parser.

But I think the implementation is not complete. There are no examples of
grammars containing epsilon in the OpenToken tests. I don't remember
what the dragon book has to say about epsilon handling.

So the best approach here is to go back and read the theory about how to
handle epsilon, add some OpenToken tests that use epsilon, and see what
needs to be done.

More than I have the energy for at the moment, but I'm happy to provide
insight into the current code.

-- 
-- Stephe