编译原理之 C 语言子集词法分析程序的构建 —— Java实现

发表于 | 分类于 | | 浏览量

原理方面就不赘述，本篇博客主要记录编译原理实验上机对于简单 C 语言子集的词法分析程序的 Java 实现。

C语言子集输入/输出以及要求

要求输入如下：

1
2
3
4
5
6
main()
{
    int a, b;
    a = 10;
    b = a + 20;
}

要求输出：

Lexical Analysis Output

同时要求：

  1. 识别保留字：if, int, for, while, do, return, break, continue，其单词种别码为 1
  2. 其余字符识别为标识符，单词种别码为 2
  3. 常数为无符号整型数，单词种别码为 3
  4. 运算符：+, -, *, /, =, >, <, >=, <=, !=，单词种别码为 4
  5. 分隔符：,, ;, {, }, (, )，单词种别码为 5

分析

分析程序流程

对于输入程序，我们不可能套用一套规则从而直接分析出结果。可以根据输入字符串构建缓冲区，然后从缓冲区逐个取出字符进行分析。

保留字、标识符

对于语言中的保留字，可以在程序中硬编码保存。当成功从输入串中构建一个 单词 的时候，进行比对来判断该 单词 是保留字还是标识符。

1
private static final String[] reverses = new String[]{"if", "int", "for", "while", "do", "return", "break", "continue"};

常数

常数与保留字、标识符的最大区别是：常数以数字开始，而保留字和标识符不能以数字起始。以此，我们可以明确区分出输入程序中的常数。

运算符与分隔符

运算符与分隔符的识别十分简单，利用 switch 即可。

实现

识别字的保存

保留字、标识符、常数、运算符、分隔符的单词种别码是固定的，如果我们在分析程序中直接写数值可能会影响可读性，可以用 enum 来表示：

1
2
3
4
5
6
7
8
9
private enum Code {
    Reverse(1), Identifier(2), Constant(3), Operator(4), Separator(5);

    private int value;

    Code(int value) {
        this.value = value;
    }
}

因为我们最终是要以上面图中的形式输出，所以需要另一种数据结构来表示识别出来的 单词种别码-单词 对：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private List<Kind> list = new ArrayList<>();

private static final class Kind {
    private Code code;
    private String value;

    Kind(Code code, String value) {
        this.code = code;
        this.value = value;
    }

    @Override
    public String toString() {
        return "(" + code.value + ", \"" + value + "\")";
    }
}

字符串分析器

我们可以使用 String 来保存输入串，并用一个类变量 index 来保存当前字符的位置，这样我们就可以利用 index 来进行逐字符分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int index = 0;
private String source;
private StringBuilder builder = new StringBuilder();

public LexicalAnalysis(String source) {
    this.source = source;
}

public void doAnalyze() {
    do {
        analyzer();
    } while (index < source.length());

    for (Kind kind : list) {
        System.out.println(kind);
    }
}

单字符分析器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
private void analyzer() {
    // 清空 builder
    builder.delete(0, builder.length());
    char ch = source.charAt(index++);

    // 剔除空格和换行符
    while (ch == ' ' || ch == '\n') {
        ch = source.charAt(index++);
    }

    if (Character.isLetter(ch)) {    // 以字符 [a-zA-Z] 开头，可能是关键字也可能是标识符
        // 提取出整个字符串 [a-zA-Z0-9]
        while (Character.isLetterOrDigit(ch)) {
            builder.append(ch);
            ch = source.charAt(index++);
        }
        // 最后一个字符不符合条件，所以 index 自减 1
        index--;
        String s = builder.toString();
        for (String reverse : reverses) {
            if (s.equals(reverse)) {
                list.add(new Kind(Code.Reverse, s));
                return;
            }
        }
        list.add(new Kind(Code.Identifier, s));
    } else if (Character.isDigit(ch)) {
        // 整数
        int sum = 0;
        while (Character.isDigit(ch)) {
            sum = sum * 10 + ch - '0';
            ch = source.charAt(index++);
        }
        // index 自减的原因同上
        index--;
        list.add(new Kind(Code.Constant, String.valueOf(sum)));
    } else {
        switch (ch) {
            case '+':
            case '-':
            case '*':
            case '/':
            case '>':
            case '<':
                list.add(new Kind(Code.Operator, String.valueOf(ch)));
                break;
            case '=':
                char prev = source.charAt(index - 2);
                if ("><!".contains(String.valueOf(prev))) {
                    // 如果 = 前边的字符是 > < !，则更新最后一个元素
                    Kind last = list.get(list.size() - 1);
                    last.value = String.valueOf(prev) + last.value;
                } else {
                    // 否则，新增
                    list.add(new Kind(Code.Operator, String.valueOf(ch)));
                }
                break;
            case ',':
            case ';':
            case '{':
            case '}':
            case '(':
            case ')':
                list.add(new Kind(Code.Separator, String.valueOf(ch)));
                break;
        }
    }
}

