more parser conflicts?
Hi devs, In unrelated work, I saw this scroll across when happy'ing the parser:
shift/reduce conflicts: 60 reduce/reduce conflicts: 16
These numbers seem quite a bit higher than what I last remember (which is something like 48 and 1, not 60 and 16). Does anyone know why? Thanks, Richard
On Mon, 1 Dec 2014, Richard Eisenberg wrote:
In unrelated work, I saw this scroll across when happy'ing the parser:
shift/reduce conflicts: 60 reduce/reduce conflicts: 16
These numbers seem quite a bit higher than what I last remember (which is something like 48 and 1, not 60 and 16). Does anyone know why?
The offending commit is bc2289e13d9586be087bd8136943dc35a0130c88. I know this because I was changing the parser for patsyn signatures, and so I updated the numbers in Parser.y to make sure I'm not adding any new conflicts: 25 June 2014 Conflicts: 47 shift/reduce 1 reduce/reduce but then when time came to rebase my changes before pushing, I noticed that it has gone up, and I had to update it yet again in Parser.y: 20 Nov 2014 Conflicts: 60 shift/reduce 12 reduce/reduce So anyway, the point is, if you try bc2289e and bc2289e^ you can see that that is the commit that introduced these new conflicts.
reduce/reduce conflicts are bad, especially so since they're undocumented. We don't know whether this introduced parser bugs or not. Mike - could you look at this please? It was your commit that introduced the new conflicts. Cheers, Simon On 02/12/2014 10:19, Dr. ERDI Gergo wrote:
On Mon, 1 Dec 2014, Richard Eisenberg wrote:
In unrelated work, I saw this scroll across when happy'ing the parser:
shift/reduce conflicts: 60 reduce/reduce conflicts: 16
These numbers seem quite a bit higher than what I last remember (which is something like 48 and 1, not 60 and 16). Does anyone know why?
The offending commit is bc2289e13d9586be087bd8136943dc35a0130c88. I know this because I was changing the parser for patsyn signatures, and so I updated the numbers in Parser.y to make sure I'm not adding any new conflicts:
25 June 2014
Conflicts: 47 shift/reduce 1 reduce/reduce
but then when time came to rebase my changes before pushing, I noticed that it has gone up, and I had to update it yet again in Parser.y:
20 Nov 2014
Conflicts: 60 shift/reduce 12 reduce/reduce
So anyway, the point is, if you try bc2289e and bc2289e^ you can see that that is the commit that introduced these new conflicts. _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
Indeed! Even documented, this seems like way too many reduce/reduce conflicts---we should be able to refactor the grammar to avoid them. On Wed Dec 03 2014 at 3:59:48 AM Simon Marlow <marlowsd@gmail.com> wrote:
reduce/reduce conflicts are bad, especially so since they're undocumented. We don't know whether this introduced parser bugs or not. Mike - could you look at this please? It was your commit that introduced the new conflicts.
Cheers, Simon
On 02/12/2014 10:19, Dr. ERDI Gergo wrote:
On Mon, 1 Dec 2014, Richard Eisenberg wrote:
In unrelated work, I saw this scroll across when happy'ing the parser:
shift/reduce conflicts: 60 reduce/reduce conflicts: 16
These numbers seem quite a bit higher than what I last remember (which is something like 48 and 1, not 60 and 16). Does anyone know why?
The offending commit is bc2289e13d9586be087bd8136943dc35a0130c88. I know this because I was changing the parser for patsyn signatures, and so I updated the numbers in Parser.y to make sure I'm not adding any new conflicts:
25 June 2014
Conflicts: 47 shift/reduce 1 reduce/reduce
but then when time came to rebase my changes before pushing, I noticed that it has gone up, and I had to update it yet again in Parser.y:
20 Nov 2014
Conflicts: 60 shift/reduce 12 reduce/reduce
So anyway, the point is, if you try bc2289e and bc2289e^ you can see that that is the commit that introduced these new conflicts. _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs
On Wed, 03 Dec 2014 11:59:42 +0000 Simon Marlow <marlowsd@gmail.com> wrote:
In unrelated work, I saw this scroll across when happy'ing the parser:
shift/reduce conflicts: 60 reduce/reduce conflicts: 16
These numbers seem quite a bit higher than what I last remember (which is something like 48 and 1, not 60 and 16). Does anyone know why?
4 of reduce/reduce conflicts are result of exact rule copy: https://phabricator.haskell.org/D569
reduce/reduce conflicts are bad, especially so since they're undocumented. We don't know whether this introduced parser bugs or not. Mike - could you look at this please? It was your commit that introduced the new conflicts.
Agreed. 11 more reduce/reduce (of left 12) came from single scary rule added in
commit bc2289e13d9586be087bd8136943dc35a0130c88 ghc generates more user-friendly error messages
exp10 :: { LHsExpr RdrName } ... | 'let' binds {% parseErrorSDoc (combineLocs $1 $2) $ text "parse error in let binding: missing required 'in'" } The other rules add shift/reduce conflicts as follows: -- parsing error messages go below here {- s/r:1 r/r:0 -} | '\\' apat apats opt_asig '->' {% parseErrorSDoc (combineLocs $1 $5) $ text "parse error in lambda: no expression after '->'" {- s/r:1 r/r:0 -} | '\\' {% parseErrorSDoc (getLoc $1) $ text "parse error: naked lambda expression '\'" } {- s/r:1 r/r:0 -} | 'let' binds 'in' {% parseErrorSDoc (combineLocs $1 $2) $ text "parse error in let binding: missing expression after 'in'" } {- s/r:0 r/r:11 -} | 'let' binds {% parseErrorSDoc (combineLocs $1 $2) $ text "parse error in let binding: missing required 'in'" } {- s/r:0 r/r:0 -} | 'let' {% parseErrorSDoc (getLoc $1) $ text "parse error: naked let binding" } {- s/r:1 r/r:0 -} | 'if' exp optSemi 'then' exp optSemi 'else' {% hintIf (combineLocs $1 $5) "else clause empty" } {- s/r:2 r/r:0 -} | 'if' exp optSemi 'then' exp optSemi {% hintIf (combineLocs $1 $5) "missing required else clause" } {- s/r:1 r/r:0 -} | 'if' exp optSemi 'then' {% hintIf (combineLocs $1 $2) "then clause empty" } {- s/r:2 r/r:0 -} | 'if' exp optSemi {% hintIf (combineLocs $1 $2) "missing required then and else clauses" {- s/r:2 r/r:0 -} | 'if' {% hintIf (getLoc $1) "naked if statement" } {- s/r:0 r/r:0 -} | 'case' exp 'of' {% parseErrorSDoc (combineLocs $1 $2) $ text "parse error in case statement: missing list after '->'" } {- s/r:1 r/r:0 -} | 'case' exp {% parseErrorSDoc (combineLocs $1 $2) $ text "parse error in case statement: missing required 'of'" } {- s/r:1 r/r:0 -} | 'case' {% parseErrorSDoc (getLoc $1) $ text "parse error: naked case statement" } Shift/reduces look harmless (like MultiWayIf ambiguity) as they seem to resolve as shift correctly. -- Sergei
On Sat, 13 Dec 2014 15:19:34 +0000 Sergei Trofimovich <slyich@gmail.com> wrote:
On Wed, 03 Dec 2014 11:59:42 +0000 Simon Marlow <marlowsd@gmail.com> wrote:
In unrelated work, I saw this scroll across when happy'ing the parser:
shift/reduce conflicts: 60 reduce/reduce conflicts: 16
These numbers seem quite a bit higher than what I last remember (which is something like 48 and 1, not 60 and 16). Does anyone know why?
4 of reduce/reduce conflicts are result of exact rule copy: https://phabricator.haskell.org/D569
reduce/reduce conflicts are bad, especially so since they're undocumented. We don't know whether this introduced parser bugs or not. Mike - could you look at this please? It was your commit that introduced the new conflicts.
Agreed.
11 more reduce/reduce (of left 12) came from single scary rule added in
commit bc2289e13d9586be087bd8136943dc35a0130c88 ghc generates more user-friendly error messages
exp10 :: { LHsExpr RdrName } ... | 'let' binds {% parseErrorSDoc (combineLocs $1 $2) $ text "parse error in let binding: missing required 'in'" }
The other rules add shift/reduce conflicts as follows:
-- parsing error messages go below here {- s/r:1 r/r:0 -} | '\\' apat apats opt_asig '->' {% parseErrorSDoc (combineLocs $1 $5) $ text "parse error in lambda: no expression after '->'" {- s/r:1 r/r:0 -} | '\\' {% parseErrorSDoc (getLoc $1) $ text "parse error: naked lambda expression '\'" } {- s/r:1 r/r:0 -} | 'let' binds 'in' {% parseErrorSDoc (combineLocs $1 $2) $ text "parse error in let binding: missing expression after 'in'" } {- s/r:0 r/r:11 -} | 'let' binds {% parseErrorSDoc (combineLocs $1 $2) $ text "parse error in let binding: missing required 'in'" } {- s/r:0 r/r:0 -} | 'let' {% parseErrorSDoc (getLoc $1) $ text "parse error: naked let binding" } {- s/r:1 r/r:0 -} | 'if' exp optSemi 'then' exp optSemi 'else' {% hintIf (combineLocs $1 $5) "else clause empty" } {- s/r:2 r/r:0 -} | 'if' exp optSemi 'then' exp optSemi {% hintIf (combineLocs $1 $5) "missing required else clause" } {- s/r:1 r/r:0 -} | 'if' exp optSemi 'then' {% hintIf (combineLocs $1 $2) "then clause empty" } {- s/r:2 r/r:0 -} | 'if' exp optSemi {% hintIf (combineLocs $1 $2) "missing required then and else clauses" {- s/r:2 r/r:0 -} | 'if' {% hintIf (getLoc $1) "naked if statement" } {- s/r:0 r/r:0 -} | 'case' exp 'of' {% parseErrorSDoc (combineLocs $1 $2) $ text "parse error in case statement: missing list after '->'" } {- s/r:1 r/r:0 -} | 'case' exp {% parseErrorSDoc (combineLocs $1 $2) $ text "parse error in case statement: missing required 'of'" } {- s/r:1 r/r:0 -} | 'case' {% parseErrorSDoc (getLoc $1) $ text "parse error: naked case statement" }
Shift/reduces look harmless (like MultiWayIf ambiguity) as they seem to resolve as shift correctly.
Proposed fix as: https://phabricator.haskell.org/D571 Simon, is using happy's "error" token the proper way of fixing these error reporting rules? Thanks! -- Sergei
It would be great to have a patch that documents all this Simon | -----Original Message----- | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of | Sergei Trofimovich | Sent: 13 December 2014 15:20 | To: GHC Devs | Cc: Simon Marlow; Dr. ERDI Gergo; Mike Izbicki | Subject: Re: more parser conflicts? | | On Wed, 03 Dec 2014 11:59:42 +0000 | Simon Marlow <marlowsd@gmail.com> wrote: | | > >> In unrelated work, I saw this scroll across when happy'ing the | parser: | > >> | > >>> shift/reduce conflicts: 60 | > >>> reduce/reduce conflicts: 16 | > >> | > >> These numbers seem quite a bit higher than what I last remember | > >> (which is something like 48 and 1, not 60 and 16). Does anyone | know why? | | 4 of reduce/reduce conflicts are result of exact rule copy: | https://phabricator.haskell.org/D569 | | > reduce/reduce conflicts are bad, especially so since they're | > undocumented. We don't know whether this introduced parser bugs or | not. | > Mike - could you look at this please? It was your commit that | > introduced the new conflicts. | | Agreed. | | 11 more reduce/reduce (of left 12) came from single scary rule added | in | > commit bc2289e13d9586be087bd8136943dc35a0130c88 | > ghc generates more user-friendly error messages | | exp10 :: { LHsExpr RdrName } | ... | | 'let' binds {% parseErrorSDoc (combineLocs $1 $2) $ text | "parse error in let binding: missing | required 'in'" | } | | The other rules add shift/reduce conflicts as follows: | | -- parsing error messages go below here | {- s/r:1 r/r:0 -} | | '\\' apat apats opt_asig '->' {% parseErrorSDoc (combineLocs $1 | $5) $ text | "parse error in | lambda: no expression after '->'" | {- s/r:1 r/r:0 -} | | '\\' {% parseErrorSDoc | (getLoc $1) $ text | "parse error: | naked lambda expression '\'" | } | {- s/r:1 r/r:0 -} | | 'let' binds 'in' {% parseErrorSDoc | (combineLocs $1 $2) $ text | "parse error in | let binding: missing expression after 'in'" | } | {- s/r:0 r/r:11 -} | | 'let' binds {% parseErrorSDoc | (combineLocs $1 $2) $ text | "parse error | in let binding: missing required 'in'" | } | {- s/r:0 r/r:0 -} | | 'let' {% parseErrorSDoc | (getLoc $1) $ text | "parse error: | naked let binding" | } | {- s/r:1 r/r:0 -} | | 'if' exp optSemi 'then' exp optSemi 'else' {% hintIf | (combineLocs $1 $5) "else clause empty" } | {- s/r:2 r/r:0 -} | | 'if' exp optSemi 'then' exp optSemi {% hintIf | (combineLocs $1 $5) "missing required else clause" } | {- s/r:1 r/r:0 -} | | 'if' exp optSemi 'then' {% hintIf | (combineLocs $1 $2) "then clause empty" } | {- s/r:2 r/r:0 -} | | 'if' exp optSemi {% hintIf | (combineLocs $1 $2) "missing required then and else clauses" | {- s/r:2 r/r:0 -} | | 'if' {% hintIf (getLoc | $1) "naked if statement" } | {- s/r:0 r/r:0 -} | | 'case' exp 'of' {% parseErrorSDoc | (combineLocs $1 $2) $ text | "parse error | in case statement: missing list after '->'" | } | {- s/r:1 r/r:0 -} | | 'case' exp {% parseErrorSDoc | (combineLocs $1 $2) $ text | "parse error in | case statement: missing required 'of'" | } | {- s/r:1 r/r:0 -} | | 'case' {% parseErrorSDoc | (getLoc $1) $ text | "parse error: | naked case statement" | } | | Shift/reduces look harmless (like MultiWayIf ambiguity) as they seem | to resolve as shift correctly. | | -- | | Sergei
Hi, Am Montag, den 01.12.2014, 15:12 -0500 schrieb Richard Eisenberg:
In unrelated work, I saw this scroll across when happy'ing the parser:
shift/reduce conflicts: 60 reduce/reduce conflicts: 16
These numbers seem quite a bit higher than what I last remember (which is something like 48 and 1, not 60 and 16). Does anyone know why?
a side node: You can use the collected build logs at https://github.com/nomeata/ghc-speed-logs if you need to find out when something first changed. In this case, the increase from 47 to 60 was http://git.haskell.org/ghc.git/commit/bc2289e, as Gergo figured out already. I’ve now started tracking these two numbers on ghcspeed as well (but I did not import the old numbers retroactively): http://ghcspeed-nomeata.rhcloud.com/timeline/?exe=2&base=2%2B68&ben=reduce%2... http://ghcspeed-nomeata.rhcloud.com/timeline/?exe=2&base=2%2B68&ben=shift%2F... Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org
participants (7)
-
Dr. ERDI Gergo -
Iavor Diatchki -
Joachim Breitner -
Richard Eisenberg -
Sergei Trofimovich -
Simon Marlow -
Simon Peyton Jones