关于lisp:用java写一个lisp-解释器

起初最早听到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 解析器解析即可，哈哈哈哈

解释器