青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆 - 17  文章 - 48  trackbacks - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用鏈接

留言簿(3)

隨筆檔案

搜索

  •  

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

實(shí)現(xiàn)正則表達(dá)式的想法很早就有,各種原因?qū)е聸]有做,最近花了點(diǎn)時(shí)間先實(shí)現(xiàn)了幾個(gè)簡(jiǎn)單的正則語法,分別是concatenation、alternation和closure,其他語法及metacharacter等有時(shí)間了有想法了之后再擴(kuò)展。

 

這三種基本的語法分別是對(duì)應(yīng)這樣的:

concatenation: abc    表示匹配字符串a(chǎn)bc

alternation: abc|def   表示匹配字符串a(chǎn)bc或者def

closure: a*               表示匹配零個(gè)到多個(gè)a構(gòu)成的字符串

 

我們知道正則表達(dá)式最終需要轉(zhuǎn)換成自動(dòng)機(jī)才能用來匹配字符串,我實(shí)現(xiàn)的正則通過如下幾個(gè)步驟把正則表達(dá)式轉(zhuǎn)換成自動(dòng)機(jī):

正則表達(dá)式->Parse成AST->生成邊(字符)集合->生成NFA->NFA subset construction->轉(zhuǎn)換成DFA->DFA minimization

最后用DFA minimization之后構(gòu)造的自動(dòng)機(jī)來匹配字符串。

 

正則語法的分析

一個(gè)正則表達(dá)式寫出來,要讓這個(gè)正則表達(dá)式匹配字符串等操作之前,我們先需要從正則表達(dá)式中提取需要的信息并在正則語法錯(cuò)誤的時(shí)候提示錯(cuò)誤,這個(gè)過程自然少不了parser。一個(gè)parser通常是從一個(gè)lexer里面獲取一個(gè)token,而正則表達(dá)式的token都是字符,那么lexer不需要做任何的分詞操作,只需要簡(jiǎn)單的把字符返回給parser即可。

那三種基本的正則語法對(duì)應(yīng)的BNF為:

re ::= alter
re_base ::= char | char_range | '(' re ')'
alter ::= alter_base alter_end
alter_base ::= concat
alter_end ::= '|' alter_base alter_end | epsilon
concat ::= concat_base concat_end
concat_base ::= re_base | closure
concat_end ::= concat_base concat_end | epsilon
closure ::= re_base '*'

這個(gè)parser分析了正則表達(dá)式之后產(chǎn)生AST,AST的node類型為:

class ASTNode
{
public:
    ACCEPT_VISITOR() = 0;
    virtual ~ASTNode() { }
};
 
class CharNode : public ASTNode
{
public:
    explicit CharNode(int c) : c_(c) { }
 
    ACCEPT_VISITOR();
 
    int c_;
};
 
class CharRangeNode : public ASTNode
{
public:
    struct Range
    {
        int first_;
        int last_;

        explicit Range(int first = 0, int last = 0)
            : first_(first), last_(last)
        {
        }
    };

    CharRangeNode() { }

    void AddRange(int first, int last)
    {
        ranges_.push_back(Range(first, last));
    }
 
    void AddChar(int c)
    {
        chars_.push_back(c);
    }
 
    ACCEPT_VISITOR();
 
    std::vector<Range> ranges_;
    std::vector<int> chars_;
};
 
class ConcatenationNode : public ASTNode
{
public:
    void AddNode(std::unique_ptr<ASTNode> node)
    {
        nodes_.push_back(std::move(node));
    }
 
    ACCEPT_VISITOR();
 
    std::vector<std::unique_ptr<ASTNode>> nodes_;
};
 
class AlternationNode : public ASTNode
{
public:
    void AddNode(std::unique_ptr<ASTNode> node)
    {
        nodes_.push_back(std::move(node));
    }
 
    ACCEPT_VISITOR();
 
    std::vector<std::unique_ptr<ASTNode>> nodes_;
};
 
class ClosureNode : public ASTNode
{
public:
    explicit ClosureNode(std::unique_ptr<ASTNode> node)
        : node_(std::move(node))
{
    }
 
    ACCEPT_VISITOR();
 
    std::unique_ptr<ASTNode> node_;
};

其中ASTNode作為AST的基類,并提供接口實(shí)現(xiàn)Visitor模式訪問ASTNode類型。

 

字符(邊)集的構(gòu)造

AST構(gòu)造好了之后,需要把AST轉(zhuǎn)換成NFA。語法中有[a-zA-Z0-9]這種字符區(qū)間表示法,我們可以用最簡(jiǎn)單原始的方法轉(zhuǎn)換,就是把區(qū)間中的每個(gè)字符都轉(zhuǎn)化成相應(yīng)的一條邊(NFA中的邊),這樣一來會(huì)導(dǎo)致字符區(qū)間越大,對(duì)應(yīng)邊的數(shù)量會(huì)越多,使得對(duì)應(yīng)的NFA也越大。因此,我們需要構(gòu)造區(qū)間字符集合來減少邊的數(shù)量。

