本文最后更新于：2 年前

语义分析器的构造

语法制导翻译绘制函数图形

表达式值的计算：深度优先后序遍历语法树
图形的绘制：画出每个坐标点

绘图所需的语义处理

1.从origin、rot和scale中得到坐标变换所需的信息；
2.for_draw语句根据t的每一个值进行如下处理：

计算被绘制点的横、纵坐标值；
根据坐标变换信息进行坐标变换，得到实际坐标；
根据点的实际坐标画出该点。

语法制导翻译的基本步骤

为文法符号设计属性；
设计语义规则中所需的辅助函数；
为产生式设计语义规则。

例子

文法：ScaleStatment → SCALE IS
L_BRACKET Expression COMMA Expression R_BRACKET
可简写为：S → SCALE IS (E,E)
它的作用是提供横、纵坐标的比例因子。
因此需要：
设计属性：.x和.y，分别保存比例因子；
设计计算表达式值的辅助函数：
GetExprValue(nptr)，它返回表达式树的值；
设计语义规则：
S → SCALE IS (E1,E2) S.x:=GetExprValue(E1.nptr);
S.y:=GetExprValue(E2.nptr);

几个关键变量及需构建的函数

<1> 全程变量：
double Parameter=0; // 为参数T分配的变量
double Origin_x=0.0, Origin_y=0.0;// 用于记录平移距离
double Rot_ang=0.0; // 用于记录旋转角度
double Scale_x=1, Scale_y=1; // 用于记录比例因子

<2> 辅助语义函数
a) 计算表达式的值：深度优先后序遍历语法树
double GetExprValue(…root);
b) 计算点的坐标值：首先获取坐标值，然后进行坐标变换
static void CalcCoord(….);
c) 绘制一个点(与环境有关): 【这里我java里就没有此绘制函数，主要思路是存下所有的点借助JFrame和JPanel绘制所有的点】
void DrawPixel(….);
d) 循环绘制所有的点：
void DrawLoop( double Start,
double End,
double Step,
…);
e)计算点的坐标：
static void CalcCoord (…)；
要计算原始坐标、比例变换、旋转变换、平移变换

语法分析器+语义分析器的代码

import java.awt.*;
import java.io.*;
import javax.swing.*;
class Tree {                     //语法树的类,
    String type="";
    int rank;
    int left=-1;   //T、FUNC都有特殊含义
    int right=-1;
    double constant=0.0d;
}
class Coordinate{
    double x;
    double y;
}



public class YuFa_Analyzer extends  JFrame {
    class Draw2 extends JFrame {
        public Draw2()
        {
            MyPanel2 mp= new MyPanel2();
            this.add(mp);
            this.setSize(500, 500);
            this.setDefaultCloseOperation(EXIT_ON_CLOSE);
            this.setVisible(true);
        }
    }
    //定义一个panel、用于绘制和实现图像
    class MyPanel2 extends JPanel
    {
        //覆盖jpanel的paint方法
        public void paint(Graphics g)
        {
            //调用父类函数进行初始化，绝对不可少
            super.paint(g);
            //System.out.println("我开始画了！");
            for(int i=0;i<Dian;i++) {
                g.drawOval((int)coord[i].x, (int)(Origin_y-(coord[i].y-Origin_y)), 1, 1);
            }
        }
    }
    static int blank=0;
    static int Dian=0;
    static int current=0;
    static int sum;
    static OutputToken Liu=new OutputToken();
    static double Parameter=0;            // 为参数T分配的变量
    static double Origin_x=0.0, Origin_y=0.0;// 用于记录平移距离
    static double Rot_ang=0.0;            // 用于记录旋转角度
    static double Scale_x=1, Scale_y=1;        // 用于记录比例因子
    static Coordinate[] coord=new Coordinate[10000];
    public  YuFa_Analyzer()
    {
        for (int j = 0; j < 10000; j++) //对象需要分别初始化
        {
            coord[j] = new Coordinate();
        }
        Draw2 demo=new Draw2();
    }



