[Haskell-cafe] Haskell grammar ambiguity

[Askar Safin]

> 3. Is this grammar unambiguous?
It is unambiguous.

I converted in into happy grammar ( https://www.haskell.org/happy/ ). Here is result: https://paste.debian.net/1201427/ . Then I run "happy" binary on it and got no output. This means that "happy" was able to check that this CFG is element of particular class of grammars (as well as I understand this is LALR(1) class), and thus is unambiguous.

But this result is useless, because I simply assumed that symbols "type", "qvar" and others are unique terminals (I listed them as tokens in happy grammar). This is not true. For example, string "a" can be "type" and in the same time "qvar". So I suggest writing proper happy grammar with unique terminals.

(Also, I converted your grammar to happy's manually, it is possible I did some mistake.)

Some additional notes (with a bit of advertisement).

Checking whether given CFG is ambiguous is in general impossible to do on Turing machine, this is theorem. So none of existing tools will give you answer for any grammar.

Happy checks whether a grammar is element of particular class (as well as I understand, LALR(1)). If it is, happy prints nothing, this means, this is LALR(1) grammar, and thus unambiguous. If not, happy reports conflicts. But this doesn't mean the grammar is ambiguous. It can be ambiguous or unambiguous.

My package http://hackage.haskell.org/package/check-cfg-ambiguity can check grammar, too. It reports given CFG either as certainly ambiguous or as possibly unambiguous. Still I was unable to find grammar, arising from practice, which can fool my package. Setting count of steps as 20 will give you very low probability of mistake. (Again: "probability of mistake" means probability of answer "it is unambiguous" being false, answer "it is ambiguous" is always certainly true.)

Also you can try this package: https://www.brics.dk/grammar/ for checking ambiguity.

I spent lot of time learning various methods of checking ambiguity, feel free to ask me questions. Add me to CC in case i will unsubscribe from this list.

I like your desire to give proper grammar for Haskell. What you want? Fixing Haskell Report? Well, this would be very good, unfortunately Haskell Report process is staled ( https://reasonablypolymorphic.com/blog/haskell202x/ ). Of course, I hope it will resurrect.

Also, I agree that BlockArguments was mistake.

Also, grammar given in Haskell Report 2010 and grammar from ghc source tree are 2 completely different things, see here: https://mail.haskell.org/pipermail/haskell-cafe/2021-April/133847.html

==
Askar Safin
http://safinaskar.com
https://sr.ht/~safinaskar
https://github.com/safinaskar