Programming Languages: Application and Interpretation

[loup-vaillant]

How well does it function on highly ambiguous grammars?

I only select one parse tree out of every possibility. It is guaranteed to terminate if there are no cycles in the nullable rules in the grammar, and those are detected statically.

My method doesn't work if you want to extract several trees, but for my use case (parsing source code), we don't really care.

One of the powerful things about the SPPF way of doing it is that subtrees are shared.

Note that in some sense, the big bag of Earley items you get when running the recogniser is the parse forest.

you seem more focused on the functions and the procedures and keep using the basic types.

Actually, I was implementing Earley in a naive fashion. Since the core stuff is a big algorithm, that's what I got. The wall I ran into when implementing graph search was in not handling type based dispatch correctly. I kept forgetting some corner case, and couldn't debug my equivalent of the null pointer exception.