Created
December 10, 2023 21:59
-
-
Save jeffxchu/8542cbcf980fce763a297b0ae51385f1 to your computer and use it in GitHub Desktop.
lisp parser
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
fun parseLisp(input: String): Any? { | |
val tokens = tokenize(input).iterator() | |
return if (tokens.hasNext()) parse(tokens) else null | |
} | |
fun parse(tokens: Iterator<String>): Any? { | |
val token = tokens.next() | |
return when (token) { | |
"(" -> parseList(tokens) | |
")" -> null // This shouldn't happen if the input is well-formed | |
else -> token | |
} | |
} | |
fun parseList(tokens: Iterator<String>): List<Any?> { | |
val list = mutableListOf<Any?>() | |
while (tokens.hasNext()) { | |
val token = tokens.next() | |
if (token == ")") { | |
return list | |
} | |
list.add(if (token == "(") parseList(tokens) else token) | |
} | |
throw IllegalArgumentException("Unmatched parentheses") | |
} | |
fun tokenize(exp: String): List<String> = | |
exp.replace("(", "( ") // Prep for split | |
.replace(")", " )") | |
.split(" ") | |
.filter { it.isNotEmpty() } | |
fun main() { | |
val lispExp = "(first (list 1 (+ 2 3) 9))" | |
println("Input: $lispExp") | |
val ast = parseLisp(lispExp) | |
println("Output: $ast") | |
} |
Author
jeffxchu
commented
Dec 10, 2023
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment