Hi All, I'm trying to parse Python 3.0 following the Python 3.0 grammar from: http://svn.python.org/projects/python/branches/py3k/Grammar/Grammar Now, when getting to the arglist, it seems that the grammar is ambiguous, and I was wondering how does Python disambiguate that (I'll not put the whole grammar here, just the part that appears to be ambiguous): arglist: (argument ',')* (argument [','] |'*' test (',' argument)* [',' '**' test] |'**' test ) argument: test [comp_for] test: or_test or_test: and_test and_test: not_test not_test: 'not' not_test | comparison comparison: star_expr star_expr: ['*'] expr So, with that construct, having call(arglist) in a format: call(*test), the grammar would find it to be consumed in the argument construction (because of the start_expr) and not in the arglist in the '*' test (because the construct is ambiguous and the argument construct comes first), so, I was wondering how does Python disambiguate that... anyone has any pointers on it? It appears that happened while adding PEP 3132. Am I missing something here? Thanks, Fabio
Fabio Zadrozny wrote:
I was wondering how does Python disambiguate that... anyone has any pointers on it?
That is easy to answer: py> parser.expr("f(*x)").totuple() (258, (326, (303, (304, (305, (306, (307, (309, (310, (311, (312, (313, (314, (315, (316, (317, (1, 'f')), (321, (7, '('), (329, (16, '*'), (303, (304, (305, (306, (307, (309, (310, (311, (312, (313, (314, (315, (316, (317, (1, 'x')))))))))))))))), (8, ')')))))))))))))))), (4, ''), (0, '')) py> symbol.arglist 329 So much for the "how", I don't know why it makes this choice; notice that this is the better choice, though: py> f((*x)) File "<stdin>", line 1 SyntaxError: can use starred expression only as assignment target Regards, Martin
I was wondering how does Python disambiguate that... anyone has any pointers on it?
That is easy to answer:
py> parser.expr("f(*x)").totuple() (258, (326, (303, (304, (305, (306, (307, (309, (310, (311, (312, (313, (314, (315, (316, (317, (1, 'f')), (321, (7, '('), (329, (16, '*'), (303, (304, (305, (306, (307, (309, (310, (311, (312, (313, (314, (315, (316, (317, (1, 'x')))))))))))))))), (8, ')')))))))))))))))), (4, ''), (0, '')) py> symbol.arglist 329
So much for the "how", I don't know why it makes this choice; notice that this is the better choice, though:
py> f((*x)) File "<stdin>", line 1 SyntaxError: can use starred expression only as assignment target
Yeap, very strange that it works... I can't get it to work in JavaCC. I'm considering setting arglist as ((argument() [','])+ ['**' test]) | '**' test Because it is able to handle the constructs removing the ambiguity, and make things right semantically later on, but I don't like the idea of being so different from the official grammar (although I'm running out of choices). Thanks, Fabio
Fabio Zadrozny wrote:
Because it is able to handle the constructs removing the ambiguity, and make things right semantically later on, but I don't like the idea of being so different from the official grammar (although I'm running out of choices).
I'm not sure it is the same (or at least related) problem, but a parsing ambiguity was also reported for the lambda varargslist in 2.x: http://bugs.python.org/issue2009 I think I'd be happier with fiddling the Grammar to eliminate these problems if Guido was to chime in as the author of pgen though... (since pgen appears to be able to make sense of the grammar as it currently stands, while other parsers sometimes have trouble) Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia ---------------------------------------------------------------
On Sun, Mar 8, 2009 at 2:18 PM, Nick Coghlan <ncoghlan@gmail.com> wrote:
Fabio Zadrozny wrote:
Because it is able to handle the constructs removing the ambiguity, and make things right semantically later on, but I don't like the idea of being so different from the official grammar (although I'm running out of choices).
I'm not sure it is the same (or at least related) problem, but a parsing ambiguity was also reported for the lambda varargslist in 2.x: http://bugs.python.org/issue2009
I think I'd be happier with fiddling the Grammar to eliminate these problems if Guido was to chime in as the author of pgen though... (since pgen appears to be able to make sense of the grammar as it currently stands, while other parsers sometimes have trouble)
To be honest I wasn't aware of this ambiguity. It seems that whoever wrote the patch for argument unpacking (a, b, *c = ...) got "lucky" with an ambiguous grammar. This surprises me, because IIRC usually pgen doesn't like ambiguities. Other parser generators usually have some way to deal with ambiguous grammars, but they also usually have features that make it unnecessary to use the exact same grammar as pgen -- for example, most parser generators are able to backtrack or look ahead more than one token, so that they can distinguish between "a = b" and "a" once the '=' token is seen, rather than having to commit to parse an expression first. -- --Guido van Rossum (home page: http://www.python.org/~guido/)
To be honest I wasn't aware of this ambiguity. It seems that whoever wrote the patch for argument unpacking (a, b, *c = ...) got "lucky" with an ambiguous grammar. This surprises me, because IIRC usually pgen doesn't like ambiguities.
So how does it resolve the ambiguity? Regards, Martin
On Sun, Mar 8, 2009 at 3:28 PM, "Martin v. Löwis" <martin@v.loewis.de> wrote:
To be honest I wasn't aware of this ambiguity. It seems that whoever wrote the patch for argument unpacking (a, b, *c = ...) got "lucky" with an ambiguous grammar. This surprises me, because IIRC usually pgen doesn't like ambiguities.
So how does it resolve the ambiguity?
I have no idea. :-( -- --Guido van Rossum (home page: http://www.python.org/~guido/)
To be honest I wasn't aware of this ambiguity. It seems that whoever wrote the patch for argument unpacking (a, b, *c = ...) got "lucky" with an ambiguous grammar. This surprises me, because IIRC usually pgen doesn't like ambiguities. Other parser generators usually have some way to deal with ambiguous grammars, but they also usually have features that make it unnecessary to use the exact same grammar as pgen -- for example, most parser generators are able to backtrack or look ahead more than one token, so that they can distinguish between "a = b" and "a" once the '=' token is seen, rather than having to commit to parse an expression first.
JavaCC can actually do that, but in the current construct, the ambiguity is not dependent on a lookahead, because both '*' test and star_expr will match it equally well -- because they're actually the same thing grammar-wise (so, there's no way to disambiguate without a semantic handling later on) After taking a 2nd look, I think that probably the best solution would be creating a new testlist to be used from the expr_stmt -- something like testlist_start_expr. E.g.: testlist: test (',' test)* [','] testlist_star_expr: [test | star_expr] (',' [test | star_expr])* [','] And also, star_expr could probably be just '*' NAME (to make it faster to match -- or could it match something else?) Note that I still haven't tested this -- I'll have time to do it tomorrow on my JavaCC grammar (so, I can give you a better feedback if this actually works). Regards, Fabio
To be honest I wasn't aware of this ambiguity. It seems that whoever wrote the patch for argument unpacking (a, b, *c = ...) got "lucky" with an ambiguous grammar. This surprises me, because IIRC usually pgen doesn't like ambiguities. Other parser generators usually have some way to deal with ambiguous grammars, but they also usually have features that make it unnecessary to use the exact same grammar as pgen -- for example, most parser generators are able to backtrack or look ahead more than one token, so that they can distinguish between "a = b" and "a" once the '=' token is seen, rather than having to commit to parse an expression first.
JavaCC can actually do that, but in the current construct, the ambiguity is not dependent on a lookahead, because both '*' test and star_expr will match it equally well -- because they're actually the same thing grammar-wise (so, there's no way to disambiguate without a semantic handling later on)
After taking a 2nd look, I think that probably the best solution would be creating a new testlist to be used from the expr_stmt -- something like testlist_start_expr.
E.g.:
testlist: test (',' test)* [','] testlist_star_expr: [test | star_expr] (',' [test | star_expr])* [',']
And also, star_expr could probably be just '*' NAME (to make it faster to match -- or could it match something else?)
Note that I still haven't tested this -- I'll have time to do it tomorrow on my JavaCC grammar (so, I can give you a better feedback if this actually works).
Ok, I've created a bug for that at: http://bugs.python.org/issue5460 and commented on a solution (and just to note, star_expr could match b, *a.a = [1,2,3], so, it cannot be changed for NAME) The solution is working for me, and it should be straightforward to apply it to Python. Regards, Fabio
participants (4)
-
"Martin v. Löwis" -
Fabio Zadrozny -
Guido van Rossum -
Nick Coghlan