词法分析程序设计

实验目的

• 理解词法分析中的正规式和自动机
• 掌握词法分析程序的实现方法和技术

实验内容

各种词法单元对应的词法记号如下：

输入：源程序
输出：二元组（词法记号，属性值/其在符号表中的位置）构成的序列

样例输入：

x = 5;
if (x > 0) then
    x = 2 * x + 1 / 3;
else
    x = 2  / x;
#

样例输出：
(10,x)
(18,=)
(11,5)
(26,;)
(2,if)
(27,()
…

题目分析

整体算法流程可以用一张图来表示

我采取的方式是将目标源程序放在一个文件中，文本文件，word文件都可以，只要是文件，然后用输入流读取该文件，将里面的程序读入到List容器中保存用于后续处理。下面这段代码的作用就是给定文件路径path，然后对其进行读取

File filename = new File(path);
    InputStreamReader isr = new InputStreamReader(new FileInputStream(filename)); // 建立一个输入流对象reader
    BufferedReader br = new BufferedReader(isr);
    String line;
    do {
        line = br.readLine(); // 一次读入一行数据
        for (int i = 0; i < line.length(); i++)
            list.add(line.charAt(i));
        list.add('\n');
    } while (!line.equals("#"));
    isr.close();
    br.close();

然后将一些关键字的字符串与值保存在一个Map<K,V>中，java中Map有HashMap和TreeMap，这里只能用TreeMap，因为基本数据类型int、double、char...的值都是12，HashMap的特点是同一个Value对应的Key只能有一个，TreeMap可以有多个

map.put("for", 1);
map.put("if", 2);
map.put("then", 3);
map.put("else", 4);
map.put("while", 5);
map.put("byte", 12);
map.put("short", 12);
map.put("int", 12);
map.put("long", 12);
map.put("float", 12);
map.put("double", 12);
map.put("char", 12);
map.put("bool", 12);

源程序代码是一个实现求$\pi$的近似值的代码

double pi = 0.0,j = 1.0;
for(double i = 1.0;i < 1000000;i += 2) {
    pi += 1 / (i * j);
    j *= 0 - 1;
}
pi = pi * 4;
#

代码全部保存到容器中后变成下图所示的样子

通过程序一个一个字符进行判断，如果取出的字符是空格，则继续往后取直到不是空格位置，因为空格没有任何意义

首先判断当前字符是不是字母开头，字母开头无非就是关键字或自定义变量，如果是字母开头，就继续往后看，看是不是字母或者数字。如何区分关键字和自定义变量成了关键，例如，本来有一个关键字是if，但是这里用户自定义变量为ifx，区分的方法很简单。如果是关键字，那么关键字后面一定会跟一个空格或者回车，如果是用户自定义变量，那么后面一定会继续跟字母或数字。

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;
        }
    }
}

如果是数字开头，那一定是常量，直接一直往后把连续的数字都取出来

if (now >= 48 && now <= 57) { // 数字开头
    sum = new StringBuffer("");
    while ((now >= 48 && now <= 57) || now == 46) {
        sum.append(now);
        now = list.get(p++);
    }
}

如果上述情况都不是，那就只剩一些符号了，用switch case输出就行了，只不过有几个符号要特别判断一下，如果遇到这些特殊符号，需要往后多看一个字符，看看拼起来是否还是正确的符号，比方说<，<就有可能和后面的字符拼起来组成<>或<=，如果不能拼起来那就是<本身了

代码

import java.util.*;
import java.io.*;

public class Main {
    static Map<String, Integer> map = new TreeMap<String, Integer>();
    static List<Character> list = new ArrayList<Character>();
    static StringBuffer str;
    static char now;
    static int syn, p;
    static StringBuffer sum;
    
