On Thu, Oct 27, 2016 at 11:48 AM, Sérgio Medeiros <sqmedei...@gmail.com> wrote:
> > This approach may be easier than try to get a PEG without left-recursive > rules directly from a left-recursive CFG. > > Either way, I think you have a tough task :-) > Actually, I see a light at the end of the tunnel... This is the algorithm for elimination in direct left recursion in a CFG: A = A alfa | beta _____________ A = beta A' A' = alfa A' | eps When the target grammar is PEG, the above translates to: A = beta (alfa)* Somehow adding the above to your algorithm would require some sort of rule rewriting, but it would remove the left recursion being bound by the number of choices, and would probably result in implementations much simpler than those of Warth's. > What exactly do you mean by "fail"? > As I said before, the semantics should give a result. > I explained that. Users expect the left-recursive grammar to parse input as if the underlying algorithm was stack-based CFG, so a user reports the parser as failing if the input string is in the CF language and the generated parser doesn't parse it. > In case the semantics gives a result, but the user was expecting > a different parsing tree, then I think it would be preferable to say > that the semantics does not give the expected result. > > Nonetheless, the semantics allows the user to change the precedence > of the operators, and then get the desired associativity. > I understand (there's no misunderstanding). Do you understand my case with my tool's users? > > Personally, because I publish a tool that can be used for > > professional/commercial work, I'm inclined to remove support for left > > recursive grammars until I can provide rules to construct "valid" > > left-recursive grammars. > > Sure, it is a valid option. > You may also disable the support for left-recursion and set > this as the default mode. Yes. It is currently disabled by default, it is labeled as "experimental", and it uses Warth's, because that handles more cases of left-recursive grammars over more inputs. The rewrite I mention above is simple to implement. It would only cover direct left recursion, but the semantics would be defined and (mostly) as expected (because of associativity) for all grammars accepted by the tool. Cheers, -- Juancarlo *Añez*
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
