MENU

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

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

实验目的展开目录

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

实验内容展开目录

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