    // syn用来标记该字符串为什么值
    // p用来标记当前遍历到什么位置
    // sum用来代表其中的常量值

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        System.out.println("Please input file name:");
        String path = cin.next();
        init();
        try {
            read(path);
        } catch (IOException e) {
            e.printStackTrace();
        }
        do {
            str = new StringBuffer("");
            scanner();
            if (syn == 11) // 常量
                System.out.println("(" + syn + "," + sum + ")");
            else if (syn >= 0 && syn <= 12 || syn >= 13 && syn <= 37) { // 打印非常量
                String tmp = str.toString().trim();
                System.out.println("(" + syn + "," + tmp + ")");
            } else if (syn == -1) {
                System.out.println("ERROR");
                syn = 0;
            }
        } while (syn != 0);
        cin.close();
    }

    private static void scanner() {
        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) { // 数字开头
            sum = new StringBuffer("");
            while ((now >= 48 && now <= 57) || now == 46) {
                sum.append(now);
                now = list.get(p++);
            }
            p--;
            syn = 11;//常量
        } else {
            switch (now) {
            case '+': {
                str.replace(0, 0, "" + now);
                now = list.get(p++);
                if (now == '=') {
                    syn = 32;
                    str.append(now);
                    p++;
                }
                else if(now == '+') {
                    syn = 36;
                    str.append(now);
                    p++;
                } else {
                    syn = 13;
                    p--;
                }
                break;
            }
            case '-': {
                str.replace(0, 0, "" + now);
                now = list.get(p++);
                if (now == '=') {
                    syn = 33;
                    str.append(now);
                    p++;
                }
                else if (now == '-') { 
                    syn = 37;
                    str.append(now);
                    p++;
                } else {
                    syn = 14;
                    p--;
                }
                break;
            }
            case '*': {
                str.replace(0, 0, "" + now);
                now = list.get(p++);
                if (now == '=') {
                    syn = 34;
                    str.append(now);
                    p++;
                } else {
                    syn = 15;
                    p--;
                }
                break;
            }
            case '/': {
                str.replace(0, 0, "" + now);
                now = list.get(p++);
                if (now == '=') {
                    syn = 35;
                    str.append(now);
                    p++;
                } else {
                    syn = 16;
                    p--;
                }
                break;
            }
            case ';': {
                syn = 26;
                str.replace(0, 0, "" + now);
                break;
            }
            case '<': {
                str.append(now);
                now = list.get(p++);
                if (now == '=') {
                    syn = 22;
                    str.append(now);
                } else if (now == '>') {
                    syn = 23;
                    p++;
                } else {
                    syn = 20;
                    p--;
                }
                break;
            }
            case '>': {
                str.append(now);
                now = list.get(p++);
                if (now == '=') {
                    syn = 24;
                    str.append(now);
                    p++;
                } else {
                    syn = 21;
                    p--;
                }
                break;
            }
            case '\n': {
                syn = 100;
                break;
            }
            case '\t': {
                syn = 100;
                break;
            }
            case ':': {
                syn = 17;
                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 ',': {
                syn = 7;
                str.replace(0, 0, "" + now);
                break;
            }
            case '{': {
                syn = 8;
                str.replace(0, 0, "" + now);
                break;
            }
            case '}': {
                syn = 9;
                str.replace(0, 0, "" + now);
                break;
            }
            case '=': {
                str.append(now);
                now = list.get(p++);
                if (now == '=') {
                    syn = 25;
                    str.append(now);
                    p++;
                } else {
                    syn = 18;
                    p--;
                }
                break;
            }
            case '#': {
                syn = 0;
                str.replace(0, 0, "" + now);
                break;
            }
            default:
                syn = -1;
            }
        }
    }

    public static void read(String path) throws IOException {
        File filename = new File(path);
        InputStreamReader isr = new InputStreamReader(new FileInputStream(filename)); // 建立一个输入流对象reader
        BufferedReader br = new BufferedReader(isr);
        String line;
        do {
            line = br.readLine(); // 一次读入一行数据
            for (int i = 0; i < line.length(); i++)
                list.add(line.charAt(i));
            list.add('\n');
        } while (!line.equals("#"));
        isr.close();
        br.close();
    }

    static void init() {
        map.put("for", 1);
        map.put("if", 2);
        map.put("then", 3);
        map.put("else", 4);
        map.put("while", 5);
        map.put("byte", 12);
        map.put("short", 12);
        map.put("int", 12);
        map.put("long", 12);
        map.put("float", 12);
        map.put("double", 12);
        map.put("char", 12);
        map.put("bool", 12);
    }
}

下面是运行效果GIF，这个源程序实现的是求$\pi$的近似值

下面的GIF是题目代码的源程序输出效果