Lexer and parser generators using CTFE

[Nick Sabalausky]

"Andrei Alexandrescu" <SeeWebsiteForEmail at erdani.org> wrote in message 
news:jilnjg$1eu9$3 at digitalmars.com...
> On 2/29/12 11:15 AM, Nick Sabalausky wrote:
>> "Andrei Alexandrescu"<SeeWebsiteForEmail at erdani.org>  wrote in message
>> news:jiljsg$193s$1 at digitalmars.com...
>>> On 2/28/12 1:52 PM, Dmitry Olshansky wrote:
>>>> - have reasonable compile times and memory consumption (though it will
>>>> only improve over time)
>>>
>>> Yes. I guess PEGs have problems there.
>>>
>>
>> Probably LR, too, unless you build the state tables in a separate prior
>> build step.
>
> It's been a while since I read about PEGs (the packrat parser paper), but 
> think it's a more fundamental issue with PEGs because they need to memoize 
> several possible parses of the input.
>

I don't know much about packrat parsers, but what I meant is that generating 
LALR tables (which are then used by an LALR parser) can be very 
computationally expensive: For simple grammars, it's trivial, but for more 
complex "typical programming langauge" grammars, it can easily take upwards 
of quite a few minutes when *not* done in CTFE (at least on my underpowered 
machine). Although maybe my implementation and GOLD's implementation both 
just have some additional hidden scaling issue that isn't inherent to the 
algorithms?

Actually using an *already*-generated LALR table (which only needs to be 
generated once per grammar, not once per input) to parse doesn't have major 
inherent efficiency issues compared to other parsing algorithms, AFAIK.