Re: Is possible to generate Lua Grammar in LL(1)?

[Fabio Mascarenhas <mascarenhas@...>]

Rafael,

The parser for Lua 4.0.1 is also recursive descent (it is very similar
Lua 5.1's parser, in fact, apart from the fact that they are
generating bytecodes for two very different VMs).

The parser itself gives a clue on how to reduce the grammar to LL(1):
you left factor and solve the conflict on the semantic action.

exprstat ::= primaryexp rest_exprstat
rest_exprstat ::= varlist_assign | assign | funcall
funcall ::= /* empty */
varlist_assign ::= ',' var {',' var} '=' explist
assign ::= '=' explist

Notice that this is more permissive than the actual grammar (see
Florian's comment about Lua not being LL(1)), in the assignment cases
you have to check that the lvalues are well-formed. The same for the
funcall case, you have to check that the last part of the expression
is a call. If your tool or method lets you add actions in the middle
of a production you can do it like the Lua parser does and add an
action just after 'primaryexp'. Not being LL(1) is no impediment to
writing a top-down parser that only needs one token of actual
lookahead if you are willing to use some dirty tricks. :-)

The least error-prone way to get a top-down parser for Lua is to
translate the actual Lua parser to whatever language you need and make
it do what you want instead of generating bytecode (as a bonus this
makes it easy to get error messages as good as the Lua parser's). Or
use ANTLR or one of the LR parser generators, they are much more
forgiving.

--
Fabio Mascarenhas


On Fri, Oct 14, 2011 at 10:13 AM, Rafael Bittencourt
<rafaelobitten@gmail.com> wrote:
> Fabio,
> This version(http://www.lua.org/source/4.0.1/src_lparser.c.html) use the
> non-recursive descent, right? So the
> grammar(http://www.lua.org/manual/4.0/manual.html#6.) is easy to reduce to
> LL(1). Currently on version 5.1 the grammar changed comparable to 4.0, i
> cant remove the  ambiguity between var and function call. Maybe i have doing
> somes mistakes in reduction, but i think the is not possible derive this
> grammar(5.1) to LL(1).
> Thank you in advance
> 2011/10/14 Fabio Mascarenhas <mascarenhas@acm.org>
>>
>> Rafael,
>>
>> This Lua grammar for ANTLR looks like it is most of the way there:
>> http://antlr.org/grammar/1178608849736/Lua.g, but it ignores operator
>> precedence. The parser in the Lua implementation
>> (http://www.lua.org/source/5.1/lparser.c.html) is mostly a
>> straightforward recursive descent parser, with expressions being the
>> tricky part (it uses precedence climbing, see
>> http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm and
>> http://compilers.iecc.com/comparch/article/92-05-140, or just read the
>> code :-) ).
>>
>> --
>> Fabio Mascarenhas
>>
>>
>> On Fri, Oct 14, 2011 at 6:26 AM, Rafael Bittencourt
>> <rafaelobitten@gmail.com> wrote:
>> > Hi,
>> > I am developing compiler for Lua Language and I implemented the
>> > algorithm of
>> >  Non recursive syntax analysis. But it need the language is in LL(1)
>> > form.
>> > So, i have tried reduce the Lua
>> > grammar(http://www.lua.org/manual/5.1/manual.html) for this form. But i
>> > didnt have sucess. I wanna know if is possible convert this grammar to
>> > LL(1), i saw the code of compiler in c and i read in any comment that
>> > use
>> > the LL(1) form.
>> > Greetings
>> > --
>> > Rafael de Oliveira Bittencourt
>> > ---------------------------------------------------------------------
>> > Bacharelando em Ciência da Computação -UFBA
>> > Estagiário Suporte-CPD/UFBa  (71) - 3283-6119
>> > GNU/Linux Registered User  #499863
>> >
>>
>
>
>
> --
> Rafael de Oliveira Bittencourt
> ---------------------------------------------------------------------
> Bacharelando em Ciência da Computação -UFBA
> Estagiário Suporte-CPD/UFBa  (71) - 3283-6119
> GNU/Linux Registered User  #499863
>