源代码

LexicalAnalysis.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class LexicalAnalysis {
    private static final String[] reverses = new String[]{"if", "int", "for", "while", "do", "return", "break", "continue"};

    private int index = 0;
    private String source;
    private StringBuilder builder = new StringBuilder();
    private List<Kind> list = new ArrayList<>();

    public LexicalAnalysis() {
        super();
    }

    public LexicalAnalysis(String source) {
        this.source = source;
    }

    public void doAnalyze() {
        do {
            analyzer();
        } while (index < source.length());

        for (Kind kind : list) {
            System.out.println(kind);
        }
    }

    private void analyzer() {
        // 清空 builder
        builder.delete(0, builder.length());
        char ch = source.charAt(index++);

        // 剔除空格和换行符
        while (ch == ' ' || ch == '\n') {
            ch = source.charAt(index++);
        }

        if (Character.isLetter(ch)) {    // 以字符 [a-zA-Z] 开头，可能是关键字也可能是标识符
            // 提取出整个字符串 [a-zA-Z0-9]
            while (Character.isLetterOrDigit(ch)) {
                builder.append(ch);
                ch = source.charAt(index++);
            }
            // 最后一个字符不符合条件，所以 index 自减 1
            index--;
            String s = builder.toString();
            for (String reverse : reverses) {
                if (s.equals(reverse)) {
                    list.add(new Kind(Code.Reverse, s));
                    return;
                }
            }
            list.add(new Kind(Code.Identifier, s));
        } else if (Character.isDigit(ch)) {
            // 整数
            int sum = 0;
            while (Character.isDigit(ch)) {
                sum = sum * 10 + ch - '0';
                ch = source.charAt(index++);
            }
            // index 自减的原因同上
            index--;
            list.add(new Kind(Code.Constant, String.valueOf(sum)));
        } else {
            switch (ch) {
                case '+':
                case '-':
                case '*':
                case '/':
                case '>':
                case '<':
                    list.add(new Kind(Code.Operator, String.valueOf(ch)));
                    break;
                case '=':
                    char prev = source.charAt(index - 2);
                    if ("><!".contains(String.valueOf(prev))) {
                        // 如果 = 前边的字符是 > < !，则更新最后一个元素
                        Kind last = list.get(list.size() - 1);
                        last.value = String.valueOf(prev) + last.value;
                    } else {
                        // 否则，新增
                        list.add(new Kind(Code.Operator, String.valueOf(ch)));
                    }
                    break;
                case ',':
                case ';':
                case '{':
                case '}':
                case '(':
                case ')':
                    list.add(new Kind(Code.Separator, String.valueOf(ch)));
                    break;
            }
        }
    }

    private enum Code {
        Reverse(1), Identifier(2), Constant(3), Operator(4), Separator(5);

        private int value;

        Code(int value) {
            this.value = value;
        }
    }

    private static final class Kind {
        private Code code;
        private String value;

        Kind(Code code, String value) {
            this.code = code;
            this.value = value;
        }

        @Override
        public String toString() {
            return "(" + code.value + ", \"" + value + "\")";
        }
    }

    public static void main(String[] args) throws Exception {
        StringBuilder sb = new StringBuilder();
        Scanner scanner = new Scanner(System.in);

        System.out.println("请输入C语言源程序的位置：");
        String line;

        try (BufferedReader reader = new BufferedReader(new FileReader(scanner.next()))) {
            while ((line = reader.readLine()) != null) {
                sb.append(line);
            }
        }

        LexicalAnalysis lexicalAnalysis = new LexicalAnalysis(sb.toString());

        lexicalAnalysis.doAnalyze();
    }
}

另一种实现方式

使用 index 控制当前字符的位置可能有些不够优雅，我们可以使用 java.nio.CharBuffer 来替代手动控制识别流程的方式。