    public void YuFa() throws IOException {

        sum=Liu.Cifa_Analyzer();

        Tree point[]=new Tree[sum+1]; //最后一位留来创造识别 负数来填补的零
        for (int j = 0; j < sum; j++) //对象需要分别初始化
        {
            point[j] = new Tree();
            point[j].rank=j;
            point[j].type=Liu.tokens[j].type;
        }
        point[sum]=new Tree();
        point[sum].rank=sum;
        point[sum].type="CONST_ID";
        point[sum].right=-2;

        Program(point);

        /*for(int i=0;i<sum+1;i++){
            System.out.println(point[i].type+"  "+point[i].left+"  "+point[i].right+"   "+point[i].constant+"   "+point[i].rank);
        }
        */

    }


    public void Program(Tree point[]) {
        while (!Liu.tokens[current].lexeme.equals("NONTOKEN")) {
        Statement(point);
        MatchToken("SEMICO");
        if(Liu.tokens[current].type.equals("COMMENT")){
            MatchToken("COMMENT");
        }
        }

    }

    public void Statement(Tree point[]){
        if(Liu.tokens[current].type.equals("ORIGIN")){
            current++;
            OriginStatement(point);
        }
        else if(Liu.tokens[current].type.equals("SCALE")){
            current++;
            ScaleStatement(point);
        }
        else if(Liu.tokens[current].type.equals("ROT")){
            current++;
            RotStatement(point);
        }
        else if(Liu.tokens[current].type.equals("FOR")){
            current++;
            ForStatement(point);
        }
        else{
            System.out.println(Liu.tokens[current].type+" 语法错误  "+current);
            System.exit(0);
        }
    }
    public void OriginStatement(Tree point[]){
        MatchToken("IS");
        MatchToken("L_BRACKET");
        int x=Expression(point);
        System.out.println();
        PrintTree(point,x,0);
        Origin_x=GetExprValue(point,x);
        MatchToken("COMMA");
        int y=Expression(point);
        PrintTree(point,y,0);
        Origin_y=GetExprValue(point,y);
        MatchToken("R_BRACKET");
    }
    public void ScaleStatement(Tree point[]){
        MatchToken("IS");
        MatchToken("L_BRACKET");
        int x=Expression(point);
        PrintTree(point,x,0);
        Scale_x=GetExprValue(point,x);
        MatchToken("COMMA");
        int y=Expression(point);
        PrintTree(point,y,0);
        Scale_y=GetExprValue(point,y);
        MatchToken("R_BRACKET");
    }
    public void RotStatement(Tree point[]){
        MatchToken("IS");
        int x=Expression(point);
        PrintTree(point,x,0);
        Rot_ang=GetExprValue(point,x);
        //System.out.println("根为:"+x);
        //System.out.println("Rot为:"+Rot_ang);
    }
    public void ForStatement(Tree point[]){
        int a,b,c,d,e;
        MatchToken("T");
        MatchToken("FROM");
        a=Expression(point);
        PrintTree(point,a,0);
        double Start=GetExprValue(point,a);
        MatchToken("TO");
        b=Expression(point);
        PrintTree(point,b,0);
        double End=GetExprValue(point,b);
        MatchToken("STEP");
        c=Expression(point);
        PrintTree(point,c,0);
        double Step=GetExprValue(point,c);
        MatchToken("DRAW");
        MatchToken("L_BRACKET");
        d=Expression(point);//x坐标
        PrintTree(point,d,0);
        MatchToken("COMMA");
        e=Expression(point);    //y坐标
        PrintTree(point,e,0);
        MatchToken("R_BRACKET");

        DrawLoop(Start,End,Step,d,e,point);   //开始画画！！
    }

    public int Expression(Tree point[]){
        int left,right;
        left=Term(point);
        while(Liu.tokens[current].type.equals("PLUS")||Liu.tokens[current].type.equals("MINUS")){
            //point[current].type=Liu.tokens[current].type;
            int mark=current;
            MatchToken(Liu.tokens[current].type);
            right=Term(point);
            MakeNode(point,mark,left,right);
            left=mark;
        }
        return left;
    }

    public int Term(Tree point[]){
        int left,right;
        left=Factor(point);
        while(Liu.tokens[current].type.equals("MUL")||Liu.tokens[current].type.equals("DIV")) {
            int mark = current;
            MatchToken(Liu.tokens[current].type);
            right = Factor(point);
            MakeNode(point, mark, left, right);
            left = mark;
        }
        return left;
    }

