I have encounter a problem with parsers having two branches of recursion. To demonstrate the problem easier, I use a simple grammar of a lambda calculus from the article written by Luca Bolognese as the example:
<expression> ::= <name> | <function> | <application> <name> ::= nonblank character sequence <function> ::= \ <name> . <body> <body> ::= <expression> <application> ::= ( <function expression> <argument expression> ) <function expression> ::= <expression> <argument expression> ::= <expression>
The parser in the article is quite concise:
let ws = " \t\n"
let specialChars = ".)(\\\n"
let pWs = spaces
let pName = manyChars (noneOf (ws + specialChars)) |>> EName
let pExpr, pExprRef = createParserForwardedToRef<Expression, Unit>()
let curry2 f a b = f(a,b)
let pFunction = pchar '\\' >>. pipe2 pName (pchar '.' >>. pExpr) (curry2 Function)
let pApplication = pchar '(' >>. pipe2 pExpr (pWs >>. pExpr) (curry2 Application)
.>> pWs .>> pchar ')'
do pExprRef := pFunction <|> pApplication <|> pName
let pExpressions = sepBy pExpr spaces1
let fparseString text =
match run pExpressions text with
| Success(result, _, _) -> result
| Failure(errorMsg, _, _) -> failwith (sprintf "Failure: %s" errorMsg)
I'm interested in pApplication
since they consist of two pExpr
s which in turn could be pApplication
s too. The parser runs out of stack space in the following benchmark:
let generateString level =
let rec loop i =
seq {
if i < level then
yield "("
yield! loop level
yield " "
yield! loop (i+1)
yield ")"
else
yield "(x x)"
}
loop 0 |> String.concat ""
let N = 5000
let s = generateString N;;
let _ = fparseString s;;
How can I rewrite the parser to be tail-recursive?
I recognized the problem when trying to write a parser for a Lisp-like language and test it with real benchmarks. I have Term
and VarBinding
which are mutually recursive types and a let
parser which exhibits the same issue as pApplication
above. My parser is on github in case the analysis is wrong regarding the not tail-recursive problem.