BNF syntax for a recursive function?

Question

I'm to write a syntax that will allow for a recursive function, i.e.

f(x) = if x == 0 then x else f(x+1)

Here's one attempt at creating the grammar:

But I don't think this is right since there's no such thing as parameterized syntax.

Answer 1

Are you aiming to simply allow recursive functions or specify only recursive functions. The following grammar allows recursive functions:

function      := id '(' parameter ')' '=' function_body ;
function_body := conditional
               | expression
               ;
expression    := function_call
               | <other expression types>
               ;
function_call := id '(' parameter ')' ;

Specifying only recursive functions would require a context-aware grammar (BNF is context-free). You can approach the problem outside of the grammar specification though and check for recursive functions later in your parser / compiler pipeline.

Checking for recursion outside of the grammar allows you to more easily identify cyclic recursion (not just f calling f but something like f -> a -> b -> c -> f).