内容简介：某一高级程序设计语言的部分词法、语法规则同以上实验，在实验3语法分析程序基础上，设计和实现该语言的语义分析程序。要求：输入是一段语句串，输出为三地址指令形式的四元式代码对于语句串：
实验目的
- 理解语义分析及中间代码生成在编译程序中的作用
- 在语法分析的基础上进行语义检查并生成中间代码
- 加深对语法制导翻译的理解
- 掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法
实验内容
某一高级程序设计语言的部分词法、语法规则同以上实验，在实验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,...），操作数1 data1 ，运算符 op ，操作数2 data2 ，所以我们需要把这几个元素定义为一个类封装起来
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如下：
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
算法交易：制胜策略与原理
［美］欧内斯特·陈（Ernest P. Chan） / 高闻酉、黄蕊 / 机械工业出版社 / 49.00
本书是一本引人入胜、信息量大、覆盖各类交易策略的图书。无论个人投资者，还是机构投资者，都可以借鉴和使用其中的策略。本书中的策略大致可分为均值回归系统和动量系统两大类。书中不仅介绍了如何使用每种类别的交易策略，更解释了各种策略之所以有效的原因。本书始终以简单、线性的交易策略为重心，因为复杂的交易策略容易受到过度拟合及数据窥探的侵害。数学和软件是算法交易的两条腿。本书用到了一定程度的数学知识，使其对各......一起来看看 《算法交易：制胜策略与原理》 这本书的介绍吧!
