On Mon, Oct 10, 2016 at 8:54 AM, Sérgio Medeiros <sqmedei...@gmail.com> wrote:
> We need to take some care here. It is difficult to establish a general > relation between CFGs and PEGs in order to guarantee that a grammar > G will give us the same result when interpreted as a CFG and when > interpreted as a PEG. > Indeed. I've mean to refer to the "set of languages expressible with grammars of type X". It's likely I wasn't precise in what I said. > 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. I've kept left recursion in Grako because I reckon the tool is used in teaching, where allowing some simple forms of left recursion may be useful, but just mentioning the experimental support for left recursive grammars sets the wrong expectations. For example, when limits are found in the current implementation of Warth's algorithm are found, they are reported as bugs against the parser generator. > Well, I think you can say the same about parsers based on CFGs, you can > build an AST with left-associativity operators without a left-recursive > CFG. > > Usually, it is easier to build a left-associative with a left-recursive > grammar > than with a right-recursive one, but you can choose which strategy to use. > "The 'correct' associativity" is just one of the expectations of users new to parsing. > 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. 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. Cheers, -- Juancarlo *Añez*
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
