On Wed, Oct 26, 2016 at 10:09 PM, Juancarlo Añez <apal...@gmail.com> wrote: >> I have worked on this subject (https://arxiv.org/abs/1304.3177), but we >> did not establish a relation between an LR grammar interpreted as a CFG >> and what would be an equivalent PEG. > > > Thanks for the reference. I'll study it. > > My work is in parsing applied to large collections of text in legacy > programming languages. Finding an algorithm that finds the equivalent PEG > grammar for an LR one, or the likes, is more interesting than PEG+Left.
Hi, Juancarlo. As LR Grammars are usually written using left-recursion, in case you did not want to use PEG + left I think you will need first to eliminate left recusion from a LR CFG grammar G, this will give you G', and then try to obtain a PEG equivalent to G'. 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 :-) >> In case you have examples of left-recursive grammars which do not give >> the expected result when interpreted as a PEG, you can post them here. > > > The implementation of Warth's algorithm in Grako drops information about > associativity when it enters the iterative step. I hadn't noticed until I > implemented your algorithm, which does recover associativity, because I > don't use left recursion in my work. > > Left or right associativity doesn't matter because it is easy to convert one > to the other when the parsing semantics are none. If there's no > associativity (the AST is flat), then another parsing step would be required > to impose the associativity. > > If you care about the examples, I can recover some from the unit tests for > left-associativity in Grako. Your algorithm passes the cases included in bug > reports against Grako, but fails to parse cases that the current Warth > implementation passes. What exactly do you mean by "fail"? As I said before, the semantics should give a result. I would say that it "fails" when it does not give a result (e.g., it keeps calling the same rule multiple times without stopping the recursion). 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. > 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. -- Sérgio _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
