递归下降法二叉树解析

﹏ヽ暗。殇╰゛Y 2023-07-06 13:05 55阅读 0赞

参考: [https://www.cnblogs.com/Ninputer/archive/2011/06/21/2085527.html][https_www.cnblogs.com_Ninputer_archive_2011_06_21_2085527.html]

编写递归下降语法分析器的一般步骤：

1.  使用一个索引来记录当前扫描的位置。通常将它做成一个整数字段。
2.  为每个非终结符编写一个方法。
3.  如果一个非终结符有超过一个的产生式，则在这个方法中对采用哪个产生式进行**分支预测**。
4.  处理单一产生式时，遇到正确终结符则将第一步创建的扫描索引位置向前移动；如遇到非终结符则调用第二步中创建的相应方法。
5.  如果需要产生解析的结果（比如本例中的二叉树），在方法返回之前将它构造出来。

![20200218222217120.png][]

如上如所示的二叉树用字符串表示为A(B(,C(,),D(,))，使用递归下降的方式解析如下

public class ParseTree {
    
        static class Node {
            private char ch;
            private Node left;
            private Node right;
    
            public Node(char ch, Node left, Node right) {
                this.ch = ch;
                this.left = left;
                this.right = right;
            }
    
            @Override
            public String toString() {
                return "" + ch + "(" +
                        (left == null ? "" : left.toString())
                        + "," +
                        (right == null ? "" : right.toString())
                        + ")";
            }
        }
    
        private int index;
        private char[] chars;
    
        public ParseTree(char[] chars) {
            this.index = 0;
            this.chars = chars;
        }
    
        public Node parse() {
            char lookaheadChar = chars[index];
            if (isLetter(lookaheadChar)) {
                char ch = chars[index++];
                index++; // skip left (
                Node left = parse();
                index++; // skip comma
                Node right = parse();
                index++; // skip right )
                return new Node(ch, left, right);
            } else if (lookaheadChar == ',' || lookaheadChar == ')') {
                return null;
            }
            throw new RuntimeException("syntax error");
        }
    
        private static boolean isLetter(char ch) {
            return ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z');
        }
    
        public static void main(String[] args) {
            String source = "A(B(,C(,)),D(,))";
            ParseTree parseTree = new ParseTree(source.toCharArray());
            Node root = parseTree.parse();
            System.out.println(root);
        }
    }

[https_www.cnblogs.com_Ninputer_archive_2011_06_21_2085527.html]: https://www.cnblogs.com/Ninputer/archive/2011/06/21/2085527.html
[20200218222217120.png]: https://img-blog.csdnimg.cn/20200218222217120.png