Flex技巧总结 && [LeetCode]Valid Number题解

前言

flex作为一个古老且强大的通用工具,由于为了适应多种多样的开发需求,因此存在着种种小技巧,用于实现某种特定的功能。本文试图将实际应用flex进行工程开发的过程中一些常见的用法进行总结,方便日后的参考与使用。

flex最为核心的功能,就是生成一个yylex()函数,这个函数自动从输入文件读入数据,进行匹配,并返回对应的token。用户在自定义词法分析的时候,所需要做的就是构建词法规则,告诉flex当匹配到某条规则的时候,需要执行怎样的操作,并返回什么值。这样,通过不断调用yylex()来匹配输入流,就可以将一段复杂代码拆分成较为有序的token流。

调整IO方式

虽然DFA在状态转移的过程中一次前进一个字符,但是为了提高IO效率,实际从文件读取的时候一般是批量往缓冲区读入的。如果有需要微调这个读入策略的需求,可以通过定义YY_INPUT宏来实现。在默认生成的代码中,这个宏被定义为一段比较复杂的C代码,当然你也可以将其修改成如下的形式来修改读入文件:

#undef YY_INPUT
#define YY_INPUT(buf,result,max_size) \
    if ( (result = fread( (char*)buf, sizeof(char), max_size, fin)) < 0) \
        YY_FATAL_ERROR( "read() in flex scanner failed");

正常情况下,flex从yyin这个文件指针来读入数据,并将需要输出的数据输出到yyout,这两个指针默认会被初始化为stdin/stdout。按照上述方式重新定义IO策略后,就会变为从fin这个文件指针来读入数据,但是输出位置还是一样的。当然,你也可以直接覆盖yyin/yyout所指向的位置,效果是等价的。

设置初始化代码

我们知道,flex的用法本质上就是"规则->行为"这样的模式,当输入匹配某个正则规则后,执行用户自定义的代码行为,并结合其他辅助代码来实现整体的功能。那么如果我们需要在每个规则匹配时,都先执行一段初始化代码呢?难道需要把这段代码复制到每一个规则的地方吗?事实上,只需要将这类用于每一条规则的代码定义为YY_USER_ACTION宏即可。这样,在发生规则匹配的时候,就会自动调用它。

词法分析中的状态转移

尽管flex是利用DFA来实现规则匹配的,但在编写规则的过程中,仍然要用到状态机的思想。对于一段代码,一般而言会分为三类字符串:代码本身、字符串字面常量以及注释。绝大多数语义在注释以及字符串常量中都没有意义,因此如果将其混在一起处理,显然会让词法分析规则变得非常冗余。因此,在构造规则的时候,我们也必须应用状态转移的思想:处于代码文本的时候是一个状态,处于常量以及注释的时候则是另外两种状态。状态之间可以相互转移:比如如果遇到标识注释开始的符号,则进入注释状态,此时会忽略一切其他规则,直至遇到注释结束标识符,此时会回到代码文本的状态,继续应用其他规则进行匹配。

为了实现这样的效果,一方面我们可以定义一些C语言的全局变量来记录状态,不过更好的方式是利用flex自身所提供的“条件规则”功能。这个功能的意思是说,我们可以为规则设置某些条件,每次只有当这个条件被激活的时候,这条规则才是有效的。并且,我们也可以为某条规则设置多个条件,只有当这些条件都被满足的时候,才会应用这条规则进行匹配。这样做最大的好处在于,可以使得规则文件写得非常简洁,同时也包含了足够的信息。

详细用法可以参考flex文档第10节"Start Conditions"。

复用DFA状态转移图

Flex不仅仅是用于构造编译器的强大工具,同样也可以将其生成的状态转移图用于二次开发。我们以LeetCode上的Valid Number这道题目为例,来展示如何利用flex强大的DFA生成功能,简洁、优雅地解决这道题目。

这道题目的题意简而言之就是让你判断一个浮点数是否合法。如果用Python的int转换,结合异常捕获,几行代码就可以搞定,或者是用正则表达式的话也会很简单。当然,用动态语言的这类高级功能来解题明显是露怯的行为,如果一定要用C艹自己造轮子呢?显然,正则表达式所基于的有限状态自动机模型是解决这类问题的利器,它避免了我们显式地进行一个又一个特殊情况判断,而是直接用一个循环以及定义了状态转移规则的矩阵来搞定。唯一的问题就是,对于这种状态比较多的正则,人肉推导实在是麻烦。

如果是按照正统方法,我们先需要用原始正则文法(Regular Language)来描述这个正则表达式,然后转换成非确定性有限状态自动机(NFA),再转换成确定性有限状态自动机,最后将其状态化简。每一步虽然看起来都非常可行,然而这并没有什么卵用,因为中间过程会非常凌乱,或许你推导一半就会失控。另一方面,你可以凭借自己的经验和感觉来推导这个自动机,或许会比严谨的数学方法简便很多,但依然需要一定的工作量,并且增加了出错的可能性。总而言之,对于这道题目,最后化简出的DFA是这个样子的:

