词法分析

标识符是一个大的集合。

记号的数据结构定义

enum kind {IF,LPAREN,ID,INTLIT,...}
struct token{
    enum kind k;
    char *lexeme;// 单词
}；
/*eg  if(x>5) 
===>>  
token{k=IF,lexeme=0};
token{k=LPAREN,lexeme=0}；
token{k=ID,lexeme="x"};
.....
*/

词法分析器的任务，字符流到记号流。

记号流是编译器内部定义的数据结构，编码所识别出的词法单元。

词法分析—手工构造法

相对复杂，容易出错。

词法分析器的生成器（自动化）：可快速原型、代码量少，但难控制细节。

转移图

token nextToken() {
    c = getChar();
    switch(c) {
        case '<':
            c= getChar();
            switch(c){
                case '=': return LE;
                case='>':return NE;
                default: rollback();return LT;    
            }
        case '=':return EQ;
        case '>': c= getChar();
            switch(c):{
                .....//和上面类似
            }
    }
}

标识符的转移图：

识别关键字

也可以弄关键字构成的哈希表，先统一按照关键符的转移图进行识别，进一步查表看是否是关键字。完美哈希

正则表达式

kleene闭包。

例子：标识符

c语言：以字母或下划线开头，后面跟多个或0个字母数字或下划线

（a|b|c|…..z|A|B|C|….|Z|–)(a|b|c|…..z|A|B|C|….|Z|–|0|1|…|9|)*

有限状态自动机

非确定有限状态自动机（NFA）

确定有限状态自动机（DFA)

NFA难以判断字符串是否可接受。需要进行搜索。需要将NFA转化为等价的DFA。

DFA的实现

带有边和节点的有向图。

边上面有信息

节点上有信息

正则表达式到NFA（Thompson算法）

RE—>NFA—>DFA—>词法分析器代码

对基本的RE直接构造

对复合的RE递归构造

NFA转化为DFA（子集构造法）

不动点算法：why能终止？

DFA最小化

Hopcroft算法

什么叫做能切分？

首先切分成非终结符和终结符两类

DFA的代码表示

转移表

哈希表

跳转表

1. 转移表：还要有词法分析驱动代码。

   

​ 最长匹配思想。

2. 跳转表:

跳转表不需要维护一个大的转移数组。