LL(1) conflict resolution for parameters

"Pat Terry" <CSPT@giraffe.ru.ac.za>
17 Dec 1995 00:43:04 -0500

          From comp.compilers

Related articles
LL(1) conflict resolution for parameters CSPT@giraffe.ru.ac.za (Pat Terry) (1995-12-17)
Re: LL(1) conflict resolution for parameters jjan@cs.rug.nl (1995-12-19)
| List of all articles for this month |

From: "Pat Terry" <CSPT@giraffe.ru.ac.za>
Newsgroups: comp.compilers
Date: 17 Dec 1995 00:43:04 -0500
Organization: Rhodes University
Keywords: LL(1)

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
          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 *)

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]


Post a followup to this message

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