语义分析及中间代码生成程序设计

实验目的

• 理解语义分析及中间代码生成在编译程序中的作用
• 在语法分析的基础上进行语义检查并生成中间代码
• 加深对语法制导翻译的理解
• 掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法

实验内容

某一高级程序设计语言的部分词法、语法规则同以上实验，在实验3语法分析程序基础上，设计和实现该语言的语义分析程序。

要求：输入是一段语句串，输出为三地址指令形式的四元式代码

对于语句串：begin a=2+3*4; x=(a+1)/3 end #

输出的三地址码为：

t1 = 3 * 4
t2 = 2 + t1
a = t2
t3 = a + 1
t4 = t3/2
x = t4

题目分析

首先观察样例的赋值顺序，a = 2+3*4，我一开始以为输出应该是

t1 = 2
t2 = 3*4
a = t1 + t2

但是结果很明显不是这样，我陷入如何保证输出顺序的问题，也就是先打印t1 = 3*4，而不是先打印t1=2。我想了很多办法，例如控制所有运算符后面的操作优先级更高......

当然，我上面想的都是错的，程序其实自动就能完成这个操作，实验三里我完成了语义分析，使用的是LL递归下降法，也就是，假如有一个给定一个语法规则，将其中所有的非终结符定义为函数。下面我来解释，为什么程序自动就能控制赋值顺序正确

举个例子，假设有一个语法规则是：

S -> num + A
A -> num * num

那么该语法规则对应的语法分析程序伪代码如下：

void S() {
    if(当前是num)
        if(当前是+)
            A()
}
void A() {
    if(当前是num)
        if(当前是*)
            if(当前是num)
                return
}

我们看一下程序的执行流程，首先进入S函数，读到num和+后，进入A函数，读到num、*、num后return。关键就在这里，实际上A函数的深度是比S函数要更深的，可以把整个函数比作盗梦空间，首先进入第一层S函数，然后进入第二层A函数，最后从A函数返回出去，然后从S返回出去。

再回过头来看之前的语句a = 2 + 3 * 4，我们将其抽象一下，就变成a = num + num * num，继续抽象，就变成a = num * T（将num*num看成一个整体T），T的深度肯定是比num要高的，所以我们只要在T函数中把T整体表示出来，也就是t1 = 3*4，此时将字符串t1返回给上一层，就变成t2 = 2 * t1，再将字符串t2返回给上一层，就变成a = t2

因为输出有变量times（times就表示t0,t1,...），操作数1data1，运算符op，操作数2data2，所以我们需要把这几个元素定义为一个类封装起来

class Element {
    String times;
    String data1;
    String op;
    String data2;
    Element(String times,String data1,String op,String data2) {
        this.times = times;
        this.data1 = data1;
        this.op = op;
        this.data2 = data2;
    }
}

之后每次只要收集到Element就将其放入容器中

List<Element> list = new ArrayList<Element>();
static void memset(String times,String data1,String op,String data2) {
    Element e = new Element(times,data1,op,data2);
    elements.add(e);
}

最重要的是熟悉语法规则，清楚知道每次调用函数的时候需不需要从函数中获取什么返回值，获取的返回值是什么。举个例子，因为有语法规则：

<语句> => ID=<表达式>
<表达式> => <项>{+<项> | -<项>}
<项> => <因子>{*<因子> | /<因子>}
<因子> => ID | NUM | (<表达式>)

所以语句函数statement()中调用表达式函数expression()时需要一个字符串获取其返回的值String data1 = expression()

而在表达式函数中调用项函数term()，也需要一个字符串获取其返回值String data1 = term()

项函数又会调用因子函数factor()，所以需要一个字符串获取其返回值String data2 = factor()

最后因子函数factor无论是产生ID还是NUM，都用字符串data来获取，获取以后返回给上一层（退回到项函数里）return data

完整代码

import java.util.*;

