# BNF syntax for a recursive function?

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.

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

• how does this grammar allow recursive functions?
– gust
Apr 19 at 3:31
• @gust I've edited my answer to make the grammar more clear. Consider a recursive function such as f(x) = f(x). This is allowed by the grammar as id '(' parameter ')' '=' matches f(x) = and the function body can be an expression such as a call to f(x).
– qz-
Apr 19 at 6:42