手工推导的有限状态自动机

而对于实际工作中可能遇到的,涉及到高性能正则表达式匹配的需求,显然会比这种玩具题目更加复杂。难道除了无脑调用正则函数库以及人肉推导自动机之外,就没有别的简便办法了吗?实际上,古老而强大的flex工具,在这里恰恰提供了一个简洁优雅的解决方案。

flex规则

对于上述这道题目,使用flex构造词法匹配规则如下:

float.flex

WHITE   " "|\t|\f|\r|\v
%%
{WHITE}*[+-]?(([0-9]+(\.[0-9]*)?)|(\.[0-9]+))([Ee][+-]?[0-9]+)?{WHITE}* {return true;}
. {return false;}
%%

如果熟悉flex规则的话,上述这段代码的含义是显然的:首先定义空白字符(对于这道题目其实没必要),然后用一条规则用来匹配出格式合法的浮点数,一条规则捕获不合法的情况。这样,我们执行命令flex -o float.cpp float.flex,就能够生成对应的C艹源代码文件。但是很显然,这里生成的代码,是根本无法编译的,因为没有给出相关的函数和定义。我们当然可以补全相关的代码,来直接用flex的生成结果实现我们的需求,但由于flex在生成代码的时候添加了大量无用的冗余,因此造成生成结果非常臃肿,所以如果能够仅仅从中提取我们所需要的部分,必然会是更好的。

提取有效信息

从生成的代码中,我们所需要的无非就是两样东西:DFA的状态转移图(矩阵的形式),以及用于词法分析的yylex()函数,其中定义了各个状态的含义。其实flex在默认的情况下,会输出压缩版本的状态转移矩阵,因为完整版本的矩阵是Nx128大小(其中N是自动机的状态数,128则是字符集大小),如果不经压缩的话,会带来不必要的空间开销。因此,为了输出完整版矩阵,我们在调用flex的时候需要增加-Cf参数,即:flex -Cf -o float.cpp float.flex

这样,在生成的代码中,就会包含形如下面的这样两条语句,定义了未被压缩的状态转移矩阵,以及接受状态表:

static yyconst flex_int16_t yy_nxt[][128] = {...}
static yyconst flex_int16_t yy_accept[..] = {...}

其中yyconst就是const关键字,或许是出于可移植性以及用户可定制性的考虑,flex将大量关键字define/typedef成了自己的特殊关键字,不过从名称上大体都能猜出是什么含义。

有了状态转移图,接下来的问题就是,如何使用它呢?此时就我们就需要参考词法分析函数——yylex()的具体实现了。在flex所生成的代码中,连这个函数的定义语句都被define成YY_DECL#define YY_DECL int yylex (void),但好在还不太干扰可读性。总而言之,找到这个标识符所对应的函数体,我们就可以简单加以分析。把一些干扰我们的注释、编译指导语句等删掉以后,得到下面这份代码框架(可以看出,缩进惨不忍睹):

YY_DECL
{
    register yy_state_type yy_current_state;
    register char *yy_cp, *yy_bp;
    register int yy_act;

    if ( !(yy_init) )
        {
        (yy_init) = 1;

        if ( ! (yy_start) )
            (yy_start) = 1; /* 定义起始状态 */

        if ( ! yyin )
            yyin = stdin;   /* 定义输入文件 */

        if ( ! yyout )
            yyout = stdout; /* 定义输出文件 */

        if ( ! YY_CURRENT_BUFFER ) { /* 提供对于缓冲区的微调功能 */
            yyensure_buffer_stack ();
            YY_CURRENT_BUFFER_LVALUE =
                yy_create_buffer(yyin,YY_BUF_SIZE );
        }

    {
    while ( 1 )     /* 主循环,直至读取到EOF */
        {
        // 下面这些与字符指针相关的地方,都是在提供yytext的功能
        // 即当匹配成功后能够取出匹配到的字符串
        yy_cp = (yy_c_buf_p);

        /* Support of yytext. */
        *yy_cp = (yy_hold_char);

        /* yy_bp points to the position in yy_ch_buf of the start of
         * the current run.
         */
        yy_bp = yy_cp;

        yy_current_state = (yy_start);
yy_match:
        /* 在这里不断进行状态转移,直至无法继续转移 */
        /* 注意YY_SC_TO_UI是一个宏,功能是安全地将字符转换为对应的无符号整型 */
        /* 本质上其实就是在图中,根据当前状态,以及下一个字符,来进行转移 */
        while ( (yy_current_state = yy_nxt[yy_current_state][ YY_SC_TO_UI(*yy_cp) ]) > 0 )
            {
            if ( yy_accept[yy_current_state] )
                {
                (yy_last_accepting_state) = yy_current_state;
                (yy_last_accepting_cpos) = yy_cp;
                }

            ++yy_cp;
            }

        yy_current_state = -yy_current_state;

yy_find_action:
        /* 然后检查是否停止在了接受状态 */
        yy_act = yy_accept[yy_current_state];

        YY_DO_BEFORE_ACTION;

do_action:  {...} //这里主要是处理读取到EOF的情况

case 1: /* 由此可见,在yy_accept中,值为1的就是接受状态,其他状态都不合法 */
{return true;}
    YY_BREAK
case 2:
{return false;}
    YY_BREAK
case 3:
ECHO;
    YY_BREAK
case YY_STATE_EOF(INITIAL):
    yyterminate();

    case YY_END_OF_BUFFER:

    default:
        YY_FATAL_ERROR(
            "fatal flex scanner internal error--no action found" );
    } /* end of action switch */
        } /* end of scanning one token */
    } /* end of user's declarations */
} /* end of yylex */

