1

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!

1
  • try to write the parser so that it returns two values: the parsed form and the list of remaining tokens to parse (spoiler: see also stackoverflow.com/q/50562146/124319) Commented Feb 18, 2021 at 8:42

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.