classification
Title: Grammar change to prevent shift/reduce problem with varargslist
Type: enhancement Stage: resolved
Components: Interpreter Core Versions: Python 3.2
process
Status: closed Resolution: accepted
Dependencies: Superseder:
Assigned To: Nosy List: dalke, mark.dickinson, ncoghlan, nnorwitz
Priority: normal Keywords: patch

Created on 2008-02-05 00:19 by dalke, last changed 2010-07-12 14:15 by mark.dickinson. This issue is now closed.

Files
File name Uploaded Description Edit
refactor_varargslist.patch mark.dickinson, 2010-07-09 09:45
Messages (11)
msg62055 - (view) Author: Andrew Dalke (dalke) * (Python committer) Date: 2008-02-05 00:19
I wrote a translator from the CFG used in the Grammar file into a form for PLY.  I 
found one problem with

varargslist: ((fpdef ['=' test] ',')*
              ('*' NAME [',' '**' NAME] | '**' NAME) |
              fpdef ['=' test] (',' fpdef ['=' test])* [','])

This grammar definition is ambiguous until the presence/lack of a "*".  PLY 
complains:

state 469

    (28) varargslist -> fpdef EQUAL test COMMA .
    (32) varargslist_star -> fpdef EQUAL test COMMA .
    (35) varargslist_star3 -> COMMA . fpdef
    (36) varargslist_star3 -> COMMA . fpdef EQUAL test
    (39) fpdef -> . NAME
    (40) fpdef -> . LPAR fplist RPAR

  ! shift/reduce conflict for NAME resolved as shift.
  ! shift/reduce conflict for LPAR resolved as shift.

    RPAR            reduce using rule 28 (varargslist -> fpdef EQUAL test COMMA .)
    COLON           reduce using rule 28 (varargslist -> fpdef EQUAL test COMMA .)
    STAR            reduce using rule 32 (varargslist_star -> fpdef EQUAL test 
COMMA .)
    DOUBLESTAR      reduce using rule 32 (varargslist_star -> fpdef EQUAL test 
COMMA .)
    NAME            shift and go to state 165
    LPAR            shift and go to state 163

  ! NAME            [ reduce using rule 32 (varargslist_star -> fpdef EQUAL test 
COMMA 
.) ]
  ! LPAR            [ reduce using rule 32 (varargslist_star -> fpdef EQUAL test 
COMMA 
.) ]

    fpdef                          shift and go to state 515



My fix was to use this definition when I did the translation.

varargslist: ((fpdef ['=' test] (',' fpdef ['=' test])* 
                   (',' '*' NAME [',' '**' NAME] | ',' '**' NAME | [','])) |
              ('*' NAME [',' '**' NAME]) |
              ('**' NAME))


So far I've not found a functional difference between these two definitions, and 
the only change to ast.c is to update the comment based on this section.

By making this change it would be easier for the handful of people who write 
parsers for Python based on a yacc-like look-ahead(1) parser to use that file more 
directly.
msg62065 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2008-02-05 11:31
I don't have any objection in principle, but I would like to see the
updated rules based on the 2.6 and 3.0 Grammar files (they should only
be minor variants of what you have already done for 2.5)
msg62066 - (view) Author: Andrew Dalke (dalke) * (Python committer) Date: 2008-02-05 11:47
I've been working from the Grammar file from CVS for 2.6 ... I thought.  
For example, I see "# except_clause: 'except' [test [('as' | ',') 
test]]" which is a 2.6-ism.

"svn log" says it hasn't changed since 2007-05-19, when except/as was 
added.

What did I miss?
msg62071 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2008-02-05 12:11
Sorry, I misread slightly (or else just got confused as to which of the
3 Grammar files I was looking at on my local machine). What you've
posted already is indeed the relevant change for 2.6 - it's only 3.0
that is slightly different because it allows the definition of
keyword-only arguments (I believe that feature may also be on the list
of items that may be backported to 2.6).
msg109699 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-07-09 09:28
+!. I had to do a very similar refactoring recently when trying to fix the parser module to understand keyword-only arguments and annotations.

