Could you kindly explain to me what would be best if for example the root symbol is Formula, and a Formula can either be A | B. Is that possible first of all please ?

def Program : Parser[Program] = positioned(Formula) ^^ {result => result}

def Formula : Parser[Formula] = positioned( "A" ~ aStatement ^^ {case "A" ~ result => new Formula(result.asInstanceOf[Either[A,B]])} |
"B" ~ bStatement ^^ {case "B" ~ result => new Formula(result.asInstanceOf[Either[A,B]])})

And what should I write in the parseAll function please ?

You can have recursion in a parser without those functions, when non terminal symbols refer to themselves or to other non terminals that refer back to them. To help you find the cause of the stack overflow, we’d really need your whole grammar.