From: Markus Liedl Date: 2007-11-17T18:35:01+09:00 Subject: Re: Alternative Ruby grammar On Nov 16, 4:54 pm, Eric Mahurin wrote: > ... > Great work Mark! thanks. > How does this grammar compare with the one the antlr one done by the > "grammarians"? Did you start from there or from scratch? I did start from scratch, trying to keep the underlying generator definition language as simple as possible. > I looks like you have a unified lexer/parser. With all of the ruby parser > dependent lexer states, I can see why this might be easier. But, this is > probably also why you might be losing performance (and why you need > memoization), right? I'm guessing there might be some backtracking needed? Thanks to memoization this grammar runs in linear time (mostly, I believe). Over-linear time (without memoization) is caused by only a few rules that directly or indirectly apply other rules multiple times at the same input position. And I'm using selective memoization. Only rules that profit from it get memoized, since lookup in the memoization table costs too. That's one of the things not yet fully optimized in the C parser. I spent some time determining the set of memoized rules when writing the elisp backend, but didn't do the same again for the C parser, though the relative costs of various operations may differ greatly. But I don't understand your proposition about backtracking. PEG based parser do naturally backtrack at certain situations. Definit Clause Grammar from Prolog are "more" backtracking, they care to find every possible parse, which PEG do not. If you'd write (or aa bb cc) a PEG parser will try to parse first aa. If this succeeds, it will never try bb or cc at the given position. Thats why they are called non-exhaustively backtracking. > Do you have (E)BNF of this LL grammar, or just gram.lisp? No, there is no other format of this grammar. gram.lisp is the source. > I'm thinking one of my next steps for my ruby-forge Grammar package (LL > grammar specified in BNF-like ruby) would be to write a (E)BNF parser to be > able to translate BNF from antlr/yacc/racc/etc. Even though mine is LL, I > handle some amount of left recursion. Of course, I'd > like to target a ruby (E)BNF working. You might have a look at the file deflang.txt. All the forms I used are described there. If you wanted to adapt this grammar you need solutions for such arcane forms as "postpone-rest-of-line" which is needed for parsing here-docs and "again" which parses a previously seen string again. Just two examples.