（编译原理）java实现词法分析器

1、闲话

最近在学编译原理，需要用语言实现一个词法分析器，其实挺简单的，主要涉及一些语言字符串操作处理，如果会正则表达式的话，感觉实现这个会很简单，但是我并不会啊，然后自己用java实现了，也算是加强了对java的一些字符操作方法的使用。

实现这个分析器，算法上基本上没什么难度，但是其中涉及的一些逻辑上的思考，说白了就是这么多种情况，有写情况还有交叉部分，你怎么让自己不绕进去，并且用代码实现自己的对这个问题思路。

那么闲话就说到这，具体我怎么想的，怎么处理的看下面

2、问题要求

一、 实验目的

设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。

二、 实验内容

2.1 待分析的简单词法

（1）关键字：所有的关键字都是小写
begin if then while do end

（2）运算符和界符

:= + - * / < <= <> > >= = ; ( ) #

（3）其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义：

ID = letter (letter | digit)*
NUM = digit digit*

（4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、NUM、运算符、界符和关键字，词法分析阶段通常被忽略。

2.2 各种单词符号对应的种别码：

2.3 词法分析程序的功能：

输入：所给文法的源程序字符串。

输出：二元组（syn,token或num）构成的序列。

其中：syn为单词种别码；
      token为存放的单词自身字符串；
      num为整型常数。

例如：对源程序begin x:=9; if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列：

(1,begin) (10,x) (18,:=) (11,9) (26,;) (2,if)……
1
2
3
4
5
6
7
8
9
10
11
12

3、思维导图

先上思维导图， 根据思维导图看看我是怎么想这个问题的。

4、代码实现

关键代码：

    /**
     * 将按间隔符分好的list进行判断，判断是否是合法的子串
     * @param list
     * @return
     */
    @SuppressWarnings("rawtypes")
    public List<Map> GetStringAndSortNum(String[] list) {
        char firstChar;//用于记录第一个首字符
        String keyword="",sortNum="";//需要输出返回的关键字，种别码
        String cType,word;//第一个首字符的类型

        //mlist用于返回整个List判断完成后的含有的字符和种别码
        List<Map> mList=new ArrayList<Map>();

        for(int i=0;i<list.length;i++){
            Map<String,String>map=new HashMap<String,String>();//m用于保存最后返回的已经判别成功的字和种别码
            //word代表需要进行处理判断的字
            word=list[i];
            //判断word是不是空的串，因为有可能根据空格分割的串中有空的换行符或者空串，不进行处理
            if(word==""||word==null||word.trim()=="")continue;

            firstChar=word.charAt(0);
            //获取这个字符的类型
            cType=GetCharType(firstChar);

            if(cType=="letter"){
                if(firstChar=='w'||firstChar=='i'||firstChar=='b'||firstChar=='d'||firstChar=='e'||firstChar=='t'){
                    //获得keyword词
                    Map<String,String>m=new HashMap<String,String>();//m用于保存最后返回的已经判别成功的字和种别码
                    m=GetKeyWord(word);
                    //取出m的值，如果是关键字
                    if(m!=null){
                        keyword=m.get("keyword");
                        sortNum=m.get("sortNum");
                    }
                    //不是关键字，但是包含关键字的前一个字符串
                    else{
                        if(IsID(word)){
                            keyword=word;
                            sortNum=g.getSortNum("ID")+"";
                        }
                        else{
                            System.out.println("这个"+word+"不是合法的ID字符，所在的位置在：第"+(i+1)+"个单词");
                        }
                    }
                }
                else{//首字母为字符，但是需要进一步判断是不是合法的ID
                    if(IsID(word)){
                        keyword=word;
                        sortNum=g.getSortNum("ID")+"";
                    }
                    else{
                        System.out.println("这个"+word+"不是合法的ID字符，所在的位置在：第"+(i+1)+"个单词");
                    }
                }
            }
            if(cType=="digit"){
                if(IsNum(word)){
                    keyword=word;
                    sortNum=g.getSortNum("NUM")+"";
                }
                else{
                    System.out.println("这个"+word+"不是合法的NUM字符，所在的位置在：第"+(i+1)+"个单词");
                }
            }
            if(cType=="opts"){
                //获取这个word的长度，如果是一个进行单运算符的判断，如果是2进行多运算符的判断
                int len=word.length();
                if(len==1){
                    if(IsSingleOpt(word)){
                        keyword=word;
                        sortNum=g.getSortNum(word)+"";
                    }
                    else if(IsEndOpt(word)){
                        keyword=word;
                        sortNum=g.getSortNum(word)+"";
                    }
                    else{
                        System.out.println("这个"+word+"不是合法的NUM字符，所在的位置在：第"+(i+1)+"个单词");
                    }
                }
                else if(len==2){
                    if(IsDoubleOpt(word)){
                        keyword=word;
                        sortNum=g.getSortNum(word)+"";
                    }
                    else{
                        System.out.println("这个"+word+"不是合法的NUM字符，所在的位置在：第"+(i+1)+"个单词");
                    }
                }
                else{
                    System.out.println("这个"+word+"不是合法的NUM字符，所在的位置在：第"+(i+1)+"个单词");
                }
            }
            if(keyword.equals("")||sortNum.equals("")||keyword==""||sortNum=="")
                continue;
            else{
                map.put("keyword", keyword);
                map.put("sortNum", sortNum);
                mList.add(map); 
                keyword="";
                sortNum="";
            }
        }
        return mList;
    }
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

代码实现后的运行效果：

测试用的文件：

begin x := 9 ; if x > 9 then x := 2 * x + 1 / 3
x = 3 ;
begin
$y := 2
if x == $y :
y = qqwe221 ;
1
2
3
4
5
6
7

其实看起来很复杂的一个词法分析器，当真正借组思维导图或者其他的流程图表示出来的时候，实现思路在脑子里就会很清晰，自己下一步要干嘛，怎么实现，当自己想到这些的时候，可以用自己喜欢的形式记录下来，这样实现起来就只需要用代码把自己的思路复现即可。

养成一种编程的习惯有时候比掌握一门语言对自己更有利。

本词法分析器的源码和测试文件均放在github上，需要的请自行进行查看。
https://github.com/Ashplumage/Compile-principle