编译器一日一练（DIY系列之复杂语法树）

目暮deep-breaths lv.1

发布时间：2023-09-22 15:13:51 270

相关标签：

代码地址：https://github.com/feixiaoxing/DIYCompiler

之前一章，我们谈到过简单语法树的构建。说是语法树，其实就是一个tree node。它的左子树是一个整数，右子树也是一个整数。所有的工作都是为了构建一个div_node。

在此基础上，大家可以思考一下，如果是一个连续的除法，这个时候应该怎么处理？一个比较容易想到的办法就是在原来简单语法树的基础之上，构建更为复杂的语法树。

div_node expr() throws NumberFormatException :
{
    Token a ;
    Token b ;
    div_node div;
}
{
    a =  
    { 
        value_node node_a = new value_node();
        node_a.set_value(Integer.parseInt( a.image ));
        
        div = new div_node();
        div.set_left_node(node_a);
        
    }
    
    (
    "/" b = 
    {
        value_node node_b = new value_node();
        node_b.set_value(Integer.parseInt( b.image ));
        
        if(div.get_right_node() == null)
        {
            div.set_right_node(node_b);
        }
        else
        {
            div_node prev = div;
            div = new div_node();
            
            div.set_left_node(prev);
            div.set_right_node(node_b);
        }
    }
    )*
    
    
    { return div ; }
}

上面的代码是一个比较典型的实现方式。其中最重要的几句代码，就是div.get_right_node（）这个判断。首先，不管怎么说，node_a和div肯定是要创建的。至于node_b是否要创建，这个要看现场的情况。这里假设node_b需要创建，情况也会有两说。一是当前div的右子树还是null，这个时候不用说，直接赋值上就可以。二是当前div已经满了，这个时候如何解决呢？其实就是在当前div的基础之上再增加一个父节点，将node_b挂到这个父节点上就可以了。

二叉树的访问方法一般是左、右、根，因此有了上面的这个构建语法树的办法，才会按照左、右、根的访问方法将语句按照原来的布局继续解析下去。至此，大家会发现，不管有多少的除法运算，最终的返回值都是一个div_node，只不过他的下面有多少层左子树罢了。

很多编译课程告诉我们，其实后面还有语义分析、中间代码生成，汇编生成等等。但其实来说，有了语法树，本身就可以做很多事情，甚至不需要后面的步骤都可以。比如有了这个除法的语法树，计算就是一件很容易的事情了，

class div_node extends node
{
  div_node() { set_node_type("/");}
  
  public int get_value() {
    int left = 0, right = 0;
    
    // get left node
    if(get_left_node().get_node_type() == "/")
    {
      left = ((div_node)get_left_node()).get_value();
    }
    else
    {
      left = ((value_node)get_left_node()).get_value();
    }

    // get right node
    if(get_right_node() == null)
    {
      return left;
    }
    else
    {
      right = ((value_node)get_right_node()).get_value();
      return left/right;
    }
  }
}

首先它会查看是否有递归，如果有递归左子树，就会继续递归调用。接着，它会看右子树，看是否确实有除法计算，没有的话，直接返回left即可；有的话，需要进行left、right的除法运算。

上面给出的都是代码的片段，这里给出完整的代码。其实这后面的逻辑都不复杂，关键是思考怎么一步一步实现这一点的。此外，一定要动手实践。哪怕是再简单的东西，有没有自己动手去做，效果还是大不一样的。

options {
    STATIC = false;
}
 
PARSER_BEGIN(Parse)
import java.io.*;

class node
{
    public node left;
    public node right;
    public String node_type;
    
    node() {this.left = this.right = null;}
    public void set_left_node(node left) { this.left = left;}
    public node get_left_node() { return this.left;}
    
    public void set_right_node(node right) { this.right = right;}
    public node get_right_node() {return this.right;}
    
    public void set_node_type(String node_type) {this.node_type = node_type;}
    public String get_node_type() {return this.node_type;}
}

class value_node extends node
{
    public int value;
    
    value_node() { set_node_type("value_node");}
    public int get_value() { return this.value;}
    public void set_value(int value) {this.value = value;}
}

class div_node extends node
{
    div_node() { set_node_type("/");}
    
    public int get_value() {
        int left = 0, right = 0;
        
        // get left node
        if(get_left_node().get_node_type() == "/")
        {
            left = ((div_node)get_left_node()).get_value();
        }
        else
        {
            left = ((value_node)get_left_node()).get_value();
        }

        // get right node
        if(get_right_node() == null)
        {
            return left;
        }
        else
        {
            right = ((value_node)get_right_node()).get_value();
            return left/right;
        }
    }
}

public class Parse {

    public static void main(String[] args) {
        for (String arg : args) {
            try {
                System.out.println(evaluate(arg).get_value());
            } catch (ParseException ex) {
                System.err.println(ex.getMessage());
            }
        }
    }
 
    public static div_node evaluate(String src) throws ParseException {
        Reader reader = new StringReader(src);
        return  new Parse(reader).expr();
    }
}
PARSER_END(Parse)
 
SKIP: { <[" ", "\t", "\r", "\n"]> }
TOKEN: {
    
}
 
div_node expr() throws NumberFormatException :
{
    Token a ;
    Token b ;
    div_node div;
}
{
    a =  
    { 
        value_node node_a = new value_node();
        node_a.set_value(Integer.parseInt( a.image ));
        
        div = new div_node();
        div.set_left_node(node_a);
        
    }
    
    (
    "/" b = 
    {
        value_node node_b = new value_node();
        node_b.set_value(Integer.parseInt( b.image ));
        
        if(div.get_right_node() == null)
        {
            div.set_right_node(node_b);
        }
        else
        {
            div_node prev = div;
            div = new div_node();
            
            div.set_left_node(prev);
            div.set_right_node(node_b);
        }
    }
    )*
    
    
    { return div ; }
}

文章来源： https://blog.51cto.com/u_15888909/5880631

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。