Peter Cashin wrote: > Sergio and Peter: > > I am interested in this topic. > > I have been using an implementation that is quite a bit simpler than Warth > etal. It has no problem with their test case grammar (after fixing their > typo error). I have a draft note on how it works that I can pull out and > clean up for anyone interested. > > But now I see Peter Goodman's grammar! > > Matching: "dcccbbaaa" etal works fine, but I'm not sure what other strings > this grammar should match....
Dropping the quotes for readability (and ignoring the difference between
prioritized and ordered choice which doesn't matter here), we have:
A <- A a | B
B <- B b | A | C
C <- C c | B | d
left-factoring A, B and C individually:
A <- B a*
B <- (A | C) b*
C <- (B | d) c*
substituting for B in A and C:
A <- (A | C) b* a*
C <- ((A | C) b* | d) c*
expanding A:
A <- A b* a* | C b* a*
left-factoring A and simplifying:
A <- C b* a* (b* a*)*
A <- C (a | b)*
therefore:
A | C = C (a | b)* | C
= C (a | b)*
substituting A | C into C:
C <- (C (a | b)* b* | d) c*
C <- (C (a | b)* | d) c*
expanding C:
C <- C (a | b)* c* | d c*
left-factoring C and simplifying:
C <- d c* ((a | b)* c*)*
C <- d c* (a | b | c)*
C <- d (a | b | c)*
One might come to the conclusion that the best approach to left-recursion
is to remove it rather than supporting it directly, although obviously we
shouldn't take a single contrived example as providing strong support for
that conclusion.
====
>> A <- A 'a'
>> <- B
>>
>> B <- B 'b'
>> <- A
>> <- C
>>
>> C <- C 'c'
>> <- B
>> <- 'd'.
>>
>> That is a fairly contrived example, however, the main problems I had
>> that I eventually could not overcome was with the
>> intertwining/braiding of A and B. If your semantics are able to
>> properly handle such awful grammars then I think that would be
>> excellent and I would be really interested in reading more in-depth
>> into them.
--
David-Sarah Hopwood ⚥ http://davidsarah.livejournal.com
signature.asc
Description: OpenPGP digital signature
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
