Sylvain Schmitz wrote:
>A good first test to check whether (a rather strong) equivalence might
>hold would be to verify that the grammar corresponding to the PEG
>
> A <- a A a / a
>
>recognizes the same language as the PEG, namely {a^(2^n - 1) | n > 0}
>(i.e. 2^n-1 consecutive `a' symbols, starting with 1, 3, 7, 15, etc.).
>This example of a non context-free language seems to me like a good
>start---if your parser recognizes any odd number of `a' tokens instead,
>then it's not a PEG parser.
Thanks for the suggestion. APG 5.0 seems to pass this test OK. With this
grammar, successively parsing strings, a^n, 1<= n <= 16, I get matches for
1, 3, 7 and 15 and no matches for the others.
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 didnt 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.
>Does your library avoid this problem Lowell?
Im not sure what problem you are referring to. My understanding is that
determinate means LL(k) and non-determinate means backtracking. 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.
Lowell Thomas
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
