Redy词法分析--整数与浮点数的合并

返回文档首页

代码下载: git clone git://git.code.sf.net/p/redy/code redy-code

这一章内容有：

整数，长整数，浮点数状态机的合并

（1）整数与浮点数的状态机

在整个Redy词言里面有这么几种不同类型的单词：变量（包括关键字）、字符串、运算符、浮点数，整数，在这么几个里面，整数与浮点数状态机合并最难，而识别单词的状态机合并却很容易，所以这里单独的把整数与浮点数合并提取出来，把他们合并成一个大的状态机后，再用这个大的状态机与其它单词的状态机进行合并。

在合并之前，我们先看一看整数与浮点数的状态机：

整数状态机：

浮点数的状态机：



要合并两台状态机并不是一件容易的事情，整数的有10个状态，11种输入类型，浮点数有7个状态，5种输入类型，合并起来还是很吃力，不管怎么困难，我们都要合并。下面我们按照的们前面的讲的状态机合并算法的步骤一步一步来。

（２）输入类型分析：

a）对于整数状态机来说，输入１１种，前面我们整数识别这一章讲到过，分为：

1. 数字0　　　（D0）
2. 数字1　　　（D1）
3. 数字2到7　（D2_7)
4. 数字8到9 　（D8_9）
5. 字母a和A  （S_a)
6. 字母B和b　（S_b)
7. 字母c到f和C到F　（S_c_f)
8. 长整数标志符l与L  （S_l)
9. 八进制前缀o和O　（S_o)
10. 十六进制前缀x和X　（S_x)
11. 除以上字符以外的类型　（other)

其中：

1. D0_9 包含　D0 , D1  , D2_7 , D8_9
2. D0_7 包含　D0 , D1  , D2_7
3. D1_9 包含　D1 , D2_7 , D8_9
4. S_a_f 包含　S_a , S_b , S_c_f 

b）现在来看浮点数状态机，输入类型有５种，为分：

1. 点号.     （point）
2. 数字0到9　　　（digit）等同于(D0_9)
3. 字母E和e　　　（S_e)
4. 符号＋和-  　　（sign)
5. 除以上字符的所有字符　　（other）

c）对于两个输入类型进行合并得:

1. 数字0　　　（D0）
2. 数字1　　　（D1）
3. 数字2到7　（D2_7)
4. 数字8到9 　（D8_9）
5. 字母a和A  （S_a)
6. 字母B和b　（S_b)
7. 字母c到d和C到D　（S_c_d）
8. 字母E各e　　　（S_e）
9. 字母F和f　　　（S_f)
10. 长整数标志符l与L  （S_l)
11. 八进制前缀o和O　（S_o)
12. 十六进制前缀x和X　（S_x)
13. 点号.     （point）
14. 符号＋和-  　　（sign)
15. 除以上字符的所有字符　　（other）

其中：

1. D0_9 包含　D0 , D1  , D2_7 , D8_9
2. D0_7 包含　D0 , D1  , D2_7
3. D1_9 包含　D1 , D2_7 , D8_9
4. S_a_f 包含　S_a , S_b , S_c_d , S_e , S_f 

（3）建立状态转换表

在合并前，先简单复习下前面讲的状态机合并算法：

第一步：

　　先把两个自动机的开始状态组合起来，并创建与之等价的一个的新状态，我们把新状态命名为(NumberBegin)，然后标记NumberBegin。

第二步：

　　找出一个被标记过的状态，对该状态取消标记，然后进行状态转移分析，如果转移的结果是一个未出现过的组合状态，则创建一个与之等价的新状态并标记该新状态。其它的结果则线出一条转移线。

第三步：

　　重复第二步，直到没有所有的状态都没有被标记。

第四步：

　　把开始状态改为NumberBegin

根据上面的算法，我们先绘制出状态转换表，然后再根据我们的状态转换表，来画状态图

状态转换表为：

从上面的分析表可以看出，状态机合并后，会增加四个新的状态。现在我们根据我们分析表来绘制状态图，因为图状态过多，所以我并没有完全给出所有的状态，只是给出新增加的状态可能链接到原状机的状态。

（４）构造状态链

状态机在合并后，新增加了四个状态，这四个状态分别为NumberZero, NumberBegin,NumberOct, Number，我们为这四个状态构造状态链，把两个状态机链接在一起，但是在构造之前，我们需要做一件事情是输入类型优化，如果大家仔细观察我们的状态分析表可以发现，在几个输入类型下面，这几个状态并不会发生状态转移，这就说明，这几个输入类型都可以被归纳到类型Other中去。

优化后输入类型有：

1. 数字0　　　（D_0）
2. 数字1_7　　（D1_7)
3. 数字0到9　　　(D8_9)
4. 字符b与B　　　(S_b)
5. 字符e与E　　　(S_e)
6. 字符l与L　　　　(S_l)
7. 字符o与O　　　(S_o)
8. 字符x 与x　　　(s_x)
9. 点号　　　　　(point)
10. 除以上以外的字符　　(ohter)

其中

1. D0_7包含D0和D1_7
2. D1_9包含D1_7和D8_9
3. D0_9包含D0，D1_7，D8_9

输入类型经过合并以后，从以前的１５变成了现在的１０个，为我们编写状态链程序节省了不少的时间。

现在我们开始编写状态链程序：

首先，我们先对这四个状态进行申明，以便后面引用：

/*number parts*/
/*number merge float and integer*/
extern struct state nu_begin;
extern struct state nu_zero;
extern struct state nu_oct;
extern struct state nu_number;

第二步，创建一个一维数组，用来映射输入类型。

