lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]




On 17/07/16 12:45 PM, Dirk Laurie wrote:
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.

Or backtracking-hard, but Lua, like LPeg, doesn't do backtracking.

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.