语法树构建中的左递归

最近在尝试实现一个c语言编译器。其中涉及到语法树的构建。在解析表达式时，就需要考虑左递归和优先级问题。左递归，可以通过 百度百科 中的方式来消除左递归。但是由于表达式又存在优先级问题。所以消除过程十分繁琐。如下简单的计算器实现例子：

消除左递归，并添加优先级后，如下：

Num: [0-9]+
factor: Num | '(' expr3 ')'
 
term_tail: | ('*' expr1 | '/' expr1) term_tail
term: factor term
 
expr_tail: | ('+' expr2 | '-' expr2) expr_tail
expr: term expr_tail

可以看出，表达式比较复杂。如果再添加其他运算，如位移运算，逻辑运算，以及其他自定义运算。则实现起来及其复杂。

Antlr4

如果使用 antlr4则语法就会变得很简单。如下，有左递归的表达式在或中越靠前，优先级越高，factor 类则无影响。

Num: [0-9]+
expr: 
     Number
    | '(' expr ')'
    | expr ('*'|'/') expr
    | expr ('+'|'-') expr
    ; 

可以在vscode 中使用 ANTLR4 grammar syntax support 插件 测试该语法。

1. 编写g4 文件

2. ctrl+s 保存以下，生成 .antlr文件夹

3. 添加 .vscode/launch.json 写入如下内容

   {
       "version": "0.2.0",
       "configurations": [
           {
               "name": "Debug ANTLR4 grammar - Test - Expr", 
               "type": "antlr-debug", 
               "request": "launch",
               "input": "test.txt", // 测试内容文件
               "grammar": "Test.g4", // 语法文件
               "startRule": "expr", // 入口表达式
               "printParseTree": true, // 是否打印语法树
               "visualParseTree": true, // 是否显示语法树
           }
       ]
   }
   

4. 在 Test.g4 目录下 F5 调试即可

image-20200626180223745

可以看到，正确生成语法树。且优先级正确。没有错误匹配。

自己动手实现

antlr 虽然好用，但是如果我们想要实现一个新的语言，并实现自举，则antlr并不是一个很好的选择。需要自己实现语法树的构建。其中的难点也是表达式的解析。以下使用一种特殊的方式消除左递归：左递归表达式中，左边的值的 tryx 必须大于自己，右边的 tryx 必须 大于等于自己。即 expr: A op B 中的 A必须优先级高于自己， B优先级至少是自己。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Calculator {

    public static int Num = 1024;

    public static int[] tokens;
    public static String[] values;

    public static int tkAt = 0;

    public static void main(String[] args) {
        tokens = new int[1024];
        values = new String[1024];

        lexer("3 - 4 * 5 + 6 * (7 - 1)");

        Node root = new Node();
        root.value = "root";
        if (valueExpr(0, root)) {
            Tree.print(root);
        } else {
            System.err.println("error");
        }
    }
    
    // 词法器
    public static void lexer(String content) {
        int at = 0;
        for (int i = 0; i < content.length(); i++) {
            char tk = content.charAt(i);

            if (tk == ' ') {
                continue;
            }

            if (tk > '0' && tk <= '9') {
                int start = i;
                int end = i + 1;

                for (; end < content.length(); end++) {
                    tk = content.charAt(end);
                    if (!(tk >= '0' && tk <= '9')) {
                        break;
                    }
                }

                i = end - 1;
                String str = content.substring(start, end);

                values[at] = str;
                tokens[at++] = Num;

                continue;
            }

            if (tk == '+' || tk == '*' || tk == '/' || tk == '-' || tk == '(' || tk == ')') {
                tokens[at++] = tk;
                continue;
            }

            System.err.println("unkown token :" + tk);
            System.exit(0);
        }
    }

    public static void next() {
        tkAt++;
    }

    public static boolean match(int tk) {
        if (tk == tokens[tkAt]) {
            return true;
        }
        return false;
    }

    public static class Node {
        public String value;
        public List<Node> children = new ArrayList<>();

        @Override
        public String toString() {
            return String.format("[value: %s, children: %s]", value, Arrays.toString(children.toArray()));
        }
    }

    // valueExpr: 
    // 3    Num
    // 2    | '(' valueExpr ')'
    // 1    | valueExpr ('*' | '/') valueExpr
    // 0    | valueExpr ('+' | '-') valueExpr
    public static boolean valueExpr(int tryx, Node parent) {

        try {
            Thread.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        int tkAtBck = tkAt;
        int step = 0;

        // 由于java不支持 goto, 这里用循环实现 goto
        while (true) {
            tkAt = tkAtBck;
            switch (step + "") {
                case "0":
                    if (tryx <= step++) {
                        Node node = new Node();
                        if (!valueExpr(step, node)) {
                            continue;
                        }

                        next();
                        if (!match('+') && !match('-')) {
                            continue;
                        }
                        node.value = "" + (char) tokens[tkAt];

                        next();
                        if (!valueExpr(step - 1, node)) {
                            return false;
                        }

                        parent.children.add(node);
                        return true;
                    }
                    break;
                case "1":
                    if (tryx <= step++) {
                        Node node = new Node();
                        if (!valueExpr(step, node)) {
                            continue;
                        }

                        next();
                        if (!match('*') && !match('/')) {
                            continue;
                        }

                        node.value = "" + (char) tokens[tkAt];

                        next();
                        if (!valueExpr(step - 1, node)) {
                            return false;
                        }

                        parent.children.add(node);
                        return true;
                    }
                    break;
                case "2":
                    if (tryx <= step++) {
                        Node node = new Node();
                        if (!match('(')) {
                            continue;
                        }

                        next();
                        if (!valueExpr(0, node)) {
                            return false;
                        }

                        next();
                        if (!match(')')) {
                            return false;
                        }
                        node.value = "()";
                        parent.children.add(node);
                        return true;
                    }
                    break;
                case "3":
                    if (tryx <= step++) {
                        Node node = new Node();
                        if (match(Num)) {
                            node.value = values[tkAt];
                            parent.children.add(node);
                            return true;
                        }
                    }
                    break;
                default:
                    return false;
            }
        }
    }
}

其中 Tree.print(root); 就是打印生成节点树。运行结果如下。

image-20200626174621941

如果需要实现计算，则只需对节点树进行后序遍历，入栈。遇到符号弹出两个值进行计算，然后放回栈继续即可。