3 ms·

Disregarding generalized parsing because you can't prove unambiguity is like eschewing Turing-complete languages because you can't solve the halting problem: it

by latk 12y ago

Disregarding generalized parsing because you can't prove unambiguity is like eschewing Turing-complete languages because you can't solve the halting problem: it's short-sighted. In the context of programming language design, an unambiguous syntax is important. However, parsing technology is not exclusively applied to programming languages. Marpa's support for ambiguity and abstract syntax forests can e.g. be used for natural language processing. 10 in 10 joke tellers concur: Ambiguity in the English language is a feature, not a bug. Well, when I use Marpa, I don't actually use abstract syntax forests. But the ability to generate and compare multiple parses, plus especially the ability to inspect the parsing state at an arbitrary point during the parse, are great debugging tools to understand why a given grammar is ambiguous.

haberman 12y ago
I agree that for natural language processing, generalized parsing makes a lot of sense. But since Marpa's documentation and papers compared it to tools like yacc, I analyzed it from the perspective of someone trying to parse programming languages or data formats -- the sort of thing yacc would be used for. Most generalized algorithms (such as GLR) allow you to generate and compare multiple parses. Marpa is not new in this regard. And while I agree that this is useful, it's a "run-time error", so-to-speak. Given a specific input, it can tell you the multiple parses it generated. The benefit of deterministic algorithms is that they can give you this kind of feedback at compile-time. They can generate sample input that would trigger the ambiguity, if they were seen in the wild. I think a static vs. dynamic typing comparison is apt here. A statically typed language can prove that the types are always correct. Dynamic typing defers this checking to runtime, so you don't get the same static guarantees about your program. The same sort of thing can be said of ambiguity checking in deterministic vs. generalized parsing.
aredridel 12y ago
Indeed: And most ambiguity is local, and you can apply other, perhaps more reasonable rules to resolve it than a parser forces you to make.

by latk 12y ago

haberman 12y ago

I agree that for natural language processing, generalized parsing makes a lot of sense. But since Marpa's documentation and papers compared it to tools like yacc, I analyzed it from the perspective of someone trying to parse programming languages or data formats -- the sort of thing yacc would be used for. Most generalized algorithms (such as GLR) allow you to generate and compare multiple parses. Marpa is not new in this regard. And while I agree that this is useful, it's a "run-time error", so-to-speak. Given a specific input, it can tell you the multiple parses it generated. The benefit of deterministic algorithms is that they can give you this kind of feedback at compile-time. They can generate sample input that would trigger the ambiguity, if they were seen in the wild. I think a static vs. dynamic typing comparison is apt here. A statically typed language can prove that the types are always correct. Dynamic typing defers this checking to runtime, so you don't get the same static guarantees about your program. The same sort of thing can be said of ambiguity checking in deterministic vs. generalized parsing.

aredridel 12y ago

Indeed: And most ambiguity is local, and you can apply other, perhaps more reasonable rules to resolve it than a parser forces you to make.