编译原理LL1文法分析树(绘图过程)算法实现

时间:2021-12-05 07:39:35
import hjzgg.analysistable.AnalysisTable;
import hjzgg.first.First;
import hjzgg.follow.Follow;
import hjzgg.treenode.TreeNode;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.HeadlessException;
import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.Map;

import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JScrollPane;

public class TreeGraphic {

    private int fatherNode;//treeGraphic搜素是的开始节点
    private TreeNode[] treeGraphic = null;
    
    private final int distNode = 50;//节点之间的距离
    private final int heightNode = 50;//节点的高度
    private final int widthNode = 50;//节点的宽度
    private final int levelHeight = 100;//层与层之间的高度
    private ArrayList<Rectangle> line = new ArrayList<Rectangle>();
    private int curY = 0;
    private int curX = 10;
    
    public TreeGraphic(int fatherNode, TreeNode[] treeGraphic) {
        super();
        this.fatherNode = fatherNode;
        this.treeGraphic = treeGraphic;
        prepareGraphic();
    }
    
    public class TreeFrame extends JFrame{
        private JPanel panel = new JPanel(){
            @Override
            protected void paintComponent(Graphics g) {
                super.paintComponent(g);
                for(Rectangle rect : line){
                    g.drawLine(rect.x, rect.y, rect.width, rect.height);
                }
            }
        };
        private JScrollPane scrollPane = new JScrollPane(panel);
        public TreeFrame() throws HeadlessException {
            super();
            init();
        }

        public TreeFrame(String title) throws HeadlessException {
            super(title);
            init();
        }
        
        private void init(){
            setLayout(new BorderLayout());
            panel.setLayout(null);
            drawTree(fatherNode);
            add(scrollPane, BorderLayout.CENTER);
            int width = curX + 50;
            int height = curY + 50;
            //这里要设置面板的PreferredSize,如果当前Frame大小不能显示PreferredSize那么才会出现滚动条
            panel.setPreferredSize(new Dimension(width, height));
            if(width > 600) width = 600;
            if(height > 300) height = 500;
            setBounds(400, 100, width, height);
            setVisible(true);
        }
        
        public void drawTree(int curNode){
            JLabel label = new JLabel(treeGraphic[curNode].content, JLabel.CENTER);
            label.setBounds(treeGraphic[curNode].getRect());
            label.setFont(new Font("宋体",Font.BOLD, 32));
            label.setOpaque(true);
            label.setBackground(Color.RED);
            panel.add(label);
            if(treeGraphic[curNode].child.size()==0) return;
            int x = treeGraphic[curNode].getRect().x;
            int y = treeGraphic[curNode].getLevel()*levelHeight+heightNode;
            int dist = widthNode / treeGraphic[curNode].child.size();//父节点到子节点连线的距离
            for(int i=0; i<treeGraphic[curNode].child.size(); ++i){
                drawTree(treeGraphic[curNode].child.get(i));
                int xx = treeGraphic[treeGraphic[curNode].child.get(i)].getRect().x + widthNode/2;
                int yy = y+levelHeight-heightNode;
                line.add(new Rectangle(x, y, xx, yy));
                x+=dist;
            }
        }
    }
    
    private void prepareNodeLevel(int curNode, int level){//确定每一个节点的层次
        treeGraphic[curNode].setLevel(level);
        for(int i=0; i<treeGraphic[curNode].child.size(); ++i)
            prepareNodeLevel(treeGraphic[curNode].child.get(i), level+1);
        if(curY < (level+1)*levelHeight) curY = (level+1)*levelHeight;
    }
    
    private void prepareNodeSize(int curNode){//确定节点的坐标位置
        if(treeGraphic[curNode].child.size() == 0){//终结点
            int x = curX; curX+=distNode+widthNode;
            int y = treeGraphic[curNode].getLevel()*levelHeight;
            treeGraphic[curNode].setRect(new Rectangle(x, y, widthNode, heightNode));
            return;
        }
        
        for(int i=0; i<treeGraphic[curNode].child.size(); ++i)
            prepareNodeSize(treeGraphic[curNode].child.get(i));
        int leftChildx=treeGraphic[treeGraphic[curNode].child.get(0)].getRect().x;
        int rightChildx=treeGraphic[treeGraphic[curNode].child.get(treeGraphic[curNode].child.size()-1)].getRect().x;
        //根据左右两边孩子的节点,确定父节点的坐标尺寸
        int parentx = (leftChildx+rightChildx)/2;
        int parenty = treeGraphic[curNode].getLevel()*levelHeight;
        treeGraphic[curNode].setRect(new Rectangle(parentx, parenty, widthNode, heightNode));
    }
    
    private void prepareGraphic(){
        prepareNodeLevel(fatherNode, 0);
        prepareNodeSize(fatherNode);
    }
    
    public static void main(String[] args) {
    //        String[] rightLinearGrammar ={
    //        "S->iCtSA|a",
    //        "A->$|eS", 
    //        "C->b"
    //};
    
    String[] rightLinearGrammar = {
//            "E->TE\'",
//            "E\'->+TE\'|$",
//            "T->FT\'",
//            "T\'->*FT\'|$",
//            "F->(E)|i"
            
            "E->TE\'",
            "E\'->ATE\'|$",
            "T->FT\'",
            "T\'->MFT\'|$",
            "F->(E)|i",
            "A->+|-",
            "M->*|/"
        };
        
    //    String[] rightLinearGrammar = {
    //            "S->ABc",
    //            "A->a|$",
    //            "B->b|$"
    //    };
        
        Map<String, String[]> mp = new LinkedHashMap<String, String[]>();
        try{
            for(int i=0; i<rightLinearGrammar.length; ++i){
                String split1[] = rightLinearGrammar[i].split("->");
                String split2[] = split1[1].split("\\|");
                mp.put(split1[0], split2);
            }
            
        } catch(Exception e){
            e.printStackTrace();
            System.out.println("右线性文法错误!");
        }
        First first = new First(mp);
        first.firstKernealCode();
        Follow follow = new Follow(mp, first.getFirstSet());
        follow.followKernealCode();
        AnalysisTable analysisTable = new AnalysisTable(first.getFirstSet(), follow.getFollowSet(), mp);
        analysisTable.analysisTableKernealCode();
        
        analysisTable.predictiveAnalysis("i+i*(i/i)-i#");
     //通过分析表,在分析句子时产生的分析栈建立分析树,并将分析树返回,利用该程序绘制树 analysisTable.AnalysisTree(); TreeGraphic treeGraphic
= new TreeGraphic(analysisTable.getFatherNode(), analysisTable.getTreeGraphic()); treeGraphic.new TreeFrame("语法分析树"); } }