比如正則表達(dá)式是:a[x-z]|[a-z]*e

那么我們希望對(duì)應(yīng)的字符集合是這樣:[a-a] [b-d] [e-e] [f-w] [x-z]

這需要構(gòu)造一個(gè)字符集,每次插入一個(gè)區(qū)間的時(shí)候,把新插入的區(qū)間與已存在的區(qū)間進(jìn)行分割,初始時(shí)已存在的區(qū)間集為空,那么正則表達(dá)式a[x-z]|[a-z]*e的劃分步驟如下:

已存在區(qū)間集合{},插入[a-a],得到{[a-a]}

已存在區(qū)間集合{[a-a]},插入[x-z],得到{[a-a], [x-z]}

已存在區(qū)間集合{[a-a], [x-z]},插入[a-z],得到{[a-a], [b-w], [x-z]}

已存在區(qū)間集合{[a-a], [b-w], [x-z]},插入[e-e],得到{[a-a], [b-d], [e-e], [f-w], [x-z]}

這個(gè)區(qū)間構(gòu)造完成了之后,還需要在后面轉(zhuǎn)換成NFA邊的時(shí)候,根據(jù)字符區(qū)間查詢出在這個(gè)集合中,由哪幾個(gè)區(qū)間構(gòu)成,比如:

查詢區(qū)間[a-a],得到[a-a]

查詢區(qū)間[x-z],得到[x-z]

查詢區(qū)間[a-z],得到區(qū)間[a-a] [b-d] [e-e] [f-w] [x-z]

在轉(zhuǎn)換成NFA時(shí),集合中的每個(gè)區(qū)間都對(duì)應(yīng)一條邊,這樣相對(duì)于每個(gè)字符對(duì)應(yīng)一條邊,邊的數(shù)量不會(huì)太多。

有了這么一個(gè)集合構(gòu)造的類之后,把正則的AST中的字符信息提取出來構(gòu)造出這么個(gè)集合即可,這樣只需要寫個(gè)visitor就完成了:

class EdgeSetConstructorVisitor : public Visitor
{
public:
    explicit EdgeSetConstructorVisitor(EdgeSet *edge_set)
        : edge_set_(edge_set)
    {
    }
 
    EdgeSetConstructorVisitor(const EdgeSetConstructorVisitor &) = delete;
    void operator = (const EdgeSetConstructorVisitor &) = delete;
 
    VISIT_NODE(CharNode);
    VISIT_NODE(CharRangeNode);
    VISIT_NODE(ConcatenationNode);
    VISIT_NODE(AlternationNode);
    VISIT_NODE(ClosureNode);

private:
    EdgeSet *edge_set_;
};

邊集合構(gòu)造完成之后,下一步就是生成NFA了。

posted on 2013-07-05 13:30 airtrack 閱讀(4441) 評(píng)論(3)  編輯 收藏 引用

FeedBack:
# re: 正則表達(dá)式實(shí)現(xiàn)(一) 2013-07-05 23:31 陳梓瀚(vczh)
# re: 正則表達(dá)式實(shí)現(xiàn)(一) 2013-07-06 01:34 airtrack
@陳梓瀚(vczh)
哈哈,早知道陳祖寫過正則引擎的系列文章,一直沒看,是想在我自己思考之后如果遇到問題的時(shí)候再看,啊哈哈。  回復(fù)  更多評(píng)論
  