class Element {
    String times;
    String data1;
    String op;
    String data2;
    Element(String times,String data1,String op,String data2) {
        this.times = times;
        this.data1 = data1;
        this.op = op;
        this.data2 = data2;
    }
}
public class Main {
    static Map<String, Integer> map = new TreeMap<String, Integer>();
    static List<Character> list = new ArrayList<Character>();
    static List<String> ID = new ArrayList<String>();
    static List<Element> elements = new ArrayList<Element>();
    static String num;
    static StringBuffer str;
    static char now;
    static int syn, p, t = 1;
    static boolean flag = true;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String code = cin.nextLine();
        for(int i = 0;i < code.length();i++)
            list.add(code.charAt(i));
        map.put("begin",1);
        map.put("end", 2);
        scanner();
        parser();
        if(flag)
            for(int i = 0;i < elements.size();i++) {
                Element e = elements.get(i);
                System.out.println(e.times + " = " + e.data1 + " " + e.op + " " + e.data2);
            }
        cin.close();
    }

    private static void scanner() {
        num = "";
        str = new StringBuffer("");
        now = list.get(p++);
        while (now == ' ')
            now = list.get(p++);
        if ((now >= 65 && now <= 90) || (now >= 97 && now <= 122)) { // 字母开头
            while ((now >= 48 && now < 57) || (now >= 65 && now <= 90) || (now >= 97 && now <= 122) || now == 95) { // 字母数字
                str.append(now);
                now = list.get(p++);
                if (map.containsKey(str.toString().trim()) && (now == ' ' || now == '\n')) {
                    syn = map.get(str.toString().trim());
                    return;
                }
            }
            p--;
            syn = 10; // 用户自定义变量
        } else if (now >= 48 && now <= 57) { // 数字开头
            num = "" + now;
            while ((now >= 48 && now <= 57) || now == 46) {
                now = list.get(p++);
                num += now;
            }
            num = num.substring(0,num.length() - 1);
            p--;
            syn = 11;//常量
        } else {
            switch (now) {
            case '+': {
                str.replace(0, 0, "" + now);
                syn = 13;
                break;
            }
            case '-': {
                str.replace(0, 0, "" + now);
                syn = 14;
                break;
            }
            case '*': {
                str.replace(0, 0, "" + now);
                syn = 15;
                break;
            }
            case '/': {
                str.replace(0, 0, "" + now);
                syn = 16;
                break;
            }
            case ';': {
                syn = 26;
                str.replace(0, 0, "" + now);
                break;
            }
            case '(': {
                syn = 27;
                str.replace(0, 0, "" + now);
                break;
            }
            case ')': {
                syn = 28;
                str.replace(0, 0, "" + now);
                break;
            }
            case '=': {
                str.append(now);
                syn = 18;
                break;
            }
            case '#': {
                syn = 0;
                str.replace(0, 0, "" + now);
                break;
            }
            default:
                syn = -1;
            }
        }
    }    
    /*
     * <程序> => begin<语句串>end
     * <语句串> => <语句>{;<语句>}
     * <语句> => ID=<表达式>
     * <表达式> => <项>{+<项> | -<项>}
     * <项> => <因子>{*<因子> | /<因子>}
     * <因子> => ID | NUM | (<表达式>)
     * 
     * ID是用户自定义变量， NUM是常量
     * 输入 begin a=9; x=2*3; b=a+x end # 
     * 输出 success！ 
     * 输入 x=a+b*c end # 
     * 输出 error！
     */
    private static void parser() {
        if(syn == 1) { // 当前单词为begin
            scanner();
            statementString();
            if(syn == 2) { // 当前单词为end
                scanner();
                if(syn == 0 && flag) // 当前单词为#
                    System.out.println("Success!");
            } else {
                if(flag)
                    System.out.println("Error,Miss end!");
                flag = false;
            }
        } else {
            System.out.println("Error,Miss begin!");
            flag = false;
        }
    }

    private static void statementString() { // 语句串
        statement();
        while(syn == 26) { // 分号
            scanner();
            statement();
        }
    }

    private static void statement() { // 语句
        String times,data1;
        if(syn == 10) {// ID
            times = str.toString();
            ID.add(str.toString());
            scanner();
            if(syn == 18) { // 等于号
                scanner();
                data1 = expression();//表达式
                memset(times,data1,"","");
            } else {
                System.out.println("Error,赋值符号错误！");
                flag = false;
            }
        } else {
            System.out.println("Error,语句错误！");
            flag = false;
        }
    }

    private static String expression() { // 表达式
        String times,data1,op,data2;
        data1 = term();
        while(syn == 13 || syn == 14) {// 当前单词为+、－
            if(syn == 13) // +
                op = "+";
            else // -
                op = "-";
            scanner();
            data2 = term();
            times = "t" + (t++);
            memset(times,data1,op,data2);
            data1 = times;
        }
        return data1;
    }

    private static String term() { // 项
        String times,data1,op,data2;
        data1 = factor();
        while(syn == 15 || syn == 16) { // 当前单词为*、/
            if(syn == 15) // *
                op = "*";
            else // /
                op = "/";
            scanner();
            data2 = factor();
            times = "t" + (t++);
            memset(times,data1,op,data2);
            data1 = times;
        }
        return data1;
    }

    private static String factor() { // 因子
        String data = "";
        if(syn == 10) { // ID
            if(!ID.contains(str.toString())) {
                System.out.println("Error,存在未定义变量" + str.toString());
                flag = false;
            } else {
                data = str.toString();
                scanner();
            }
        } else if(syn == 11) { // NUM
            data = num;
            scanner();
        }
        else if(syn == 27) { // 左括号
            scanner();
            data = expression();
            if(syn == 28)
                scanner();
            else {
                System.out.println("Error,')'错误!");
                flag = false;
            }
        } else {
            System.out.println("Error,表达式错误");
            flag = false;
        }
        return data;
    }
    static void memset(String times,String data1,String op,String data2) {
        Element e = new Element(times,data1,op,data2);
        elements.add(e);
    }
}

程序运行的GIF如下：