实验目的
- 理解词法分析在编译过程中的作用
- 初步了解和掌握词法分析程序的实现方法和技术
实验内容
- 编写程序，输入一串字符，判断该字符串是否为合法标识符或合法整型常量
- 无符号数的算术四则运算中的各类单词的识别
输入：由无符号数、+、－、*、/、(、)构成的算术表达式
输出：对识别出的每一单词均单行输出
样例输入：8*2.5-1.0e2
样例输出：
8
*
2.5
－
1.0e2
题目分析
第一种做法，可以首先写出算术表达式的RE，通过RE构建NFA，然后生成最小化DFA，根据DFA构建一棵Trie树。
第二种做法，直接抽象成简单的字符串处理问题，举个例子，小数点后面能跟的只有数字，如果出现了数字以外的字符，就直接报错退出；乘号后面能跟的有左括号"("、数字，如果出现这两种以外的字符，就报错退出。我用的就是这种办法，所以下面我主要讲述一下算法思路
程序实现
定义说明
首先规定一些定义：
字符：若本文中提到字符，则只是限定在0~9、+、－、*、/、(、)这些范围内
字符串：仅由0~9、+、－、*、/、(、)这七种字符任意组合构成的序列串称为字符串
last字符：如果有字符串1+(5/80)-69，now字符是9，那么last字符是6；同理，now字符是/，那么last字符是5
其他说明：本文中会见到很多d，d的含义是0-9的任一数字
last字符与now字符
依据算术表达式的规则，我们能列出last字符确定的情况下，能跟在last字符后面的now字符表。如下图所示(d表示0-9任一数字，e表示科学记数法中的e)。举个例子，假如确定last字符为d，那么除了左括号以外，所有的字符都能跟在d后面；如果确定last字符为e，那么now字符可以为d、+、-，因为可能存在1e9、1e+9、1e-9的情况
算法思路
以字符串15+6e9/(32*(78.5+3.0))为例，首先看一下程序最终输的结果
输入字符串以后，首先初始化last字符为该字符串的第一个字符last = str.charAt(0)，Java语言所有的下标都是从0开始，所以要获取第一个字符'1'，就要取其0位置
初始化last字符后，还应该获取输入字符串的长度len = str.length()，方便后面遍历整个字符串
最后一步准备工作是将当前的last字符赋值给字符串cur，cur的作用后面再讲
然后应该从第2个字符开始，遍历整个字符串，并且利用now字符获取当前遍历到的字符now = str.charAt(i)(i = [1...len-1])，再次强调，下标是从0开始，所以假设一个字符串的长度为5，那么他每个字符的下标分别为0,1,2,3,4
循环体内应该判断last字符属于什么类别，数字？加号？还是减号等等，然后分别进入相应的函数，判断last字符和now字符的组合是否合法，也就是是否符合上面的那张表
还是以上面的字符串15+6e9/(32*(78.5+3.0))为例，last字符为1，now字符为d，所以应该将last字符和now字符拼接在一起，很明显，他们都是数字，所以当然要拼在一起而不是拆开，因此我们将cur = cur + now，还记得我们之前初始化的时候给cur赋值为1，所以现在cur就变为了15，不光如此，我们还要更新last字符的类型，将now字符的值赋值给last字符last = now
接下来继续循环，此时now字符变为+，last字符类型还是d，遇到加号，此时操作就不一样了，考虑一下，假如是一个156+28字符串，我们应该将156、+、28分别打印出来，所以如果遇到+字符，我们应该将当前的cur的值添加到一个“盒子”里，并且将now字符给cur，注意这里是用新的值将cur的值覆盖，而不是追加到cur后面
下面继续回来说例子，刚才说到遇到+字符，应该将cur的值保存到“盒子”里，然后将now字符赋值给cur，最后还要将last字符更新为now字符，因此，这部分代码就是这样
ans.add(cur);//ans就是上面提到的“盒子”
cur = now;
last = now;现在last字符为+，所以应该进入相应的函数，因为now字符现在为6，是d类型，所以应该将cur添加到“盒子”中，然后分别更新cur和last
ans.add(cur);
cur = now;
last = now继续往后遍历，last字符为6，now字符为e，他俩组合在一起就是6e，说明这是一个科学记数法，是满足算术表达式的规则的，因此cur应该在末尾追加now字符，也就是cur = cur + now，然后将last的值更新为now，也就是last = 'e'
接着继续遍历，last字符为'e'，now字符为9，他俩组合组合在一起就是e9，还是一个正确的算术表达式，因此cur应该在末尾追加now字符，然后将last的值更新为now
继续遍历，last字符为9，now字符为/，此时规则就和遇到+一样，应该将cur的值保存到“盒子”里，然后令cur = now，last = now
剩下的我就不多做解释了，总体主要是根据last和now字符表进行判断，如果满足要求，到底是将cur的值进行更新，还是进行追加这是比较重要的部分。
还有一点就是，如果出现科学记数法1e+9，总体思路还是不变的，但是如果遇到+，上面说到的思路是将前后进行拆分，这样就变成了1e、+、9，这明显不太对，我们需要的是1e+9这个整体，所以如果now字符是+或-，需要进行一次特判，当前位置是i，判断i-2位置是不是e，如果是e，就应该将他们全部连接起来，也就是追加到cur里面，如果不是，说明就是一个普通的加（减）法表达式，并不是科学记数法，那么就将他们拆开
代码
import java.util.*;
public class Main {
static String str, cur;
static char last, now;
static List<String> ans = new ArrayList<String>();
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
str = cin.next();
cur = "" + str.charAt(0);
if ("+".equals(cur) || "-".equals(cur) || "*".equals(cur) || "/".equals(cur) || "e".equals(cur)
|| ".".equals(cur)) {
System.out.println("Error");
return;
}
int LP = 0, RP = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(')
LP++;
if (str.charAt(i) == ')')
RP++;
}
if (LP != RP) {
System.out.println("Error");
return;
}
last = cur.charAt(0);
for (int i = 1; i < str.length(); i++) {
now = str.charAt(i);
if (Character.isDigit(last))
num(i);
else if (last == '+' || last == '-' || last == '*' || last == '/')
opreator(i);
else if (last == 'e')
opreator_e(i);
else if (last == '.')
opreator_Dian(i);
else if (last == '(')
opreator_Left(i);
else if (last == ')')
opreator_Right(i);
}
if (ans.contains("Error")) {
System.out.println("Error");
return;
}
ans.add(cur);
for (int i = 0; i < ans.size(); i++) {
System.out.println(ans.get(i));
}
cin.close();
}
static void opreator_Left(int i) {
if (Character.isDigit(now) || '(' == now) {
ans.add("(");
cur = "" + now;
last = str.charAt(i);
} else
ans.add("Error");
}
static void opreator_Right(int i) {
if ('+' == now || '-' == now || '*' == now || '/' == now || ')' == now) {
ans.add(")");
cur = "" + now;
last = now;
} else
ans.add("Error");
}
static void opreator_Dian(int i) {
if (Character.isDigit(now)) {
cur += now;
last = now;
} else
ans.add("Error");
}
static void opreator_e(int i) {
if (Character.isDigit(now) || '+' == now || '-' == now) {
cur += now;
last = now;
} else
ans.add("Error");
}
static void opreator(int i) {
if (('+' == last || '-' == last) && 'e' == str.charAt(i - 2)) {
cur += now;
last = now;
} else if (Character.isDigit(now) || '(' == now) {
ans.add("" + last);
cur = "" + now;
last = now;
} else
ans.add("Error");
}
static void num(int i) {
if (Character.isDigit(now) || 'e' == now || '.' == now) {
cur += now;
last = now;
} else if ('+' == now || '-' == now || '*' == now || '/' == now || ')' == now) {
ans.add(cur);
cur = "" + now;
last = now;
} else
ans.add("Error");
}
}下面是运行效果GIF，GIF比较大，可能会有点卡