# re: 正則表達(dá)式實(shí)現(xiàn)(一) 2013-07-06 20:13 溪流
學(xué)習(xí)了  回復(fù)  更多評(píng)論
  

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
      <noscript id="pjuwb"></noscript>
            <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
              <dd id="pjuwb"></dd>
              <abbr id="pjuwb"></abbr>
              国产精品九九久久久久久久| 欧美中文字幕在线| 欧美日韩免费看| 亚洲一区二区三区在线播放| 一本一本久久a久久精品综合妖精 一本一本久久a久久精品综合麻豆 | 国产精品久久久久久影院8一贰佰| 一本色道久久加勒比88综合| 99精品视频网| 国产精品视频久久一区| 久久高清免费观看| 老司机免费视频一区二区| 亚洲美女一区| 一个人看的www久久| 国产色视频一区| 欧美激情在线观看| 国产精品99一区| 久久精品在线播放| 欧美国产日韩一二三区| 亚洲欧美久久久| 久久影视精品| 午夜国产欧美理论在线播放| 久久九九精品99国产精品| 亚洲乱码一区二区| 欧美一区二区精美| 亚洲精品欧美激情| 亚洲欧美日韩在线观看a三区| 狠狠v欧美v日韩v亚洲ⅴ| 亚洲人成艺术| 韩国v欧美v日本v亚洲v| 日韩网站在线看片你懂的| 国产综合精品| 中文一区在线| 亚洲欧洲日本国产| 性做久久久久久| 在线综合欧美| 久久网站免费| 欧美一区二区视频网站| 欧美精品尤物在线| 久久综合激情| 国产欧美精品国产国产专区| 91久久在线播放| 激情婷婷欧美| 欧美一区二区精品久久911| 在线一区欧美| 欧美精品在线免费播放| 欧美成人一品| 韩日成人av| 欧美一区二区三区免费大片| 亚洲性感美女99在线| 欧美国产精品人人做人人爱| 另类天堂视频在线观看| 国产精品人成在线观看免费| 日韩午夜激情电影| 9国产精品视频| 欧美极品一区| 亚洲激情视频在线| 最新国产精品拍自在线播放| 久久久久欧美| 久久综合给合| 国产一区深夜福利| 久久精品理论片| 久久综合电影| 影音先锋在线一区| 久久午夜国产精品| 欧美成人按摩| 亚洲精品日韩精品| 欧美日韩国产一区精品一区 | 亚洲国产一区二区精品专区| 亚洲国产三级| 欧美乱在线观看| 亚洲国产精品第一区二区三区| 精品51国产黑色丝袜高跟鞋| 久久精品人人做人人爽电影蜜月| 久久精品一二三| 狠狠爱成人网| 美女视频网站黄色亚洲| 欧美韩日精品| 一区二区日韩免费看| 欧美偷拍一区二区| 亚洲一区观看| 美国三级日本三级久久99| 亚洲激情成人在线| 欧美精品乱码久久久久久按摩| 亚洲伦理在线| 久久精品国产77777蜜臀| 今天的高清视频免费播放成人| 久久欧美肥婆一二区| 亚洲国产一成人久久精品| 亚洲天堂成人在线视频| 国产精品日韩欧美一区二区| 久久精品麻豆| 99国产一区二区三精品乱码| 久久精品国产v日韩v亚洲| 亚洲精品国产拍免费91在线| 国产精品www| 久久亚洲一区| 亚洲午夜电影在线观看| 欧美电影在线免费观看网站| 亚洲一区二区毛片| 亚洲第一在线视频| 国产精品日韩二区| 欧美精品一级| 久久成人久久爱| 99成人在线| 欧美国产视频日韩| 久久国产精品久久久久久| 99人久久精品视频最新地址| 国内视频精品| 国产精品草莓在线免费观看| 裸体歌舞表演一区二区| 午夜激情综合网| 9i看片成人免费高清| 噜噜爱69成人精品| 亚洲欧美在线一区二区| 91久久中文字幕| 午夜精品亚洲| 日韩视频在线播放| 久久久亚洲精品一区二区三区| 伊人久久亚洲热| 国产午夜精品视频| 欧美刺激性大交免费视频| 亚洲小视频在线观看| 欧美大尺度在线观看| 亚洲高清不卡在线| 国内精品久久久久久 | 亚洲国产婷婷综合在线精品| 欧美一区二区免费| 99re在线精品| 在线日本欧美| 欧美精品一区二区三区一线天视频 | 亚洲欧洲日产国产综合网| 国产精品福利在线| 免费不卡中文字幕视频| 久久久最新网址| 亚洲影视九九影院在线观看| 亚洲国产欧美精品| 久久综合久久美利坚合众国| 欧美一区二区福利在线| 亚洲专区免费| 亚洲精品乱码视频| 极品少妇一区二区三区精品视频| 国产精品人人做人人爽| 欧美黄色免费网站| 另类专区欧美制服同性| 欧美制服丝袜第一页| 亚洲一区二区三区精品视频| 久久久久国色av免费观看性色| 久久久久青草大香线综合精品| 亚洲欧美国产77777| 艳女tv在线观看国产一区| 亚洲国产高清自拍| 国产精品免费一区二区三区观看| 国产精品日韩高清| 国产精品高潮在线| 欧美三级视频在线播放| 欧美日韩国产二区| 欧美日韩亚洲高清一区二区| 欧美连裤袜在线视频| 欧美大胆成人| 欧美激情精品久久久| 久久久久久久久久久久久女国产乱| 久久久久久国产精品mv| 久久全球大尺度高清视频| 久久精品视频播放| 久久久777| 久久精品国产一区二区电影| 欧美高清视频在线| 午夜视频一区在线观看| 亚洲午夜电影在线观看| 亚洲伊人第一页| 久久精品国语| 欧美在线播放一区二区| 欧美成人资源| 欧美午夜在线视频| 国产精品视屏| 国产精品久久久久久久久| 永久免费视频成人| 亚洲免费激情| 亚洲欧美大片| 老司机67194精品线观看| 欧美搞黄网站| 国产精品99久久99久久久二8| 亚洲精品在线免费| 亚洲欧美一区二区原创| 欧美精品日韩三级| 国产精品一区亚洲| 一色屋精品视频免费看| 99热在这里有精品免费| 久久精品91| 亚洲免费av电影| 久久高清免费观看| 欧美日本韩国| 亚洲激情一区二区| 午夜精品在线看| 亚洲大胆av| 亚洲精品日韩在线| 能在线观看的日韩av| 国产精品一区一区三区| 91久久一区二区| 亚洲自拍啪啪|