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

7次阅读

共计 3998 个字符，预计需要花费 10 分钟才能阅读完成。

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

正文完