从中可以看出,1表示状态转移图中的起始节点,在进行正则匹配的时候,我们从这一点开始,读入字符,不断转移,直至停止在某个节点,无法进一步转移。此时我们在接受状态表中查找当前状态所对应的数值,如果是1的话,说明这是个接受状态,否则就不是。注意这里面的两个1含义完全不同:前者是状态的标识,后者则是标志某个状态是否是接受状态。

理解了yylex()函数是如何使用状态转移图的,我们就能以同样的方式将其嵌入我们的程序中。简而言之,就是也按照同样的起始状态,一个个读入字符来转移,并且在无法继续转移,或者字符已经读完的时候,判断一下是否停在了接受状态。由此得到的解题代码如文末附录1所示,虽然确实能够解决这道题目,但是由于代码太长,根本无法交到LeetCode上。并且,在实际的工程中,这么长的代码,硬编码这么多的常数,也是件很丑陋的事情。

状态转移矩阵的压缩

为了解决代码冗长的问题,我们可以尝试使用flex的压缩版矩阵。同样地,我们需要分析yylex()函数的具体行为,并将其移植到自己的程序中。上文中已经提到,如果不加-Cf参数,flex会生成压缩版本的状态转移矩阵。由于这种压缩技巧比较tricky,实际上在生成的代码中会定义多个矩阵来用于状态转移:

static yyconst flex_int16_t yy_accept[22] = {...}
static yyconst flex_int32_t yy_ec[256] = {...}
static yyconst flex_int32_t yy_meta[12] = {...}
static yyconst flex_int16_t yy_base[22] = {...}
static yyconst flex_int16_t yy_def[22] = {...}
static yyconst flex_int16_t yy_nxt[55] = {...}
static yyconst flex_int16_t yy_chk[55] = {...}

此时,在yylex()函数中,使用这些矩阵的方法变得稍微复杂了一些,但大体还是可以直接照着重构的。此时的状态转移循环如下所示:

yy_current_state = (yy_start);
yy_match:
do
    {
    register YY_CHAR yy_c = yy_ec[YY_SC_TO_UI(*yy_cp)] ;
    // 这个if语句就不影响状态转移,只是为了记录状态
    if ( yy_accept[yy_current_state] )
        {
        (yy_last_accepting_state) = yy_current_state;
        (yy_last_accepting_cpos) = yy_cp;
        }
    while ( yy_chk[yy_base[yy_current_state] + yy_c] != yy_current_state )
        {
        yy_current_state = (int) yy_def[yy_current_state];
        // 注意这个22是Magic Number,是会发生变化的
        if ( yy_current_state >= 22 )
            yy_c = yy_meta[(unsigned int) yy_c];
        }
    yy_current_state = yy_nxt[yy_base[yy_current_state] + (unsigned int) yy_c];
    ++yy_cp;
    }
// 这个43也是Magic Number
while ( yy_base[yy_current_state] != 43 );

我们只需要把这个循环中的冗余代码去掉,改写成自己的版本,就可以轻松地将压缩版的状态转移图应用到自己的程序中去。最终,我们得到的代码如附录2中所示,提交到LeetCode后轻松AC。

总结

虽然flex是一个非常古老的工具,但是在特定的场景下,也能够发挥出强大的作用。毕竟,它所依据的正则语言以及自动机理论,就是一切正则表达式工具的基础。因此,掌握这样的工具,并理解正则表达式引擎、编译器背后的深层次原理,是十分有助于提升程序员的自我修养的。

附:上述源代码以及flex规则文件可以点此下载

附录1

使用未压缩版状态转移矩阵得到的代码如下(省略了矩阵的大部分内容):

