On 10/9/07, Lowell Thomas <[EMAIL PROTECTED]> wrote: > Christopher Diggins wrote: > >However, the documentation of Boost.Spirit describes it as > >non-deterministic. I am unsure exactly why they say this, but I > >suspect that it is because the order of evaluation of arguments to a > >function is not specified in the C++ standard. > > I was unfamiliar with Boost.Spirit. With a quick scan of their documentation > I didn't see any specific mention of "non-deterministic", but they did have > this to say about alternates. > > "Alternative operands are tried one by one on a first come first served > basis starting from the leftmost operand. After a successfully matched > alternative is found, the parser concludes its search, essentially > short-circuiting the search for other potentially viable candidates." > > I would interpret this to mean that their parsers back track > (non-deterministic) and use prioritized-choice disambiguation.
They mention it here: http://www.boost.org/libs/spirit/doc/techniques.html . If you use prioritized-choice disambiguation, then I would consider that unambiguous. As I understand this to be the point that Bryan Ford is trying to make in his PEG paper. I am unfamiliar with the interpretation of back-tracking to mean non-deterministic, but I am new to the field of research. > >Does your library avoid this problem Lowell? > > I'm not sure what problem you are referring to. My understanding is that > determinate means LL(k) and non-determinate means backtracking. Perhaps my interpretation is mistaken. > APG 5.0 is a > back tracking parser, not LL(k). However, one of its new features is > "partial determinism". That is, it uses tables to be determinant when the > look ahead symbol is sufficient to decide and is backtracking when not. Hope > this answers your question. I was wondering whether choice rules in your grammar were applied in a predicatable (i.e. prioritized) manner. Regardless, your approach sounds like a creative blend of techniques. > Lowell Thomas Cheers, - Christopher Diggins _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
