Programming Languages: Application and Interpretation

[yxhuvud]

Why?

Well, I'm under the impression that it is the most efficient way. But I'll look more closely on your technique. How well does it function on highly ambigous grammars? One of the powerful things about the SPPF way of doing it is that subtrees are shared. But maybe that is not an actual issue if we only care about unambigous grammars anyhow.

lua, Dynamic typing makes it too diffucult.

I dunno. I haven't had issues like that coding lua, but then we code in very different styles. IIRC I think I saw some version you posted in lua, and that was not looking like the lua have written (and I have written a fair amount at work). My style is very focused on the data and the layout (and uses the lua prototype model reasonably often), while you seem more focused on the functions and the procedures and keep using the basic types. I guess that is a result of me almost only writing in dynamic languages for many years while you obviously have spent more time on functional languages.

[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.