[Haskell-cafe] Haskell grammar ambiguity

[Li-yao Xia]

Thanks for your great answer, Askar. Using happy to optimistically test 
for ambiguity is a great idea, and I'll be sure to check your other 
references.


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


Right now I'm trying to understand Haskell's concrete syntax enough to

1. Teach it (with "better parser error messages" as a potential subgoal)
2. Implement it (as a concrete lower bound for the abstract goal of 
"completely understand it")

And right now it seems reading the Haskell2010 report and also 
GHC/Parser.y is not enough. One also has to think hard on top of that. 
This can usually be fixed by producing a better reference document.

Li-yao


On 6/16/2021 10:22 AM, Askar Safin wrote:
>> 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
>