Re: Interesting ambiguity in "The Complete Syntax of Lua"

[Dirk Laurie <dirk.laurie@...>]

2016-07-17 14:42 GMT+02:00 Paul Baker <paulbaker8@gmail.com>:
> I entered "The Complete Syntax of Lua" from the Reference Manual [1]
> into a context-free grammar tool, in order to investigate the
> well-known "function call x new statement" ambiguity.
>
> To my surprise, the tool found that the grammar was ambiguous even
> with the "stat ::= functioncall" production (and hence the above
> ambiguity) removed. With some help, I eventually found that the
> ambiguity occurs when a "varlist `=´ explist" statement follows an
> "exp". Specifically, "exp var" is ambiguous.
>
> An example of an ambiguous "exp var" is "f(g)(h)[i]". Using two
> consecutive "varlist `=´ explist" statements, we can have, say:
>
>> function f(g) return g end
>> function g(h) return h end
>> h = {}
>> i = 1
>> a = f(g)(h)[i] = 1
>
> According to the grammar in the reference manual, this last line could
> be parsed successfully as either "a = f(g); (h)[i] = 1" or "a = f;
> (g)(h)[i] = 1". I was interested to know which of these the
> semicolon-free line would be equivalent to, but it did not
> successfully parse at all. It seems that without a semicolon the
> entirety of "f(g)(h)[i]" is parsed as a single expression, leading to
> an error:
>
> stdin:1: unexpected symbol near '='
>
> [1] https://www.lua.org/manual/5.1/manual.html#8

Lua's parser is greedy. a = f(g)(h)[i] is legal, so it is not interested
in trying anything shorter.

The problem of finding a way to put semicolons into a Lua program
to make it compile may well be NP-hard.