enum NUMBER_INPUT_TYPES
{
    NU_OTHER=0,
    NU_D0,
    NU_D1_7,
    NU_D8_9,
    NU_S_B,
    NU_S_E,
    NU_S_L,
    NU_S_O,
    NU_S_X,
    NU_POINT,
    NU_INPUT_NUM,
};
char number_input_map[ASCII_NUM]=
{
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,9,0,1,2,2,2,2,2,2,2,3,3,0,0,0,0,0,0,
    0,0,4,0,0,5,0,0,0,0,0,0,6,0,0,7,0,0,0,0,0,0,0,0,8,0,0,0,0,0,0,0,
    0,0,4,0,0,5,0,0,0,0,0,0,6,0,0,7,0,0,0,0,0,0,0,0,8,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
};

第三步，为每一个状态编写状态链

a）状态NumberBegin：

1. 在输入类型D0下转移到状态NumberZero
2. 在输入类型point下转移到状态Float::FractionBegin
3. 在输入类型D1_9下转移到状态Number

/*NumberBegin*/
struct state* nu_begin_targets[]=
{
    &lex_state_err,        /*NU_OTHER*/
    &nu_zero,            /*NU_D0*/
    &nu_number,            /*NU_D1_7*/
    &nu_number,            /*NU_D8_9*/
    &lex_state_err,        /*NU_S_B*/
    &lex_state_err,        /*NU_S_E*/
    &lex_state_err,        /*NU_S_L*/
    &lex_state_err,        /*NU_S_O*/
    &lex_state_err,        /*NU_S_X*/
    &ft_frac_begin,        /*NU_POINT*/
};
struct state nu_begin=
{
    "nu_begin",
    TOKEN_UNKOWN,
    NU_INPUT_NUM,
    number_input_map,
    0,
    nu_begin_targets,
    0,
};

b）状态NumberZero：

1. 在输入类型S_b下转移到状态Integer::IntegerBegin
2. 在输入类型S_o下转移到状态Integer::OctBegin
3. 在输入类型S_x下转移到状态Integer::Hexbegin
4. 在输入类型S_l下转移到状态integer::long
5. 在输入类型D8_9下转移到状态Float::IntPart
6. 在输入类型D0_7下转移到状态NumberOct
7. 在输入类型S_e下转移到状态Float::ExponentBegin
8. 在输入类型point下转移到状态Float::FractionBegin。

/*NumberZero*/
struct state* nu_zero_targets[]=
{
    &lex_state_err,        /*NU_OTHER*/
    &nu_oct,            /*NU_D0*/
    &nu_oct,            /*NU_D1_7*/
    &ft_int_part,        /*NU_D8_9*/
    &ist_bin_begin,        /*NU_S_B*/
    &ft_exp_begin,        /*NU_S_E*/
    &ist_long,            /*NU_S_L*/
    &ist_oct_begin,        /*NU_S_O*/
    &ist_hex_begin,        /*NU_S_X*/
    &ft_frac_begin,        /*NU_POINT*/
};
struct state nu_zero=
{
    "nu_zero(demical)",
    TOKEN_DEC,
    NU_INPUT_NUM,
    number_input_map,
    0,
    nu_zero_targets,
    1,
};

c）状态Number：

1. 在输入类型point下，转移到状态Float::FractionBegin
2. 在输入类型S_e下转移到状态Float::ExponentBegin
3. 在输入类型S_l下转移到状态integer::long
4. 在输入类型D0_9下转移到自身。

/*NUMBER*/
struct  state* nu_number_targtes[]=
{
    &lex_state_err,        /*NU_OTHER*/
    &nu_number,            /*NU_D0*/
    &nu_number,            /*NU_D1_7*/
    &nu_number,            /*NU_D8_9*/
    &lex_state_err,        /*NU_S_B*/
    &ft_exp_begin,        /*NU_S_E*/
    &ist_long,            /*NU_S_L*/
    &lex_state_err,        /*NU_S_O*/
    &lex_state_err,        /*NU_S_X*/
    &ft_frac_begin,        /*NU_POINT*/
};
struct state nu_number=
{
    "nu_number(demical)",
    TOKEN_DEC,
    NU_INPUT_NUM,
    number_input_map,
    0,
    nu_number_targtes,
    1,
};

e）状态NumberOct：

1. 在输入类型D0_7下转移到自身
2. 在输入类型S_e下转移到状态Float::ExponentBegin
3. 在输入类型S_l下转移到状态integer::long
4. 在输入类型D8_9下转移到状态Float::intPart.

/*NumberOct    */
struct state* nu_oct_targtes[]=
{
    &lex_state_err,        /*NU_OTHER*/
    &nu_oct,            /*NU_D0*/
    &nu_oct,            /*NU_D1_7*/
    &ft_int_part,        /*NU_D8_9*/
    &lex_state_err,        /*NU_S_B*/
    &ft_exp_begin,        /*NU_S_E*/
    &ist_long,            /*NU_S_L*/
    &lex_state_err,        /*NU_S_O*/
    &lex_state_err,        /*NU_S_X*/
    &ft_frac_begin,        /*NU_POINT*/
};
struct state nu_oct=
{
    "nu_oct(oct)",
    TOKEN_OCT,
    NU_INPUT_NUM,
    number_input_map,
    0,
    nu_oct_targtes,
    1,
};

到现在为些，我们已经完成了浮点数与整数状态机的合并，大家可以在下载下来的文件夹下面的tutorial/lexical/sl_number中找到所有合并后的代码，sl_integer是整数状态机的状态链，sl_float是浮点数状态机的状态链，sl_number为合并后新增四个状态的状态链程序。

（5）运行结果

返回文档首页