I'm trying to write a very rudimentary lisp parser in TypeScript that turns a string (in this case the, the lisp code) into an syntax tree (nested arrays representing the parsed s-expressions) while avoiding any mutation.
Here's my progress so far:
// The lisp code used as input.
const input = "(+ 1 1 (+ 2 2) (+ 1 1))"
// My tokenizer, which does the job fine.
function tokenizer(input: string): string[ {
return input
.replace(/\(/g, " ( ")
.replace(/\)/g, " ) ")
.trim()
.split(/\s+/)
}
// The parser, which doesn't work as expected.
function parser(tokens: string[], list: any[] = []): any[] {
if (tokens.length == 0)
return list
const [head, ...tail] = tokens
if (head === "(")
return [...list, parser(tail)]
if (head === ")")
return list
return parser(tail, [...list, head])
}
What I can't figure out is how to continue the parsing of the remaining tokens after the first parens gets closed.
For instance, the parser currently return [ "+", "1", "1", [ "+", "2", "2" ] ].
I've tried recursing again through the remaining tokens on close, but that nests any further expressions inside the preceding one:
function parser(tokens: string[], list: any[] = []): any[] {
if (tokens.length == 0)
return list
const [head, ...tail] = tokens
if (head === "(")
return [...list, parser(tail)]
if (head === ")")
return parser(tail, list)
return parser(tail, [...list, head])
}
Returns [ "+", "1", "1", [ "+", "2", "2", [ "+", "1", "1" ] ] ]
Any help at solving this would be very appreciated. Cheers!