简单的词法分析程序

实验目的展开目录

理解词法分析在编译过程中的作用
初步了解和掌握词法分析程序的实现方法和技术

实验内容展开目录

编写程序，输入一串字符，判断该字符串是否为合法标识符或合法整型常量
无符号数的算术四则运算中的各类单词的识别

输入：由无符号数、+、－、*、/、(、) 构成的算术表达式
输出：对识别出的每一单词均单行输出

样例输入：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 比较大，可能会有点卡

Catalog