4 reduce/reduce parser conflicts resolved
ClosedPublic

Authored by skvadrik on Jul 29 2015, 11:41 AM.

Details

Summary

As GHC documentation (section 7.4.4, Type operators) says:

"There is now some potential ambiguity in import and export lists; for example if you write import M( (+) ) do you mean the function (+) or the type constructor (+)? The default is the former, but with -XExplicitNamespaces (which is implied by -XExplicitTypeOperators) GHC allows you to specify the latter by preceding it with the keyword type"

Turns out this ambiguity causes 4 of 6 reduce/reduce conflicts in GHC parser. All 4 conflicts arise from a single production:

qcname
    :  qvar
    |  oqtycon

Recursive inlining of 'qvar' and 'oqtycon' helps reveal the faulty productions:

qcname
    : 
...
    | '(' QVARSYM ')'
    | '(' VARSYM ')'
    | '(' '*'    ')'
    | '(' '-'    ')'

These productions can either be parsed as variable or type constructor, but variable constuctor is always preferred. My patch removes ambiguity while preserving the existing behaviour:

  • all unambigous productions are left as-is
  • ambigous productions for variable constuctors are left
  • ambigous productions for type constructors are removed (there's no way they could be triggered)

Updated comment.

Test Plan

Tested with 'make fasttest'

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
skvadrik updated this revision to Diff 3702.Jul 29 2015, 11:41 AM
skvadrik retitled this revision from to 4 reduce/reduce parser conflicts resolved.
skvadrik updated this object.
skvadrik edited the test plan for this revision. (Show Details)
skvadrik set the repository for this revision to rGHC Glasgow Haskell Compiler.
skvadrik added a project: GHC.
skvadrik updated this object.Jul 29 2015, 11:42 AM
skvadrik edited edge metadata.
skvadrik updated this object.
skvadrik updated this object.
simonpj requested changes to this revision.Jul 29 2015, 11:51 AM
simonpj edited edge metadata.

Thanks! But a bit of commentary is needed.

compiler/parser/Parser.y
682

Your patch effectively inlines 'oqtycon', with some consequent duplication. That's probably justified to get rid of r/r errors, but it deserves a Note. Otherwise someone in 5 yrs time is going to "cllean it up" by removing the duplication, undoing yoru wor.

Pls add a Note to explain!

Simon

This revision now requires changes to proceed.Jul 29 2015, 11:51 AM
skvadrik updated this revision to Diff 3704.Jul 29 2015, 12:51 PM
skvadrik edited edge metadata.
skvadrik removed rGHC Glasgow Haskell Compiler as the repository for this revision.

Added Note [Type constructors in export list]

I also changed production

qcname_ext
: qcname
| 'type' qcname

to

qcname_ext
: qcname
| 'type' oqtycon

since all type constructors (even conflicting with variable constructors) and only type constructors (but not variable constructors) should be prefixed with 'type'.

trofi edited edge metadata.Jul 29 2015, 2:04 PM
trofi set the repository for this revision to rGHC Glasgow Haskell Compiler.
skvadrik updated this revision to Diff 3705.Jul 29 2015, 2:37 PM
skvadrik updated this object.

Pushed from 'arc' commandline to trigger validate.

simonmar accepted this revision.Jul 30 2015, 4:02 AM
simonmar edited edge metadata.

Thankyou for doing this!

skvadrik updated this revision to Diff 3709.Jul 30 2015, 4:41 AM
skvadrik edited edge metadata.

Added a separate production for restricted type constructors.

Now theer's a better chance that anyone who adds new type constructor
will also add it to production for restricted type constructor.

I've come up with a small refactoring. Sorry, seems I'm late. Didn't expect the patch will be accepted it so soon. :)

bgamari requested changes to this revision.Jul 30 2015, 5:36 AM
bgamari edited edge metadata.

This looks good but I'll mark it as needing changes while you refactor.

This revision now requires changes to proceed.Jul 30 2015, 5:36 AM

I meant that current diff (3709) is the refactored one. I added it after simonpj marked patch as 'accepted'. So now I have nothing else to fix. :)

skvadrik edited edge metadata.Jul 30 2015, 6:04 AM
bgamari accepted this revision.Jul 30 2015, 6:52 AM
bgamari edited edge metadata.

Great! Thanks again!

My pleasure :)

trofi accepted this revision.Jul 30 2015, 7:03 AM
trofi edited edge metadata.

Yay! Less conflicts!

Thank you!

skvadrik marked an inline comment as done.Jul 31 2015, 3:11 PM
skvadrik requested a review of this revision.Jul 31 2015, 3:13 PM
skvadrik edited edge metadata.
This revision was automatically updated to reflect the committed changes.