Taking keyword-only arguments into account, I think the replacement needs to be:

varargslist: (vfpdef ['=' test] (',' vfpdef ['=' test])* [',' 
   ['*' [vfpdef] (',' vfpdef ['=' test])* [',' '**' vfpdef] | '**' vfpdef]]
 |  '*' [vfpdef] (',' vfpdef ['=' test])* [',' '**' vfpdef] | '**' vfpdef)

and the analogous replacement needs to be made in the production for 'typedargslist', too.

BTW, I'm a bit surprised that the grammar doesn't allow for trailing commas after keyword-only arguments:  that is,

def f(a, b,): ...     is fine, but
def f(*, a, b,): ...  is a SyntaxError
msg109701 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-07-09 09:45
Here's a patch.

I'm assuming that this doesn't violate the moratorium, since it's not so much a change to the grammar itself as a modification to the way that it's expressed.
msg109705 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2010-07-09 10:09
> BTW, I'm a bit surprised that the grammar doesn't allow for trailing commas after keyword-only arguments:  that is,
>
> def f(a, b,): ...     is fine, but
> def f(*, a, b,): ...  is a SyntaxError

That seems more like an oversight than a deliberate restriction. Does
your patch eliminate the discrepancy?

(And agreed the moratorium doesn't apply).
msg109706 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-07-09 10:20
No,  "def f(*, a,): ..." is still a SyntaxError with the patch.  I'd think that allowing that extra comma *would* be a violation of the moratorium, though maybe it's debatable.  Perhaps worth bringing up on python-dev?
msg109707 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2010-07-09 10:28
> No,  "def f(*, a,): ..." is still a SyntaxError with the patch.  I'd think that allowing that extra comma *would* be a violation of the moratorium, though maybe it's debatable.  Perhaps worth bringing up on python-dev?

Good point - I just wouldn't worry about it in that case.
msg109800 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-07-09 21:47
> Good point - I just wouldn't worry about it in that case.

Ah, now I have to apologise:  after some discussion on #python-dev IRC, I'm afraid I've (perhaps foolishly) rejected this advice. :)  See python-dev discussion starting at 

http://mail.python.org/pipermail/python-dev/2010-July/101636.html

I'll hold off on the modification in this issue until that discussion resolves.
msg110088 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-07-12 14:15
Applied in r82837.  I'll open a separate issue for the trailing commas.
History
Date User Action Args
2010-07-12 14:15:52mark.dickinsonsetstatus: open -> closed
resolution: accepted
messages: + msg110088

stage: patch review -> resolved
2010-07-09 21:47:36mark.dickinsonsetmessages: + msg109800
2010-07-09 10:28:01ncoghlansetmessages: + msg109707
2010-07-09 10:20:16mark.dickinsonsetmessages: + msg109706
2010-07-09 10:09:34ncoghlansetmessages: + msg109705
2010-07-09 09:45:40mark.dickinsonsetfiles: + refactor_varargslist.patch
keywords: + patch
messages: + msg109701

stage: patch review
2010-07-09 09:28:04mark.dickinsonsetnosy: + mark.dickinson
messages: + msg109699
2010-07-09 05:26:38terry.reedysetversions: + Python 3.2, - Python 2.6, Python 3.0
2008-02-05 12:11:45ncoghlansetmessages: + msg62071
2008-02-05 11:47:56dalkesetmessages: + msg62066
2008-02-05 11:31:18ncoghlansetmessages: + msg62065
2008-02-05 01:34:37christian.heimessetpriority: normal
nosy: + nnorwitz, ncoghlan
components: + Interpreter Core, - None
versions: + Python 2.6, Python 3.0
2008-02-05 00:19:49dalkecreate