On Sat, Oct 8, 2016 at 11:41 PM, Juancarlo Añez <apal...@gmail.com> wrote: > I implemented a version Medeiro et al's[3] algorithm in Grako. I don't know > what I did that for, because it should be easy to prove that an algorithm > that sets a bound to recursion will fail for certain grammars and inputs.
Hi, Juancarlo. Lemma 2 (or Lemma 3.2 in https://arxiv.org/abs/1207.0443) states that the semantics always gives a result (a matching succeeds or fails). For some grammars the semantics may give a result which does not seem correct for a given application, or it is not similar to the result we would get by using a CFG instead of a PEG. > What disappoints me about the papers is that they don't characterize the > grammars for which the algorithms do work. > > Not all left-recursive grammars are LR, and only LR grammars will parse with > LR algorithms. 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. 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. The paper about left-recursion has examples where the semantics gives an useful result for common left-recursive idioms from Context-Free Grammars, but there is no general guarantee. > Which set of grammars are PEG+Left_Recursion_Alg_X? > > The need for left-associativity in expressions can be handled in several > different ways in a PEG parser, without trying to make a PEG parser parse > with left-recursive grammars. 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. 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. -- Sérgio _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
