实验目的展开目录
- 理解语义分析及中间代码生成在编译程序中的作用
- 在语法分析的基础上进行语义检查并生成中间代码
- 加深对语法制导翻译的理解
- 掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法
实验内容展开目录
某一高级程序设计语言的部分词法、语法规则同以上实验,在实验 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 如下:
我不知道你有没有了解过前缀表达式、后缀表达式的概念。
比如 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。
当然这是我个人的一些看法,可能会有纰漏之处,而且也没有具体测试过是否可行,望见谅 @(太开心)
您确实提供了一个很好的思路,蟹蟹 @(呵呵)
作者也是刚好在学编译原理吗?
是的,这学期的课程