#define YY_SC_TO_UI(c) ((unsigned int) (unsigned char) c)
#define yyconst const
typedef int flex_int16_t;
typedef int flex_int32_t;
typedef unsigned char YY_CHAR;
static yyconst flex_int16_t yy_nxt[][128] =
    {
    {
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,

        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
        0,    0,    0,    0,    0,    0,    0,    0
    },
    ......
    } ;
static yyconst flex_int16_t yy_accept[21] =
    {   0,
        0,    0,    4,    2,    2,    3,    2,    2,    1,    0,
        0,    0,    1,    1,    1,    1,    0,    1,    0,    1
    } ;
class Solution {
public:
    bool isNumber(string s) {
        int yy_current_state = 1;
        for ( int i = 0; i < s.length(); ++i ) {
            yy_current_state = yy_nxt[yy_current_state][YY_SC_TO_UI(s[i])];
            if ( yy_current_state < 0 ) return false;
        }
        return yy_accept[yy_current_state] == 1;
    }
};

附录2

使用压缩版状态转移矩阵得到的代码如下:

#define YY_SC_TO_UI(c) ((unsigned int) (unsigned char) c)
#define yyconst const
typedef int flex_int16_t;
typedef int flex_int32_t;
typedef unsigned char YY_CHAR;
static yyconst flex_int16_t yy_accept[22] =
    {   0,
        0,    0,    4,    2,    2,    3,    2,    2,    1,    0,
        0,    0,    1,    1,    1,    1,    0,    1,    0,    1,
        0
    } ;

static yyconst flex_int32_t yy_ec[256] =
    {   0,
        1,    1,    1,    1,    1,    1,    1,    1,    2,    3,
        4,    5,    6,    1,    1,    1,    1,    1,    1,    1,
        1,    1,    1,    1,    1,    1,    1,    1,    1,    1,
        1,    7,    1,    1,    1,    1,    1,    1,    1,    1,
        1,    1,    8,    1,    8,    9,    1,   10,   10,   10,
       10,   10,   10,   10,   10,   10,   10,    1,    1,    1,
        1,    1,    1,    1,    1,    1,    1,    1,   11,    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,    1,    1,    1,    1,

       11,    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,    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,    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,    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,    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,    1,    1,    1,    1,
        1,    1,    1,    1,    1,    1,    1,    1,    1,    1,
        1,    1,    1,    1,    1
    } ;

static yyconst flex_int32_t yy_meta[12] =
    {   0,
        1,    1,    1,    1,    1,    1,    1,    1,    1,    1,
        1
    } ;

static yyconst flex_int16_t yy_base[22] =
    {   0,
        0,    0,   42,   43,   10,   43,   12,   31,   21,    0,
        0,   30,    0,   24,   25,   28,   29,   19,   14,    3,
       43
    } ;

static yyconst flex_int16_t yy_def[22] =
    {   0,
       21,    1,   21,   21,   21,   21,   21,   21,   21,    5,
        7,   21,    9,    9,   14,   14,   21,   14,   21,   15,
        0
    } ;

static yyconst flex_int16_t yy_nxt[55] =
    {   0,
        4,    5,    6,    5,    5,    5,    5,    7,    8,    9,
        4,   10,   20,   10,   10,   10,   10,   11,   12,   13,
       12,   13,   15,   20,   15,   15,   15,   15,   18,   16,
       13,   17,   21,   14,   21,   21,   19,   18,   20,   14,
       14,   21,    3,   21,   21,   21,   21,   21,   21,   21,
       21,   21,   21,   21
    } ;

static yyconst flex_int16_t yy_chk[55] =
    {   0,
        1,    1,    1,    1,    1,    1,    1,    1,    1,    1,
        1,    5,   20,    5,    5,    5,    5,    5,    5,    5,
        7,    7,    9,   19,    9,    9,    9,    9,   18,    9,
        9,    9,   14,   14,   15,   15,   17,   16,   17,   12,
        8,    3,   21,   21,   21,   21,   21,   21,   21,   21,
       21,   21,   21,   21
    } ;

class Solution {
public:
    bool isNumber(string s) {
        int yy_start = 1;
        int yy_current_state = yy_start;
        for ( int i = 0; i < s.length(); ++i ) {
            register YY_CHAR yy_c = yy_ec[YY_SC_TO_UI(s[i])] ;
            while ( yy_chk[yy_base[yy_current_state] + yy_c] != yy_current_state )
                {
                yy_current_state = (int) yy_def[yy_current_state];
                if ( yy_current_state >= 22 )
                    yy_c = yy_meta[(unsigned int) yy_c];
                }
            yy_current_state = yy_nxt[yy_base[yy_current_state] + (unsigned int) yy_c];
        }
        return yy_accept[yy_current_state] == 1;
    }
};
comments powered by Disqus
发布时间:
2015-06-15
分类:
标签: