The trouble with ambiguous grammars
On Oct 17, 2008, at 12:25 PM, Waldemar Horwat wrote:
Here's a clearer case that Firefox gets wrong (or your grammar gets
wrong, depending on your point of view):function f() {return "f"} var x = 3; let (a = 1) a ? f : x++();
The grammar states that the last statement must evaluate to "f".
Firefox gives a syntax error. This is incorrect because the let
expression up to the ++ is a PrimaryExpression so can be used as the
left operand of a function call.
Consider the simpler, let-expression-free test:
js> var a = 1, f = 2;
js> a ? f : x++();
typein:3: SyntaxError: missing ; before statement: typein:3: a ? f : x++(); typein:3: .........^
(The error pointer is off by two, I'm filing a bug on that.)
Safari and IE seem to agree (IE blames the correct column number, the
one for the ( -- good for it).
This is an error according to ES1-3 because x++ is a postfixExpression
derived from
PostfixExpression : LeftHandSideExpression LeftHandSideExpression [no LineTerminator here] ++ LeftHandSideExpression [no LineTerminator here] --
while expr() meaning "call expr with zero arguments" derives from
CallExpression : MemberExpression Arguments
and MemberExpression is never an unparenthesized PostfixExpression:
MemberExpression : PrimaryExpression FunctionExpression MemberExpression [ Expression ] MemberExpression . Identifier new MemberExpression Arguments
So your example with or without the leading let (a = 1) is not
syntactically valid.
In an ambiguous grammar, you also need to prove the negative: no
other expansion can match that source program and shadow your
expansions. Proving the negative causes trouble because a language
extension could turn the mismatch into a match and because
sometimes, as in the above case, you expected some other part of the
grammar to shadow your expansions but it didn't.
That's a good point, but it is not what is going on here. There is no
valid sentence x++() produced by ES1-3's expression grammar.
On Oct 17, 2008, at 3:39 PM, Brendan Eich wrote:
On Oct 17, 2008, at 12:25 PM, Waldemar Horwat wrote:
Here's a clearer case that Firefox gets wrong (or your grammar gets wrong, depending on your point of view):
function f() {return "f"} var x = 3; let (a = 1) a ? f : x++();
The grammar states that the last statement must evaluate to "f". Firefox gives a syntax error. This is incorrect because the let expression up to the ++ is a PrimaryExpression so can be used as the left operand of a function call.
Er, you are right, I should have acknowedged this point. The rest of
my post is about x++() not being a valid sentence, which supports your
argument.
While we don't have any usability problems, and torturous statements
such as
let (a = 1) a ? f : x++();
are not written by real users (they'd parenthesize to clear up
things), I agree that we don't want the "prove a negative" problem.
On Oct 17, 2008, at 3:47 PM, Brendan Eich wrote:
On Oct 17, 2008, at 3:39 PM, Brendan Eich wrote:
On Oct 17, 2008, at 12:25 PM, Waldemar Horwat wrote:
... let (a = 1) a ? f : x++();
The grammar states that the last statement must evaluate to "f". Firefox gives a syntax error. This is incorrect because the let expression up to the ++ is a PrimaryExpression so can be used as the left operand of a function call.
Er, you are right, I should have acknowedged this point. The rest of my post is about x++() not being a valid sentence, which supports your argument.
While we don't have any usability problems, and torturous statements such as
let (a = 1) a ? f : x++();
are not written by real users (they'd parenthesize to clear up things), I agree that we don't want the "prove a negative" problem.
This shows a problem with ES4's reliance on top-down parser
construction. We never created an LR(1) grammar (ignoring ASI and the
other exceptions that don't fit in LR-anything, and solving dangling
else as is customary). To avoid the "prove a negative" problem, we
need one. IIRC you have one -- can you share it via ecmascript.org?
Brendan Eich wrote:
On Oct 17, 2008, at 3:47 PM, Brendan Eich wrote:
On Oct 17, 2008, at 3:39 PM, Brendan Eich wrote:
Er, you are right, I should have acknowedged this point. The rest of my post is about x++() not being a valid sentence, which supports your argument.
While we don't have any usability problems, and torturous statements such as
let (a = 1) a ? f : x++();
are not written by real users (they'd parenthesize to clear up things), I agree that we don't want the "prove a negative" problem.
It can rear up accidentally with semicolon insertion. Split the example across two lines:
let (a = 1) a ? f : x++ (...)
This shows a problem with ES4's reliance on top-down parser construction. We never created an LR(1) grammar (ignoring ASI and the other exceptions that don't fit in LR-anything, and solving dangling else as is customary). To avoid the "prove a negative" problem, we need one. IIRC you have one -- can you share it via ecmascript.org?
The old ES4 grammar is machine-verified LR(1). It's on:
www.mozilla.org/js/language/old-es4
WaldemarOn Oct 17, 2008, at 4:16 PM, Waldemar Horwat wrote:
The old ES4 grammar is machine-verified LR(1). It's on:
One based on ES3 would be helpful for ES3.1 and Harmony. Someone needs
to invest effort here. If not you, who? This is as good a time as any
to call for capable potential volunteers to scope the work and, if
they are willing, and step forward.
Brendan Eich wrote:
On Oct 17, 2008, at 4:16 PM, Waldemar Horwat wrote:
The old ES4 grammar is machine-verified LR(1). It's on:
One based on ES3 would be helpful for ES3.1 and Harmony. Someone needs to invest effort here. If not you, who? This is as good a time as any to call for capable potential volunteers to scope the work and, if they are willing, and step forward.
I'll do it for both. For Harmony it's not clear what's in and out at this point, so I'm somewhat at a loss as to what to put in there.
WaldemarOn Oct 20, 2008, at 11:35 AM, Waldemar Horwat wrote:
Brendan Eich wrote:
On Oct 17, 2008, at 4:16 PM, Waldemar Horwat wrote:
The old ES4 grammar is machine-verified LR(1). It's on:
www.mozilla.org/js/language/old-es4 One based on ES3 would be helpful for ES3.1 and Harmony. Someone
needs to invest effort here. If not you, who? This is as good a
time as any to call for capable potential volunteers to scope the
work and, if they are willing, and step forward.I'll do it for both. For Harmony it's not clear what's in and out
at this point, so I'm somewhat at a loss as to what to put in there.
Testing ideas from strawman:strawman
pages and (other than let expressions, which are already found
wanting) validating or invalidating them would be most helpful. Thanks,
On Oct 20, 2008, at 11:44 AM, Brendan Eich wrote:
On Oct 20, 2008, at 11:35 AM, Waldemar Horwat wrote:
Brendan Eich wrote:
On Oct 17, 2008, at 4:16 PM, Waldemar Horwat wrote:
The old ES4 grammar is machine-verified LR(1). It's on:
www.mozilla.org/js/language/old-es4 One based on ES3 would be helpful for ES3.1 and Harmony. Someone needs to invest effort here. If not you, who? This is as good a time as any to call for capable potential volunteers to scope the work and, if they are willing, and step forward.
I'll do it for both. For Harmony it's not clear what's in and out at this point, so I'm somewhat at a loss as to what to put in there.
Testing ideas from strawman:strawman pages and (other than let expressions,
Or (in the case of strawman:lambdas) lambda with expression body syntax, as opposed to block body syntax.
Here's a clearer case that Firefox gets wrong (or your grammar gets wrong, depending on your point of view):
function f() {return "f"} var x = 3; let (a = 1) a ? f : x++();
The grammar states that the last statement must evaluate to "f". Firefox gives a syntax error. This is incorrect because the let expression up to the ++ is a PrimaryExpression so can be used as the left operand of a function call.
This is why ambiguous grammars are bad and unsuitable for our spec. In an unambiguous grammar, if you find a series of production expansions that matches a source program, then you know that those are the expansions that will be taken. In an ambiguous grammar, you also need to prove the negative: no other expansion can match that source program and shadow your expansions. Proving the negative causes trouble because a language extension could turn the mismatch into a match and because sometimes, as in the above case, you expected some other part of the grammar to shadow your expansions but it didn't.
Here's a clearer case that Firefox gets wrong (or your grammar gets wrong, depending on your point of view): function f() {return "f"} var x = 3; let (a = 1) a ? f : x++(); The grammar states that the last statement must evaluate to "f". Firefox gives a syntax error. This is incorrect because the let expression up to the ++ is a PrimaryExpression so can be used as the left operand of a function call. This is why ambiguous grammars are bad and unsuitable for our spec. In an unambiguous grammar, if you find a series of production expansions that matches a source program, then you know that those are the expansions that will be taken. In an ambiguous grammar, you also need to prove the negative: no *other* expansion can match that source program and shadow your expansions. Proving the negative causes trouble because a language extension could turn the mismatch into a match and because sometimes, as in the above case, you expected some other part of the grammar to shadow your expansions but it didn't. Waldemar