Chinaunix首页 | 论坛 | 博客

NosicLin的ChinaUnix博客nosic.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

NosicLin

  • 博客访问： 326201
  • 博文数量： 32
  • 博客积分： 424
  • 博客等级： 准尉
  • 技术积分： 465
  • 用 户 组： 普通用户
  • 注册时间： 2012-03-02 10:23
文章分类

全部博文（32）

文章存档

2012年（32）

我的朋友
最近访客
推荐博文
相关博文
Redy词法分析--整数与浮点数的合并

分类： Python/Ruby

2012-03-02 16:47:12



代码下载: 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
输入类型经过合并以后，从以前的１５变成了现在的１０个，为我们编写状态链程序节省了不少的时间。

现在我们开始编写状态链程序：
首先，我们先对这四个状态进行申明，以便后面引用：
  1. /*number parts*/
  2. /*number merge float and integer*/
  3. extern struct state nu_begin;
  4. extern struct state nu_zero;
  5. extern struct state nu_oct;
  6. extern struct state nu_number;
第二步，创建一个一维数组，用来映射输入类型。
  1. enum NUMBER_INPUT_TYPES
  2. {
  3.     NU_OTHER=0,
  4.     NU_D0,
  5.     NU_D1_7,
  6.     NU_D8_9,
  7.     NU_S_B,
  8.     NU_S_E,
  9.     NU_S_L,
  10.     NU_S_O,
  11.     NU_S_X,
  12.     NU_POINT,
  13.     NU_INPUT_NUM,
  14. };
  15. char number_input_map[ASCII_NUM]=
  16. {
  17.     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,
  18.     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,
  19.     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,
  20.     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,
  21.     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,
  22.     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,
  23.     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,
  24.     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,
  25. };
第三步，为每一个状态编写状态链

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

  1. /*NumberBegin*/
  2. struct state* nu_begin_targets[]=
  3. {
  4.     &lex_state_err,        /*NU_OTHER*/
  5.     &nu_zero,            /*NU_D0*/
  6.     &nu_number,            /*NU_D1_7*/
  7.     &nu_number,            /*NU_D8_9*/
  8.     &lex_state_err,        /*NU_S_B*/
  9.     &lex_state_err,        /*NU_S_E*/
  10.     &lex_state_err,        /*NU_S_L*/
  11.     &lex_state_err,        /*NU_S_O*/
  12.     &lex_state_err,        /*NU_S_X*/
  13.     &ft_frac_begin,        /*NU_POINT*/
  14. };
  15. struct state nu_begin=
  16. {
  17.     "nu_begin",
  18.     TOKEN_UNKOWN,
  19.     NU_INPUT_NUM,
  20.     number_input_map,
  21.     0,
  22.     nu_begin_targets,
  23.     0,
  24. };
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。
  1. /*NumberZero*/
  2. struct state* nu_zero_targets[]=
  3. {
  4.     &lex_state_err,        /*NU_OTHER*/
  5.     &nu_oct,            /*NU_D0*/
  6.     &nu_oct,            /*NU_D1_7*/
  7.     &ft_int_part,        /*NU_D8_9*/
  8.     &ist_bin_begin,        /*NU_S_B*/
  9.     &ft_exp_begin,        /*NU_S_E*/
  10.     &ist_long,            /*NU_S_L*/
  11.     &ist_oct_begin,        /*NU_S_O*/
  12.     &ist_hex_begin,        /*NU_S_X*/
  13.     &ft_frac_begin,        /*NU_POINT*/
  14. };
  15. struct state nu_zero=
  16. {
  17.     "nu_zero(demical)",
  18.     TOKEN_DEC,
  19.     NU_INPUT_NUM,
  20.     number_input_map,
  21.     0,
  22.     nu_zero_targets,
  23.     1,
  24. };
c）状态Number：
  1. 在输入类型point下，转移到状态Float::FractionBegin
  2. 在输入类型S_e下转移到状态Float::ExponentBegin
  3. 在输入类型S_l下转移到状态integer::long
  4. 在输入类型D0_9下转移到自身。
  1. /*NUMBER*/
  2. struct state* nu_number_targtes[]=
  3. {
  4.     &lex_state_err,        /*NU_OTHER*/
  5.     &nu_number,            /*NU_D0*/
  6.     &nu_number,            /*NU_D1_7*/
  7.     &nu_number,            /*NU_D8_9*/
  8.     &lex_state_err,        /*NU_S_B*/
  9.     &ft_exp_begin,        /*NU_S_E*/
  10.     &ist_long,            /*NU_S_L*/
  11.     &lex_state_err,        /*NU_S_O*/
  12.     &lex_state_err,        /*NU_S_X*/
  13.     &ft_frac_begin,        /*NU_POINT*/
  14. };
  15. struct state nu_number=
  16. {
  17.     "nu_number(demical)",
  18.     TOKEN_DEC,
  19.     NU_INPUT_NUM,
  20.     number_input_map,
  21.     0,
  22.     nu_number_targtes,
  23.     1,
  24. };
e）状态NumberOct：
  1. 在输入类型D0_7下转移到自身
  2. 在输入类型S_e下转移到状态Float::ExponentBegin
  3. 在输入类型S_l下转移到状态integer::long
  4. 在输入类型D8_9下转移到状态Float::intPart.
  1. /*NumberOct    */
  2. struct state* nu_oct_targtes[]=
  3. {
  4.     &lex_state_err,        /*NU_OTHER*/
  5.     &nu_oct,            /*NU_D0*/
  6.     &nu_oct,            /*NU_D1_7*/
  7.     &ft_int_part,        /*NU_D8_9*/
  8.     &lex_state_err,        /*NU_S_B*/
  9.     &ft_exp_begin,        /*NU_S_E*/
  10.     &ist_long,            /*NU_S_L*/
  11.     &lex_state_err,        /*NU_S_O*/
  12.     &lex_state_err,        /*NU_S_X*/
  13.     &ft_frac_begin,        /*NU_POINT*/
  14. };
  15. struct state nu_oct=
  16. {
  17.     "nu_oct(oct)",
  18.     TOKEN_OCT,
  19.     NU_INPUT_NUM,
  20.     number_input_map,
  21.     0,
  22.     nu_oct_targtes,
  23.     1,
  24. };
到现在为些，我们已经完成了浮点数与整数状态机的合并，大家可以在下载下来的文件夹下面的tutorial/lexical/sl_number中找到所有合并后的代码，sl_integer是整数状态机的状态链，sl_float是浮点数状态机的状态链，sl_number为合并后新增四个状态的状态链程序。

（5）运行结果



返回文档首页





阅读(2543) | 评论(1) | 转发(1) |
0

上一篇：Redy词法分析--状态机合并算法

下一篇：Redy词法分析--关键字的识别

给主人留下些什么吧！~~

重返人生2012-03-03 00:25:08

不错的文章，加油↖(^ω^)↗

回复 | 举报
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6