daily pastebin goal
61%
SHARE
TWEET

Untitled

a guest Oct 11th, 2018 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class MaximalMunch
  5. {
  6.  
  7.  Scanner reader;
  8.  Vector<Node> nodes;
  9.  Stack<String> instructions;
  10.  
  11.  Node root;
  12.  
  13.  //this is the list of subtree roots to evaluate
  14.  Stack<Node> subtree_nodes;
  15.  
  16.  public MaximalMunch (String filename)
  17.  {
  18.   try
  19.   {
  20.    reader = new Scanner (new File (filename));
  21.   }
  22.   catch (Exception f)
  23.   {
  24.    System.out.println("File not found");
  25.    System.exit(1);
  26.   }
  27.  
  28.   nodes = new Vector<Node> ();
  29.   subtree_nodes = new Stack<Node> ();
  30.  
  31.   read();
  32.   assemble();
  33.  
  34.  }
  35.  
  36.  //read in the nodes
  37.  public void read ()
  38.  {
  39.  
  40.   while (reader.hasNext())
  41.   {
  42.    String line = reader.next();
  43.    
  44.    int n = 0;
  45.    
  46.    //count how deep the node is
  47.    for (int i = 0; i < line.length(); i++)
  48.    {
  49.     if (line.charAt(i) == '=')
  50.      n++;
  51.     else
  52.      break;
  53.    }
  54.  
  55.    nodes.add (new Node (line.substring(n), n));
  56.  
  57.   }
  58.    
  59.  }
  60.  
  61.  //hurp, build tree
  62.  public void assemble ()
  63.  {
  64.  
  65.   root = nodes.remove(0);
  66.   Node current = nodes.remove(0);
  67.  
  68.   while (nodes.size() > 0)
  69.   {
  70.    Node inspect = nodes.remove(0);
  71.  
  72.    //check if need to backtrack up tree
  73.    if (inspect.nest < current.nest)
  74.    {
  75.  
  76.     for (int i = 0; i < current.nest - inspect.nest+1; i++)
  77.      current = current.parent;
  78.  
  79.      current.addChild(inspect);
  80.      current = inspect;
  81.    }
  82.    else
  83.     current.addChild(inspect);
  84.  
  85.   }
  86.  
  87.  }
  88.  
  89.  //match LOAD
  90.  public boolean match_load (Node root)
  91.  {
  92.   boolean match = false;
  93.  
  94.   if (root.value.equals("MEM") && root.children.size() > 0)
  95.   {
  96.    //check for ADDI matches
  97.    if (root.children.get(0).value.equals("CONST"))
  98.    {
  99.     subtree_nodes.push(root.children.get(1));
  100.  
  101.     instructions.push("LOAD r<- M[r + " + root.children.get(0).children.get(0).value + "]");
  102.  
  103.    }
  104.    else if (root.children.get(1).value.equals("CONST"))
  105.    {
  106.     subtree_nodes.push(root.children.get(0));
  107.    
  108.     instructions.push("LOAD r<- M[r + " + root.children.get(1).children.get(1).value + "]");
  109.    }
  110.  
  111.   }
  112.  
  113.   return match;
  114.  
  115.  }
  116.  
  117.  //tries to match store tiles
  118.  public boolean match_store (Node root)
  119.  {
  120.   boolean match = false;
  121.  
  122.   if (root.value.equals("MOVE"))
  123.   {
  124.    if (root.children.get(0).value.equals("MEM"))
  125.    {
  126.    
  127.     if (
  128.  
  129.     subtree_nodes.push(root.children.get(0));
  130.    
  131.     instructions.push("STORE M[r+" + "<-r");
  132.  
  133.    }
  134.    else if (root.children.get(1).value.equals("MEM"))
  135.    {
  136.    
  137.  
  138.     subtree_nodes.push(root.children.get(0));
  139.    
  140.     instructions.push("STORE M[r+" + "<-r");
  141.  
  142.  
  143.    }
  144.  
  145.   }
  146.  
  147.   return match;
  148.  
  149.  }
  150.  
  151.  //tries to match arithmetic operations ( + * - / )
  152.  public boolean match_arith (Node root)
  153.  {
  154.  
  155.   boolean match = false;
  156.  
  157.   if (root.children.size() > 0)
  158.   {
  159.     //check for operator
  160.     if (root.children.get(0).value.equals("+"))
  161.     {
  162.      if (root.children.get(0).children.size() == 2)
  163.       match = true;
  164.      
  165.      subtree_nodes.push(root.children.get(0));
  166.    
  167.      instructions.push("ADD r<- M[r+r]");
  168.  
  169.     }
  170.     else if (root.children.get(0).value.equals("-"))
  171.     {
  172.      if (root.children.get(0).children.size() == 2)
  173.       match = true;
  174.  
  175.      subtree_nodes.push(root.children.get(0));
  176.    
  177.      instructions.push("SUB r<- M[r-r]");
  178.  
  179.     }
  180.     else if (root.children.get(0).value.equals("*"))
  181.     {
  182.      if (root.children.get(0).children.size() == 2)
  183.       match = true;
  184.  
  185.      subtree_nodes.push(root.children.get(0));
  186.    
  187.      instructions.push("MUL r<- M[rxr]");
  188.  
  189.     }
  190.     else if (root.children.get(0).value.equals("/"))
  191.     {
  192.      if (root.children.get(0).children.size() == 2)
  193.       match = true;
  194.  
  195.      subtree_nodes.push(root.children.get(0));
  196.    
  197.      instructions.push("DIV r<- M[r/r]");
  198.  
  199.     }
  200.  
  201.  
  202.     }
  203.  
  204.    //push the subtree nodes into the list of subtrees to evaluate
  205.    subtree_nodes.push(root.children.get(0));
  206.    subtree_nodes.push(root.children.get(1));
  207.   }
  208.  
  209.  
  210.  
  211.   return match;
  212.  
  213.  }
  214.  
  215.  //match ADDI
  216.  public boolean match_addi (Node root)
  217.  {
  218.  
  219.   boolean match = false;
  220.  
  221.   if (root.value.equals("+") && root.children.size() == 2)
  222.   {
  223.    if (root.children.get(0).value.equals("CONST"))
  224.    {
  225.     subtree_nodes.push(root.children.get(1));
  226.    }
  227.    else if (root.children.get(1).value.equals("CONST"))
  228.    {
  229.     subtree_nodes.push(root.children.get(0));
  230.    }
  231.  
  232.   }
  233.  
  234.   return match;
  235.  
  236.  }
  237.  
  238.  //match CONST
  239.  public boolean match_const (Node root)
  240.  {
  241.   boolean match = false;
  242.  
  243.   if (root.value.equals("CONST"))
  244.    match = true;
  245.  
  246.   return match;  
  247.  
  248.  }
  249.  
  250.  //match SUBI
  251.  public boolean match_subi (Node root)
  252.  {
  253.   boolean match = false;
  254.  
  255.   if (root.value.equals("-") && root.children.size() == 2)
  256.   {
  257.    if (root.children.get(1).value.equals("CONST"))
  258.    {
  259.     match = true;
  260.     subtree_nodes.push(root.children.get(0));
  261.    }
  262.   }
  263.  
  264.   return match;
  265.  }
  266.  
  267. //match MOVEM
  268.  
  269.  public boolean match_movem (Node root)
  270.  {
  271.   boolean match = false;
  272.  
  273.   if (root.value.equals("MOVE") && root.children.size() == 2)
  274.   {
  275.    if (root.children.get(0).equals("MEM") && root.children.get(1).equals("MEM") && root.children.get(0).children.size() > 0 && root.children.get(1).children.size() > 0)
  276.     {
  277.      match = true;
  278.      subtree_nodes.push(root.children.get(0));
  279.      subtree_nodes.push(root.children.get(1));
  280.     }
  281.   }
  282.  
  283.   return match;
  284.  
  285.  }
  286.  
  287.  //matches tiles
  288.  public void munch ()
  289.  {
  290.  
  291.   subtree_nodes.push(root);
  292.  
  293.   //tries to match tiles in order of biggest to smallest
  294.  
  295.   while (!subtree_nodes.isEmpty())
  296.   {
  297.  
  298.    Node current = subtree_nodes.pop();
  299.  
  300.    if (match_store(current))
  301.    {
  302.    
  303.  
  304.    }
  305.    else if (match_load(current))
  306.    {
  307.    
  308.  
  309.    }
  310.    else if (match_arith(current))
  311.    {
  312.  
  313.  
  314.    }
  315.    else if (match_movem(current))
  316.    {
  317.  
  318.  
  319.    }
  320.    else if (match_addi(current))
  321.    {
  322.  
  323.  
  324.    }
  325.    else if (match_subi(current))
  326.    {
  327.  
  328.  
  329.    }
  330.    else
  331.    {
  332.  
  333.  
  334.    }
  335.  
  336.  
  337.  
  338.  
  339.   }
  340.  
  341.  }
  342.  
  343.  //write the stuff to file
  344.  public void write ()
  345.  {
  346.  
  347.  
  348.  }
  349.  
  350.  public static void main (String[] args)
  351.  {
  352.  
  353.   MaximalMunch tree = new MaximalMunch(args[0]);
  354.  
  355.  }
  356.  
  357.  //IR node class
  358.  public class Node
  359.  {
  360.   public String value;
  361.   public Node parent;
  362.   public Vector<Node> children;
  363.   public int nest;
  364.  
  365.   public Node (String v, int n)
  366.   {
  367.    value = v;
  368.    nest = n;
  369.    children = new Vector<Node>();
  370.   }
  371.  
  372.   public Node (Node p, String v, int n)
  373.   {
  374.    parent = p;
  375.    value = v;
  376.    nest = n;
  377.    children = new Vector<Node>();
  378.   }
  379.  
  380.   public void addChild (Node n)
  381.   {
  382.    n.parent = this;
  383.    children.add(n);
  384.   }
  385.  
  386.  }
  387.  
  388. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top