LexicalAnalysisCharBuffer.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.nio.CharBuffer;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class LexicalAnalysisCharBuffer {
    private static final String[] reverses = new String[]{"if", "int", "for", "while", "do", "return", "break", "continue"};

    private CharBuffer charBuffer;
    private StringBuilder builder = new StringBuilder();
    private List<Kind> list = new ArrayList<>();

    public LexicalAnalysisCharBuffer() {
        super();
    }

    public LexicalAnalysisCharBuffer(String source) {
        charBuffer = CharBuffer.wrap(source.toCharArray());
    }

    public void doAnalyze() throws IOException {
        do {
            analyzer();
        } while (charBuffer.hasRemaining());

        for (Kind kind : list) {
            System.out.println(kind);
        }

    }

    private void analyzer() throws IOException {
        // 清空 builder
        builder.delete(0, builder.length());
        char aChar = charBuffer.get();

        // 剔除空格和换行符
        while (aChar == ' ' || aChar == '\n') {
            aChar = charBuffer.get();
        }

        if (Character.isLetter(aChar)) {    // 以字符 [a-zA-Z] 开头，可能是关键字也可能是标识符
            // 提取出整个字符串 [a-zA-Z0-9]
            while (Character.isLetterOrDigit(aChar)) {
                builder.append(aChar);
                aChar = charBuffer.get();
            }
            // 最后一个字符不符合条件，所以 index 自减 1
            charBuffer.position(charBuffer.position() - 1);
            String s = builder.toString();
            for (String reverse : reverses) {
                if (s.equals(reverse)) {
                    list.add(new Kind(Code.Reverse, s));
                    return;
                }
            }
            list.add(new Kind(Code.Identifier, s));
        } else if (Character.isDigit(aChar)) {
            // 整数
            int sum = 0;
            while (Character.isDigit(aChar)) {
                System.out.println("计算：" + aChar);
                sum = sum * 10 + (aChar - '0');
                System.out.println("sum: " + aChar);
                aChar = charBuffer.get();
            }
            // index 自减的原因同上
            charBuffer.position(charBuffer.position() - 1);
            list.add(new Kind(Code.Constant, String.valueOf(sum)));
        } else {
            switch (aChar) {
                case '+':
                case '-':
                case '*':
                case '/':
                case '>':
                case '<':
                    list.add(new Kind(Code.Operator, String.valueOf(aChar)));
                    break;
                case '=':
                    char prev = charBuffer.get(charBuffer.position() - 2);
                    if ("><!".contains(String.valueOf(prev))) {
                        // 如果 = 前边的字符是 > < !，则更新最后一个元素
                        Kind last = list.get(list.size() - 1);
                        last.value = String.valueOf(prev) + last.value;
                    } else {
                        // 否则，新增
                        list.add(new Kind(Code.Operator, String.valueOf(aChar)));
                    }
                    break;
                case ',':
                case ';':
                case '{':
                case '}':
                case '(':
                case ')':
                    list.add(new Kind(Code.Separator, String.valueOf(aChar)));
                    break;
            }
        }
    }

    private enum Code {
        Reverse(1), Identifier(2), Constant(3), Operator(4), Separator(5);

        private int value;

        Code(int value) {
            this.value = value;
        }
    }

    private static final class Kind {
        private Code code;
        private String value;

        Kind(Code code, String value) {
            this.code = code;
            this.value = value;
        }

        @Override
        public String toString() {
            return "(" + code.value + ", \"" + value + "\")";
        }
    }

    public static void main(String[] args) throws Exception {
        StringBuilder sb = new StringBuilder();
        Scanner scanner = new Scanner(System.in);

        System.out.println("请输入C语言源程序的位置：");
        String line;

        try (BufferedReader reader = new BufferedReader(new FileReader(scanner.next()))) {
            // 读取文件，构建 String
            while ((line = reader.readLine()) != null) {
                sb.append(line);
            }
        }

        LexicalAnalysisCharBuffer lexicalAnalysisCharBuffer = new LexicalAnalysisCharBuffer(sb.toString());

        lexicalAnalysisCharBuffer.doAnalyze();
    }
}

思路与上一种实现一样，不过使用这种方式我们无需操作 index。

-------------本文结束感谢阅读-------------
  • 本文标题：编译原理之 C 语言子集词法分析程序的构建 —— Java实现
  • 本文作者：xlui
  • 发布时间：2018年05月13日 - 11:05
  • 最后更新：2023年01月20日 - 01:01
  • 本文链接： https://xlui.me/t/compiling-principle-lexical-analysis/
  • 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明出处！