[词法分析]再见，正则表达式

对于用过Yacc、Javacc的人来说这个标题可能是不可思议的，难道不是先从词法分析入手？
其实我只是试图换个角度，用有穷自动机而不是正则式来实现词法分析。两者虽然在数学上是等价的，但是实现有很大不同。如果你跟我一样不太喜欢自己的实现被一大堆if-else或者switch-case弄得乱乱的，也许DFA是个不错的解决方案。

数据结构

/* const.h */
typedef enum {
    END, IDENT, ELSE, IF, WHILE, READ, WRITE, BREAK,
    INTEGER_TYPE, REAL_TYPE, INTEGER, REAL,
    PLUS, MINUS, MULTIPLY, DIVIDE, ASSIGN, LT, LE, EQ, NE, GT, GE,
    AND, OR, NOT,
    COMMA, EOS, LPARENT, RPARENT, LBRACKET, RBRACKET, LBRACE, RBRACE,
    SKIP, DENY
} AcceptType;

/* datastruct.h */
struct State {
    AcceptType type;
    struct State* nextState[1 << 8];
};

     上面那个枚举类型表征各种词法分析符号，如END表示文件结束，相当于读入了EOF，具体最后再列个表，现在将重要的。
    State结构体表示是DFA状态，每个状态有一个接受态，对应一个AcceptType；后面那个面目狰狞的数组，就是平时画在纸上的DFA状态到处指的箭头。比如有一个状态是这样的：

        /-\ 'x' /-\
        |a|---->|b|
        \-/     \-/
    那么对应的，写一个这样的语句来搞之：
    a.nextState['x'] = &b;
    如果是这样的：
        /------\
        |标识符 |-\ 数字
        \------/  | 字母
           ^      | 下划线
            \-----/
    那么用循环可以搞定之，伪代码如下：
int i;

for(i = 'a'; i <= 'z'; ++i) {

    标识符.nextState[i] = &标识符;

}

for(i = 'A'; i <= 'Z'; ++i) {

    标识符.nextState[i] = &标识符;

}

for(i = '0'; i <= '9'; ++i) {

    标识符.nextState[i] = &标识符;

}

 

这样一来自动机的构造与分析过程就完全分开了，在词法分析的时候就不需要把大量的判断、分支和状态转移堆积在一坨来写。当然，前提是状态们的初始化都正确完成。词法分析过程中会逐字节地读入字符（注意编码……），因此nextState数组的大小为(1 << 8)。具体下一篇文章再来讲。

 

附AcceptType枚举类型中各符号的意义：

END: 结束符

IDENT: 标识符

IF ELSE WHILE READ WRITE BREAK: 变成小写后，就是对应的关键字类型

INTEGER_TYPE REAL_TYPE: 对应于数据声明的类型关键字和int, real

INTEGER REAL: 整型常数和实型常数

PLUS MINUS MULTIPLY DIVIDE ASSIGN: 运算符号，依次是+-*/=

LT LE EQ NE GT GE: 比较符号，依次是小于<、小于等于<=、等于==、不等于!=、大于>、大于等于>=

AND OR NOT: 逻辑运算符，依次是与&&、或||、非!

COMMA: 逗号

EOS: 语句结尾，分号

LPARENT RPARENT LBRACKET RBRACKET LBRACE RBRACE: 各种括号，依次是()[]{}

SKIP: 可跳过的空格符，以及注释

DENY: 拒绝，接受类型为这个的都是非接受状态

评论

3 楼 lwwin 2009-01-13  

我只想到了函数^^HOHO
考试加油^^～

2 楼 NeuronR 2009-01-12  

lwwin 写道

我记得你好像说不支持逗号表达式了呀……COMMA做什么用呢？

int i, j, k;

1 楼 lwwin 2009-01-12  

我记得你好像说不支持逗号表达式了呀……COMMA做什么用呢？