    public int Factor(Tree point[]){
        int left,right;
        if(Liu.tokens[current].type.equals("PLUS")||Liu.tokens[current].type.equals("MINUS")){
            left=current;
            MatchToken(Liu.tokens[current].type);
            right=Factor(point);
            MakeNode(point,left,sum,right);
        }
        else{
            left=component(point);

        }

        return left;
    }

    public int component(Tree point[]){
        int left,right,mark;
        left=Atom(point);

        while(true) {
            if (Liu.tokens[current].type.equals("POWER")) {
                mark = current;
                MatchToken("POWER");
                right = component(point);
                MakeNode(point, mark, left, right);
                left=mark;
            }
            else{
                break;
            }
        }
        return left;
    }

    public int Atom(Tree point[]){
        int left,right,mark;
        left=0;//无奈的初始化
        if(Liu.tokens[current].type.equals("CONST_ID")){
            left=current;
            mark=current;
            MatchToken("CONST_ID");
            MakeNode(point,mark,left,left);//常数的left right参数没啥用
        }
        else if(Liu.tokens[current].type.equals("T")){
            left=current;
            mark=current;
            MatchToken("T");
            MakeNode(point,mark,left,left);//T的left right参数没啥用
        }
        else if(Liu.tokens[current].type.equals("FUNC")){
            left=current;
            mark=current;
            MatchToken("FUNC");
            MatchToken("L_BRACKET");
            right=Expression(point);
            MatchToken("R_BRACKET");
            MakeNode(point,mark,left,right);
        }
        else if(Liu.tokens[current].type.equals("L_BRACKET")){
            MatchToken("L_BRACKET");
            //mark=current;
            left=Expression(point);
            MatchToken("R_BRACKET");

        }
        else{
            System.out.println(Liu.tokens[current].type+"  WRONG1  "+current);
            System.exit(0);//出错了
        }
        return left;
    }






    public void MakeNode(Tree point[],int mark,int left,int right){//制作节点，并且只要判断left和right值相不相等，就能知道哪些Token在Expression中，这里程序其实没用上...
        if(point[mark].type.equals("CONST_ID")){
            point[mark].constant=Liu.tokens[mark].value;
            point[mark].right=-2;
        }
        else if(point[mark].type.equals("T")){ //制定一个规则表示T
            point[mark].left=-100;
            point[mark].right=-10;
        }
        else if(point[mark].type.equals("FUNC")){  //制定一个规则来表示不同的func，其实没啥用...
            //"SIN", "COS", "TAN", "LN", "EXP", "SQRT"
            if(Liu.tokens[mark].lexeme.toUpperCase().equals("COS")){
                point[mark].left=-2;
                point[mark].right=right;
            }
            else if(Liu.tokens[mark].lexeme.toUpperCase().equals("SIN")){
                point[mark].left=-3;
                point[mark].right=right;
            }
            else if(Liu.tokens[mark].lexeme.toUpperCase().equals("TAN")){
                point[mark].left=-4;
                point[mark].right=right;
            }
            else if(Liu.tokens[mark].lexeme.toUpperCase().equals("LN")){
                point[mark].left=-5;
                point[mark].right=right;
            }
            else if(Liu.tokens[mark].lexeme.toUpperCase().equals("EXP")){
                point[mark].left=-6;
                point[mark].right=right;
            }
            else if(Liu.tokens[mark].lexeme.toUpperCase().equals("SQRT")){
                point[mark].left=-7;
                point[mark].right=right;
            }
        }
        else{
            point[mark].left=left;
            point[mark].right=right;
        }
    }

    public void MatchToken(String token){
        if(Liu.tokens[current].type.equals(token)){
            current++;
        }
        else {
            System.out.println(Liu.tokens[current].type+" Match WRRRRROOOOONG! "+current);
            System.exit(0);
        }
    }

