On 2014-09-20 07:59PM, Loup Vaillant-David wrote:
>By default, Earley recognisers store their Earley items in such a way
>that reconstruction (or back pointer following) happens from right to
>left. Which means the first ambiguities will be detected at the *end*
>of the parse.
But a depth-first traversal turns that around.
>In parsing expression grammars, it's very intuitive. Imagine you
>parse this rule:
>
> A -> B C D
>
>So you parse B, then C, then D (they are written in that order, after
>all). If you detect an ambiguity in B (or anything below it),
>prioritised choice will take care of it. Now imagine there are two
>ways to parse the following input:
>
> _B_ _C_ _D_ -- first possibility
> / \ / \ / \
> a b c d e f -- input
> \_______/ | \___/
> B C D -- second possibility
The left back pointers move back through the rule. So a pre-order
traversal will go like this (I'm using tildes because it was
annoying to copy/paste the bullet):
A -> B C D ~ -- at this step you apply A => B C D.
A -> B C ~ D
A -> B ~ C D
A -> ~ B C D
No more left pointers, so return back up to A -> B ~ C D.
Follow its right pointer to B ... ambiguous! So choose between:
B -> a b ~
B -> a b c ~
Then return back up to A -> B C ~ D and follow its right pointer
to deal with C, etc.
--Josh
_______________________________________________
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc
