How to write a CFG with functions?

Question

In an Assignment, I was asked to write a CFG for functions like:

def f(x, y): return x + y

def g(x, y): return x – y

def h(x, y, z): return x + y % z

def w(x, y, z): return x * y – z

and

def h1(x, y, z): return (x + y) % z

def h2(x, y, z): return x + y % z

I have tried to work it up as a normal CFG but, I could not do it for function definitions and function bodies. I am not pretty sure how to start with this kind of CFG's.

Answer 1

This is a bad question - you cannot generally encode the rule "only parameters are used in the function body" in a CFG. Ignoring that little problem, however, we can try:

S := def F (L): return E

F := CN
C := f | g | h | w
N := (empty string) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0

L := X | XY
X := x | y | z
Y := , L

E := X | E + E | E - E | E / E | E % E | E * E | (E)

S provides the overall structure of the function. F defines how function names are made. L defines how a list of variables is made. E defines how an expression involving variables and operators is made. Note that this would allow stuff like def f(x): return y, but you can't prevent that in a CFG.