起初最早听到lisp这个名字是一个偶尔的机会，留下了很牛的印象，工夫匆匆五年就过来了，前些日子看sicp,外面又再次提到了这个名字，从网上找了几个入门文档学习了一下根底语法，便又持续看起了sicp;从写下第一行（+ 1 2）代码,日子转瞬一个月就过来了,不得不说 lisp的前缀表达式的形式还是很不错的，不知怎得缓缓有了写一个lisp 解释器的想法，而后想到了之前王垠仿佛写过一篇文章《怎么写一个解释器》 如果你对如何写一个解释器感兴趣能够看下这篇文章，还是有所启发的。
回来了吗？哈哈哈
咱们持续旅途
写一个lisp解释器能够分三步:
1.将lisp表达式的字符串转换成一个树性构造的数组
2.解释这棵树
3.反对变量和办法调用
这里应用的语言是java
结构语法树
首先第一步：如何将lisp表达式的字符串转换成一个树性构造的数组？
咱们看一几个lisp表达式 剖析一下他的形成
(+ 1 2)(+ 1 2 (- 3 4))(+ 1 2 (- 3 4) 5)(+ 1 2 (- 3 4) 5 (+ 6 7 (+ 8 9)))(+ 1 2 (- 3 4) (+ 5 6 (+ 7 8)))(+ 1 2 (- 3 4) (+ 5 6 (+ 7 8)) 9)能够看到以上表达式外面能够分成两种元素：一个是不可分割的最小元素如 + - 1 2 3 这种 ，还有 （- 3 4）这种复合元素，而复合元素也是由最小的根底元素形成，于是咱们失去了第一个规定（复合元素能够被拆分成更小的根底元素和复合元素）。
以(+ 1 2 (- 3 4) 5 (+ 6 7 (+ 8 9)))这个表达式为例，它如果是一棵树长什么样子呢？上面让咱们画出它的状态：
咱们有了它的样子，但要如何将一个字符串模式的表达式转换成这样一棵树呢？ 这是咱们接下来要剖析的问题
duang duang duang duang...
让咱们回到咱们的第一个规定 这里还有什么暗藏信息呢？
1.复合元素可拆分
2.根底元素不可拆分
3.复合元素是被“（）”包裹的元素
有了这三项咱们就能够在进一步的思考了，树树树，树的元素是什么？
1.节点
2.叶子节点
头绪，头绪，有了头绪
节点对应的是复合元素，根底元素对应的是叶子节点，那如何辨别复合元素和根底元素呢？
“3.复合元素是被“（）”包裹的元素”，是它，是它，就是它。
复合节点里的第一个元素是“（”后的第一个元素，最初一个元素是“）”前的第一个元素，咱们又失去了第二个规定，有了下面两个规定咱们开始构建咱们的第一棵树:
代码：
node
class ExpNode implements Iterable<Object>{ List<Object> data = new ArrayList<>(); Node parent; public static ExpNode newInstance() { return new ExpNode(); } public void add(Object o) { if (o instanceof ExpNode) { ((ExpNode) o).parent = this; } super.add(o); } public Iterator<Object> iterator() { return data.iterator(); }}parse
public class Parse { public static ExpNode parseTree(String exp) { ExpNode root = ExpNode.newInstance(); buildNode(trimStr(exp), 0, root); return (ExpNode) root.iterator().next(); } private static void buildNode(String exp, int level, Cons node) { int lIndex = exp.indexOf("("); int rIndex = exp.indexOf(")"); if (rIndex > -1) { if (lIndex < rIndex && lIndex > -1) { String subExp = exp.substring(lIndex, rIndex + 1); if (isBaseLeaf(exp)) { ExpNode a = parseNode(subExp).orElseThrow(RuntimeException::new); node.add(a); } else { Optional<ExpNode> nodeOptional = parseNode(subExp); if (nodeOptional.isPresent()) { ExpNode val = nodeOptional.get(); node.add(val); node = val; } else { ExpNode objects = ExpNode.newInstance(); node.add(objects); node = objects; } } ++level; log.debug("{}{}---{}", createRepeatedStr(level), exp.substring(lIndex), subExp); buildNode(exp.substring(lIndex + 1), level, node); } else { //) b a (+ 8 9) => ) b a ( => b a if (lIndex > -1) { String subExp = trimStr(exp.substring(rIndex + 1, lIndex)); if (subExp.length() > 0 && !subExp.contains(")")) { String[] values = subExp.split(" "); for (String val : values) { node.parent().add(parseObj(val)); } } } else { // 所有都是后退// ) b a) => b a) => b a String subExp = exp.substring(rIndex + 1); int r2Index = 1 + subExp.indexOf(")"); if (r2Index > 1) { subExp = trimStr(subExp.substring(1, r2Index - 1)); if (subExp.length() > 0) { String[] values = subExp.split(" "); for (String val : values) { node.parent().add(parseObj(val)); } } } } --level; log.debug("{}{}", createRepeatedStr(level), exp.substring(rIndex)); buildNode(exp.substring(rIndex + 1), level, node.parent()); } } else { log.debug(createRepeatedStr(level)); } } private static Optional<ExpNode> parseNode(String exp) { String subExp = ""; if (isBaseLeaf(exp)) { //（xx [xx]） subExp = exp.substring(1, exp.length() - 1); } else { // （xx [xx] (xx xx xx） // (xx [xx] ( // (( subExp = exp.substring(1); subExp = subExp.substring(0, subExp.indexOf("(")); if (subExp.trim().isEmpty()) { return Optional.empty(); } } String[] keys = subExp.split(" "); ExpNode node = ExpNode.newInstance(); for (int i = 0; i < keys.length; i++) { node.add(parseObj(keys[i])); } return Optional.of(node); } private static Object parseObj(String val) { try { return Integer.valueOf(val); } catch (NumberFormatException e) { if (val.equals("true") || val.equals("false")) { return Boolean.valueOf(val); } else if (val.indexOf("'") == 0 && val.lastIndexOf("'") == val.length() - 1) { return val.replaceAll("\"", "\""); } else { return Var.of(val); } } } private static boolean isBaseLeaf(String exp) { return count(exp, "\\(") == 1 && count(exp, "\\)") == 1 && exp.matches("^\\(.+?\\)$"); } private static int count(String str, String regx) { Matcher matcher = Pattern.compile(regx).matcher(str); int i = 0; while (matcher.find()) { i++; } return i; } private static String trimStr(String str) { String tempStr = str.replace(" ", " ").trim(); return tempStr.contains(" ") ? trimStr(tempStr) : tempStr; } private static String createRepeatedStr(int n) { return String.join("", Collections.nCopies(n, "--")); }}当然还有更简略的形式 哈哈哈，将“（”替换成“[”,将“）”转换成“]”,让后用json 解析器解析即可，哈哈哈哈