LL(1) conflict resolution for parameters

I feel sure this must be a fairly well known problem, with a clean solution,
but I am not sure that I have found the best one.


Problem: Write a recursive descent compiler that can handle parameters passed
by value or reference. Here's a toy grammar that catches the idea


      Program = { Procedure } .
      Procedure = Header Locals Body .
      Header = ProcIdent "(" Parameter { "," Parameter } ")" .
      Parameter = ( "REF" | "VAL" ) VarIdent (* quite explicit *).
      Locals = "VAR" VarIdent { "," VarIdent } .
      Body = "BEGIN" ProcCall { ";" ProcCall } "END" .
      ProcCall = ProcIdent "(" Argument { "," Argument } ")" .
      Argument = Reference | Value .
      Reference = VarIdent (* generate code to pass address of variable *) .
      Value = Expression (* generate code to pass value of expression *) .
      Expression = Term { ("+" | "-") Term } .
      Term = Factor { ("*" | "/") Factor } .
      Factor = VarIdent | number | "(" Expression ")" .
      VarIdent = identifier .
      ProcIdent = identifier .


The above is not LL(1), because the alternatives for Argument both have
identifier in their FIRST sets.


We want strict checking, of course. So consider


      SillyProc (VAL a, REF b, VAL c)
      VAR x, y, z
      BEGIN
          SillyProc(x, y, 4); (* this one is fine *)
          SillyProc(2, 3, 4); (* 3 in this one is semantically wrong *)
          SillyProc(x, b+c, x+y/z) (* b+c in this one is semantically wrong *)
      END


No problem with a hand crafted recursive descent parser, of course,
assuming "declare before use" restraints. Each time the Argument
procedure is called, one can pass it a parameter telling it which
alternative to follow, derived from the (known) attributes of the
relevant ProcIdent symbol table entry.


Catch: But we want to use a parser generator that requires an LL(1)
grammar. No problem with fixing the grammar, of course. Simply
change the production for Argument:


      Argument = Expression .


If you do this, what is the best way of transmitting the information
to Expression so that the correct code can be generated, and so that
the correct tests can be made to check the constraints?


Any suggestions will be welcomed. I can post a summary to comp.compilers
in due course.


Thanks in advance.


Pat Terry, Computer Science, Rhodes University, GRAHAMSTOWN 6140, RSA
cspt@cs.ru.ac.za or cspt@giraffe.ru.ac.za or pdterry@psg.com
Voice +27-461-318291 or +27-461-318292 FAX +27-461-25049
[This grammar is ambiguous -- foo(x) looks the same whether x is to be passed
by value or by reference. Back when I was writing Fortran compilers, I just
parsed up arguments into expression trees, then looked at the tree and in the
special case that the tree was just an identifier, treated it as a reference
argument. -John]


--

Return to the comp.compilers page.
Search the comp.compilers archives again.