词法分析是编译的第一阶段。主要任务是读入源程序的输入字符，将他们组成词素，生成并输出一个词法单元序列，每个词法对应于一个词素。这个词法单元序列被输出到语法分析器进行语法分析。词法分析器通常还要和符号表进行交互。

​ ——《编译原理》（龙书）

词法分析设计

其实词法分析也就是对字符串的匹配问题。在实验中，我采用了以枚举类容纳正则表达式进行匹配的方式，涉及到的难点主要有：注释的处理、各类符号正则匹配。

整体架构

本次项目没有对编码前的设计进行修改。
目前项目架构如下：

1
2
3
4
5
6
7
8
9
.
├── Compiler.java
├── front
	└── token
		├── Tokenizer.java
    	├── TokenList.java
    	└── Token.java
└── utils
    └── Input.java

在Input类中，首先将文件按行存储到ArrayList<String> lines中，使用getFollowingChars函数实现从当前字符预读取n个字符，使用goForward函数实现每次前进n个字符，使用match函数进行正则匹配，使用skipBlacks函数跳过不可见字符。

在Tokenizer类中，通过initToken方法实现了程序主要功能。

注释处理

主要有两种形式的注释：

  • //：只要出现，那么就跳过当前行之后的所有字符。
  • /* ... */：出现/*后，先向前2个字符（此刻对应字符为/），不断逐字符匹配，直到匹配到*/为止，并忽略期间的所有字符。
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
public class Tokenizer {
    // source中存储了所有的lines
    public static void initToken(Input source){
        TokenList tokens = new TokenList();
        while(!source.reachEndFile()){
            source.skipBlacks();
            // 按行注释
            if("//".equals((source.getFollowingChars(2)))){
                source.nextLine();
            }
            // 成段注释
            else if("/*".equals((source.getFollowingChars(2)))){
                source.goForward(2);
                while(!"*/".equals(source.getFollowingChars(2))&&!source.reachEndFile()){
                    source.goForward(1);
                }
                if("*/".equals((source.getFollowingChars(2)))){
                    source.goForward(2);
                    continue;
                }
            }
            else{
                for(Token.Type type: Token.Type.values()){
                    String token = source.match(type.getPattern());
                    if(Objects.nonNull(token)){
                        Token temp = new Token(type, source.getCurrentLineNumber(), token);
                        tokens.append(temp);
                        source.goForward(token.length());
                        break;
                    }
                }
            }
        }
        tokens.print();
    }

各类符号正则匹配

对于各类符号来说，难点如下：

  • 注意顺序

    • int、const等保留字要在Ident前面
    • ==要在=前面。

  • 注意转义（个人建议是不确定的都转了就完事了）

    • OR("\\|\\|"),
    • MULT("\\*"),
    • PLUS("\\+"),
    • LPARENT("\\("),
    • LBRACK("\\["),
    • LBRACE("\\{"),
  • 注意分词
    • int、const等保留字匹配时后面需要加上\\b。
    • 也可以使用前瞻断言?!\\w。

Type枚举类如下：

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
enum Type{
        //需要进行分词
        MAINTK("main",true),
        CONSTTK("const",true),
        INTTK("int",true),
        BREAKTK("break",true),
        CONTINUETK("continue",true),
        IFTK("if",true),
        ELSETK("else",true),
        WHILETK("while",true),
        GETINTTK("getint",true),
        PRINTFTK("printf",true),
        RETURNTK("return",true),
        VOIDTK("void",true),
        // 三个较为特殊的正则
        IDENFR("[_A-Za-z][_A-Za-z0-9]*"),
        INTCON("[0-9]+"),
        STRCON("\\\"[^\\\"]*\\\""),
        // 涉及到 = 的双符号放在前面
        LEQ("<="),
        GEQ(">="),
        EQL("=="),
        NEQ("!="),
        // 其他正常正则
        NOT("!"),
        AND("&&"),
        OR("\\|\\|"),
        PLUS("\\+"),
        MINU("-"),
        MULT("\\*"),
        DIV("/"),
        MOD("%"),
        LSS("<"),
        GRE(">"),
        ASSIGN("="),
        SEMICN(";"),
        COMMA(","),
        LPARENT("\\("),
        RPARENT("\\)"),
        LBRACK("\\["),
        RBRACK("\\]"),
        LBRACE("\\{"),
        RBRACE("\\}");
        private Pattern pattern;
        Type(String name){
            this.pattern = Pattern.compile("^"+name);
        }
        Type(String name,boolean br){
            if(br==true){
                this.pattern = Pattern.compile("^"+name+"\\b");
            }
        }
        public Pattern getPattern() {
            return pattern;
        }
    }