"Andrei Alexandrescu" <[email protected]> wrote in message news:[email protected]... > On 2/29/12 11:15 AM, Nick Sabalausky wrote: >> "Andrei Alexandrescu"<[email protected]> wrote in message >> news:[email protected]... >>> 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.
