内容简介：某一高级程序设计语言的部分词法、语法规则同以上实验，在实验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如下：
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Algorithms on Strings, Trees and Sequences
Dan Gusfield / Cambridge University Press / 1997-5-28 / USD 99.99
String algorithms are a traditional area of study in computer science. In recent years their importance has grown dramatically with the huge increase of electronically stored text and of molecular seq......一起来看看 《Algorithms on Strings, Trees and Sequences》 这本书的介绍吧!
URL 编码/解码
URL 编码/解码
RGB HSV 转换
RGB HSV 互转工具