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

[Florian Weimer <fw@...>]

* Rafael Bittencourt:

> 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.

Lua is not in LL(1).  Telling assignments from function calls requires
unbounded look-ahead.  You need some LL(1) extension, or you cannot
parse Lua.  (The ANTLR parser enables backtracking, but this is
certainly not required.)

Does your tool support direct left recursion and grammar attributes?
Then this transformation might work (from lua2-mode):

  ;; We need an arbitrary amount of look-ahead to decide whether this
  ;; is an assignment or a function call.
  ;;
  ;; The original grammar is:
  ;;
  ;; stat         ::= varlist "=" explist
  ;;                  functioncall
  ;; varlist      ::= var {"," var}
  ;; var          ::= Name 
  ;;                  prefixexp "[" exp "]"
  ;;                  prefixexp "." Name
  ;; prefixexp    ::= var
  ;;                  functioncall
  ;;                  "(" exp ")"
  ;; functioncall ::= prefixexp args
  ;;                  prefixexp ":" Name args
  ;; args         ::= "(" [explist] ")"
  ;;                  tableconstructor
  ;;                  String
  ;;
  ;; We transform this to (with var and args as above):
  ;;
  ;; stat         ::= var {"," var} "=" explist
  ;;                  prefixexp args
  ;;                  prefixexp ":" Name args
  ;; prefixexp    ::= Name 
  ;;                  prefixexp "[" exp "]"
  ;;                  prefixexp "." Name
  ;;                  prefixexp args
  ;;                  prefixexp ":" Name args
  ;;                  "(" exp ")"
  ;;
  ;; We use in-var and comma-seen to disambiguate between var and and
  ;; prefixexp.