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: enter image description here

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

  • $\begingroup$ how does this grammar allow recursive functions? $\endgroup$
    – gust
    Apr 19 at 3:31
  • $\begingroup$ @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). $\endgroup$
    – qz-
    Apr 19 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.