    public double GetExprValue(Tree[] point, int root){
        if(point[root].type.equals("PLUS")){
            return GetExprValue(point,point[root].left)+GetExprValue(point,point[root].right);
        }
        else if(point[root].type.equals("MINUS")){
            return GetExprValue(point,point[root].left)-GetExprValue(point,point[root].right);
        }
        else if(point[root].type.equals("MUL")){
            return GetExprValue(point,point[root].left)*GetExprValue(point,point[root].right);
        }
        else if(point[root].type.equals("DIV")){
            return GetExprValue(point,point[root].left)/GetExprValue(point,point[root].right);
        }
        else if(point[root].type.equals("POWER")){
            return Math.pow(GetExprValue(point,point[root].left),GetExprValue(point,point[root].right));
        }
        else if(point[root].type.equals("FUNC")){
            switch(point[root].left){
                case -2:
                    return Math.cos(GetExprValue(point,point[root].right));
                case -3:
                    return Math.sin(GetExprValue(point,point[root].right));
                case -4:
                    return Math.tan(GetExprValue(point,point[root].right));
                case -5:
                    return Math.log(GetExprValue(point,point[root].right));
                case -6:
                    return Math.exp(GetExprValue(point,point[root].right));
                case -7:
                    return Math.sqrt(GetExprValue(point,point[root].right));
            }
        }
        else if(point[root].type.equals("CONST_ID")){
            return point[root].constant;
        }
        else if(point[root].type.equals("T")){
            return Parameter;
        }
        else{
            System.out.println("计算Expression出错");
            return 0.0d;
        }

        return 0.0d;
    }

    public void DrawLoop(double Start,
                         double End,
                         double Step,
                         int x,
                         int y,
                         Tree point[]){

        for(Parameter=Start;Parameter<=End;Parameter+=Step){
            coord[Dian]=CalcCoord(point,coord[Dian],x,y);
            Dian++;
        }
        System.out.println("有几个点！！："+Dian);
    }

    public Coordinate CalcCoord(Tree point[],Coordinate coord,int x,int y){
        double local_x,local_y,temp;
        local_x=GetExprValue(point,x);
        local_y=GetExprValue(point,y);
        local_x*=Scale_x;
        local_y*=Scale_y;
        temp=local_x*Math.cos(Rot_ang)+local_y*Math.sin(Rot_ang);
        local_y=local_y*Math.cos(Rot_ang)-local_x*Math.sin(Rot_ang);
        local_x=temp;
        local_x+=Origin_x;
        local_y+=Origin_y;
        coord.x=local_x;
        coord.y=local_y;
        return coord;
    }

    public void  PrintTree(Tree point[],int root,int k)
    {
        int i=0;
        for(i=0;i<k;i++){
            System.out.print('\t');
        }
        k++;
        System.out.println(point[root].type);
        if(point[root].type.equals("PLUS")){
            PrintTree(point,point[root].left,k);
            PrintTree(point,point[root].right,k);
        }
        else if(point[root].type.equals("MINUS")){
            PrintTree(point,point[root].left,k);
            PrintTree(point,point[root].right,k);
        }
        else if(point[root].type.equals("MUL")){
            PrintTree(point,point[root].left,k);
            PrintTree(point,point[root].right,k);
        }
        else if(point[root].type.equals("DIV")){
            PrintTree(point,point[root].left,k);
            PrintTree(point,point[root].right,k);
        }
        else if(point[root].type.equals("POWER")){
            PrintTree(point,point[root].left,k);
            PrintTree(point,point[root].right,k);
        }
        else if(point[root].type.equals("FUNC")){
            switch(point[root].left){
                case -2:
                    PrintTree(point,point[root].right,k);
                    break;
                case -3:
                    PrintTree(point,point[root].right,k);
                    break;
                case -4:
                    PrintTree(point,point[root].right,k);
                    break;
                case -5:
                    PrintTree(point,point[root].right,k);
                    break;
                case -6:
                    PrintTree(point,point[root].right,k);
                    break;
                case -7:
                    PrintTree(point,point[root].right,k);
                    break;

            }
        }
        else if(point[root].type.equals("CONST_ID")){

        }
        else if(point[root].type.equals("T")){

        }
    }

}

编译原理

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

PekingUniversityOJ No.1485 上一篇

语法分析器下一篇