Redy词法分析--综合识别

近回文档首页

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

这一章的内容有：

这一章大家会看到一个完整的大的状态机，用于识别Redy语言中所有的单词。

（一）简介

在前面基本上讲完了Redy中大部份单词，其中有变量，字符串，注释，整数，长整数，浮点数，运算符。但还有一小部份单词在前面还没有提到过，分别为：

1. 关键字（如if，else，while，for等）
2. 语句分隔符（符号‘；‘和换行符），在Redy中每一条语句占用一行（组合语句除外），如果相把多条语句写在一行的，那么就需要用‘；’来分开。
3. 白空格（由多个空格或制表符组成），白空格对于语言来说没有多在用处，当识别到白空格时就把它抛弃。

变量状态机在识别时，会一同识别到关键字，所以最终到底为变量还是关键字，需要在判断一次。

对于分隔符和白空格，这里就不细说，他们的识别都非常的简单，我只是给出他们的状态机

（二）综合识别

（１）简介

在前面文章中讲过整数，长整数，浮点数的合并，其实这已经完成了七成的工作了，后面的几个状态机的合并要简单得多，为了表述方便，我们把整数，长整数，浮点数都称为数。下一步的目标是得到一个大的状态机。

（２）状态机合并

现在总共有字符串，变量，数，运算符，注释，语句分格符，白空格这么七个小的状态机，为了实现综合识别，我们需要把它们合并在一起，相比前面的整数与浮点数的合并来说，这次合并要简单的多，如果仔细观察可以发现，

1. 字符串识别的状态机的开始状态只在双引号下发生状态转移
2. 语句分格符状态机的开始状态只在符号‘；’和符号‘\n‘发生状态转移
3. 数识别的汰态机的开始状态只在数字0到9和点号下发生状态转移
4. 变量识别的状态机的开始状态只在字母a到z，字母A到Z，下划线，符号‘@'下发生状态转移
5. 白空格识别的状态机的开始状态只在空白符和制表符下发生状态转移
6. 注释识别的状态机的开始符叼只在符号‘#’下发生状态转移

上面这６个状态机的开始状态能识别的输入类型两两不同，没有冲突，所以合并这６个非常的简单

七个状态机已经讨论了６个，只剩下一个运算符，而这６个状态机与运算符突冲的也只有数的点号，这次冲突处理起来都很简单。只需要为冲突的状态建立一个等价的新状态，新状态的后继状态者是单个，不是组合状态。具体的合并就不细讲，下面我给出状态图：

由于在一张图中不好绘制，所以绘制了两张状态图。从上面的状态图，可以看出，七个状态机在合并后，总共增加了二个状态，为这二个状态构造状态链，把这7个状态机连接在一起，一个大的综合性的状态机就这么形成了。

（３）状态链的构造

二个状态里面，最复杂的是LexicalBegin，因为它能接受的输入类型最多，第二个状态LexicaiPoint能接受的类型只有一个，构造成来非常简单

首先，申明这两个状态：

/*merge parts*/
extern struct state me_begin;
extern struct state me_period;

第二步，为每一个状态构造状态链

a）状态LexicalBegin

输入类型有下面这么27种：

1. 符号＠，下画线，以及字母　　　（TO_ID)
2. 数字０　　　　　　　　　　　　（D_0)
3. 数字1到９　　　　　　　　　　（D1_9)
4. 双引号　　　　　　　　　　　　（D_QUOTE)
5. 空格和制表符                        　　　(WS)
6. 换行符　　　　　　　　　　　　(NewLine)
7. 分号　　　　　　　　　　　　（Semicolon)
8. 19种运算符　

1. '('    ')'    '['    ']'    '.'    ','
   '+'    '-'    '~'    '*'    '/'    '%'
   '<'    '>'    '='    '!'
   '&'    '^'    '|'

9. 除以上字符以外的所有字符      （Other）

用一个一维数组来映射状态LexicalBegin接受符号的输入类型：

enum MERGE_INPUT_TYPE
{
    ME_OTHER=0,
    ME_TO_ID,
    ME_D0,
    ME_D1_9,
    ME_QUOTE,
    ME_WS,
    ME_NEWLINE,
    ME_SEMICOLON,

    ME_COMMA,
    ME_PERIOD,
    ME_REVERSE,
    ME_L_RB,
    ME_R_RB,
    ME_L_SB,
    ME_R_SB,
    ME_EXCLAMATION,
    ME_AMPERSAND,
    ME_BAR,
    ME_CARET,
    ME_STAR,
    ME_PERCENT,
    ME_MINUS,
    ME_PLUS,
    ME_DIVIDE,
    ME_EQUAL,
    ME_GREATER,
    ME_LESS,
    ME_INPUT_NUM
};

char merge_input_map[ASCII_NUM]=
{
    0,0,0,0,0,0,0,0,0,5,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    5,15,4,0,0,20,16,0,11,11,19,22,8,21,9,23,2,3,3,3,3,3,3,3,3,3,0,7,26,24,25,0,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,13,0,14,18,0,
    0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,17,0,10,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

};

后继状态为：

struct state* me_begin_targets[]=
{
    &lex_state_err,        /*ME_OTHER*/
    &id_identifier,        /*ME_TO_ID*/
    &nu_zero,            /*ME_D0*/
    &nu_number,            /*ME_D1_9*/
    &st_string,            /*ME_QUOTE*/
    &ws_ws,                /*ME_WS*/
    &sb_newline,        /*ME_NEWLINE*/
    &sb_semicolon,        /*ME_SEMICOLON*/

    &op_comma,            /*ME_COMMA*/
    &me_period,            /*ME_PERIOD*/
    &op_reverse,        /*ME_REVERSE*/
    &op_l_rb,            /*ME_L_RB*/
    &op_r_rb,            /*ME_R_RB*/
    &op_l_sb,            /*ME_L_SB*/
    &op_r_sb,            /*ME_R_SB*/
    &op_not_equal_begin,/*ME_EXCLAMATION*/
    &op_bits_and,        /*ME_AMPERSAND*/
    &op_bits_or,        /*ME_BAR*/
    &op_bits_xor,        /*ME_CARET*/
    &op_multiply,        /*ME_STAR*/
    &op_mod,            /*ME_PERCENT*/
    &op_minus,            /*ME_MINUS*/
    &op_plus,            /*ME_PLUS*/
    &op_divide,            /*ME_DIVIDE*/
    &op_assign,            /*ME_EQUAL*/
    &op_greater_than,    /*ME_GREATER*/
    &op_less_than,        /*ME_LESS*/

};

状态LexicalBegin为:

struct state me_begin=
{
    "me_begin",
    TOKEN_UNKOWN,
    ME_INPUT_NUM,
    merge_input_map,
    0,
    me_begin_targets,
    0,
};

b）状态lexicalPoint

LexicalPoint只在输入类型D0_9下转移到Float::FractionBegin，输入映射数组：

char me_period_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,0,0,1,1,1,1,1,1,1,1,1,1,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,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
};

后继状态为：

struct state* me_period_targtes[]=
{
    &lex_state_err,
    &ft_fraction,
};

状态LexicalPoint：

struct state me_period=
{
    "me_period",
    TOKEN_DIVIDE,
    2,
    me_period_input_map,
    0,
    me_period_targtes,
    1,
};

到现在为止，已经把两个状态的状态链数据构造完成，七个小的状态机就被这两个状态链接了在一起，形成一个大的综合性的状态机，该状态机可以识别Redy语言中的所有单词。

（三）运行结果

这里贴几张运行的结果图来结大家看看，这部份的代码可以在tutorial/lexical/merge2下面找到

近回文档首页