Lexical Analysis

**Reference: **<Engineering A Compiler>. Chapter 2
**Keywords: ** Finite Automaton, Regular Expression

---

词法分析，就是从一串字符中识别出符合一定词法规则的字符串序列 - 单词（token），比如，从"how are you"中识别出单词"how", "are", "you"，这些单词的词法规则是以空格分割。类似地，C语言中的标志符的词法规则是：由字母（A-Z,a-z）、数字（0-9）、下划线“_”组成，并且首字符不能是数字，但可以是字母或者下划线（当然还有一些其它的限定）。那么词法分析器的职责就是从一串字符中识别出符合该条规则的连续子串。一般词法规则由正则表达式（Regular Expression）描述，通过一系列变换生成对应的有限状态机（Finite Automaton），我们通过对于有限状态机的模拟便可以实现一个记法分析器。

The cycle of constructions

---

下面通过一个例子简单地介绍：如何从由正则表达式描述的词法规则出发，生成一个最小有限状态机，进而实现一个词法分析器。
词法规则：ab*
目的：实现一个函数判定输入字符串是否符合该条记法规则。

变换过程：

根据最终的DFA可以写出如下代码：

class TestLexicalPred
{
    enum CharType { CT_a, CT_b, CT_other };

public:
    TestLexicalPred() { }

    CharType getCharType(char ch)
    {
        if (ch == 'a')
            return CT_a;
        else if (ch == 'b')
            return CT_b;
        return CT_other;
    }

    bool test(string text)
    {
        enum State { s0, s1, se };
        State transitionTable[][3] = 
        {
            { s1, se, se },
            { se, s1, se },
            { se, se, se }
        };

        State state = s0;
        for (int i = 0; i < text.length(); ++i)
        {
            CharType ct = getCharType(text[i]);
            state = transitionTable[state][ct];
            if (state == se)
                break;
        }
        return state == s1;
    }
};

int main()
{
    TestLexicalPred t;
    cout << t.test("a") << endl; // true
    cout << t.test("ab") << endl; // true
    cout << t.test("abbbbbb") << endl; // true
    cout << t.test("bab") << endl; // false
    cout << t.test("aaa") << endl; // false
    cout << t.test("aba") << endl; // false

    return 0;
}

---

首先，将正则表达式（RE）转换成非确定有限状态机（NFA）（Thompson’s Construction），下面是转换规则：

TrivialNFAs for Regular Expression Operators

其次，将NFA转化为DFA（The Subset Construction）

The Subset Construction

最后，简化DFA（Hopcroft’s Algorithm）。

Hopcroft’s Algorithm

---

Create time: 2016-11-10