MENU

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

November 29, 2018 • Read: 9907 • 编译原理阅读设置

实验目的

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

实验内容

某一高级程序设计语言的部分词法、语法规则同以上实验,在实验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如下:

Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

4 Comments
  1. OceanicKang OceanicKang

    我不知道你有没有了解过前缀表达式、后缀表达式的概念。
    比如 2+34 的前缀表达式是 +234,(2+3)4 的前缀表达式是 +234。
    很明显,从左向右依次出现的运算符的优先级是逐渐升高的,那么如果这些符号以栈存储,从右向左依次出栈就可以还原出结果。
    我不知道三地址码是什么,不过从你的介绍来看,感觉应该就是有关运算符优先级的实验。
    我提供一下我的思路:
    2+34 的前缀表达式 +234 从右向左依次出栈,每到符号位停止, 4 3 组合 t1 = 3 4,之后再出栈 2 +,与之前的 t1 组合成 t2 = 2 + t1,这样也就有了你的 t1 = 3 * 4,t2 = 2 + t1
    (2+3)4 的前缀表达式 +234 ,出栈4 3 2 + 组合 t1 = 2 + 3,此时多了一个 4,于是将 4 放回栈中,再出栈 4 组合 t2 = 4 t1,这样就有了 t1 = 2 + 3,t2 = 4 * t1
    如你gif 图中的 x = 1+(2(3+4)) 前缀表达式为 +12+34,那么出栈 4 3 + 组合 t1 = 3 + 4,出栈 2 组合 t2 = 2 t1,出栈 1 + 组合 t3 = 1 + t2,最后 x = t3。
    当然这是我个人的一些看法,可能会有纰漏之处,而且也没有具体测试过是否可行,望见谅@(太开心)

    1. mathor mathor

      @OceanicKang您确实提供了一个很好的思路,蟹蟹@(呵呵)

  2. reality reality

    作者也是刚好在学编译原理吗?

    1. mathor mathor

      @reality是的,这学期的课程