用户:  密码: 记住我     找回密码 
| 文章 >> 编程通用 >> 算法

编写自己的正则表达式解析器

日期 | 作者阿米尔Gerzic | 浏览86 | 评分100 | 标签算法 评论

{S0}简介
你有没有想过正则表达式的详细工作如何?如果答案是肯定的,那么这篇文章适合你。我会设法引导你一步一步如何创建自己的迷你正则表达式库。本文的目的是不给你一个高度优化,测试和伟大的正则表达式库,但解释后面的文本文件中的模式匹配的校长。如果你只想要一个好的图书馆,并不在乎它是如何工作的,您可能需要升压的regex库,你可以找到。我必须承认,我没有完全阅读文章,但在我看来,文章的重点主要是关于如何使用正则表达式库,由作者提供。在这篇文章中,笔者采用类似的技术(虽然我可能是错误的),以创建一个更复杂的库。您现在正在阅读的文章,可以被看作是为我刚才提及的文章的先决条件。
正则表达式的MS。NET库或Java SDK(如果你写在Java代码中)。正如你可以看到,正则表达式在许多不同的编程语言和技术。其实的文章,不注重在具体的语言编写的库。我写在C代码,使用STL主要是因为它是我最喜欢的语言/库,但是从文章的原则可以适用于任何语言(显然)。我会尝试尽可能独立的语言,如可能的话使用伪代码。如果你想在Java代码中,请给我发送电子邮件。本文提供的代码是免费的(显然),但如果你喜欢它,并在您的应用程序中使用它,将是巨大的,如果你给我什么我应得的信贷。也请给我发电子邮件,所以我可以炫耀我的同行和/或潜在的雇主。概述
那么如何我们要做到这一点?之前,我们开始与编码,这是必要的,需要充分了解这里本文中使用的方法来解释数学的背景的。我会强烈建议阅读和理解数学的背后,因为一旦我们克服了数学的一部分,其余的将是非常简单的。但是请注意,我不会有任何数学证明。如果你是在证明有兴趣,请检查出的引用,可以在本文的部分发现。此外,请注意,正则表达式解析器,我们将在这里创建将支持这三个操作:KLEEN封闭或星空运营商("*")级联(例如:"AB")UNION运算符(与字符表示"|")
然而,许多额外的运营商可以模拟相结合,这三家运营商。例如:A = AA *(至少有一个一)[0-9] =(0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)[Z] =(A |乙|...| Z)等。
实施只有三家运营商的原因非常简单。当我开始打算写这篇文章时,我很快就认识到,我不得不限制自己在很多方面。主题是如此之大,它需要一本书来解释每一个小细节(也许我有一天会写)。正如我以上所述,本文的目的是,装备库,但向您介绍正则表达式背后的原则。如果你想知道更多关于如何使用正则表达式,那么你可以检查出书:精通正则表达式 - 奥赖利。
以下为文章概述: &# 160;
NFA的代表不确定的有限状态自动机。 NFA的可以被看作是一种特殊的最终状态机,这在某种意义上是一个抽象的模型与原始的内部存储器的机器。如果你想知道有关有限状态机的更多信息,请参阅下面一节。
让我们来看看在NFA的数学上的定义。
NFA的一个组成:有限集我输入符号国家有限集S一个从S X我的下一个状态函数为P(S)一个接受状态的S的子集Q从S的初始状态S0
表示为A(I,S,F,Q,S0)
如果我们能解释12岁以上的定义,我们可以说,一个NFA是一个集合S的函数f连接的状态(可能是一个更聪明的12岁)。 NFAS代表两种格式:表和图。例如,让我们来看看表表示:
输入
国一b彗星ðEPSILONS0S1,S3 S1 S3 S4,S5 S4 {S6} S5 {S6}
相当于图:
表/图上面,我们可以看到,有特殊的转换称为EPSILON过渡,这是NFA的特色之一。过渡是一个从一个状态到另一个事件。 EPSILON过渡是一个从一个状态到另一个空字符串过渡。换句话说,我们会从一个状态到另一个上没有的字符输入。例如,我们可以看到从上面的表/图,我们可以从S3到S4和S5,这意味着我们有一个选择的输入。同样,有是有选择的字符输入A从状态S0,S1或S3国因此,名称不确定性,因为在某些时候,我们能去的路径是不是唯一的,但我们有一个选择。双盘旋像例如S6(或在"{}"中的表附后),最后接受国家制定。一旦达到这些国家之一,我们有一个接​​受的状态,因此一个接受字符串。
在一个NFA,喜欢的数学上的定义定义,总是启动状态。我Graphvis,一个伟大的工具绘制不同类型的图表(见节),用于绘图NFAS和的DFA(见后)。由于Graphvis奠定了自身的图形的节点,它在我看来,启动状态总是在图的顶部绘制的状态。因此,我们将按照该公约。
DFA的代表确定性有限状态自动机。 DFA是非常密切的关系到NFA。事实上,NFA的数学定义为DFA的太。但明显存在着差异,从中我们就会乘虚而入。一个很大的区别是,在一个DFA有没有EPSILON转换。此外,每个国家,从这种状态下,所有过渡在不同的输入字符。换句话说,如果我们在状态s,然后输入一个字符,该字符从第一个独特的转型此外,所有国家在一个DFA,必须有一个输入字符有效的过渡。这里输入字符是有限的我输入符号(如在数学上的定义)。例如,在上面的图表(下DFA的),符号,我将{A,B,C,D}。
现在,我们了解NFAS和的DFA,我们可以说,任何NFA的,有一个等价的DFA(您将不得不信任我,因为我不认为这是给你出发这句话的数学证明)。作为人类,通常它是我们更容易构造一个NFA,以及解释一个NFA的接受的语言。但是,为什么我们需要的DFA然后呢?那么,如果我们想对电脑,这是很难的"教"他们做的很好的教育的猜测(有时甚至是我们不能做出明智的猜测)。而这正是计算机需要做的,当遍历一个NFA的。如果我们写一个算法,它会使用NFA检查接受的字符组合,它会涉及检查的选择,它并没有使以前的回溯。显然,正则表达式解析器的工作使用NFAS,但他们通常比那些使用的DFA慢。这是由于这一事实,DFA有独特的道路,为每个接受字符串,所以没有涉及回溯。因此,我们要使用一个DFA,以检查是否输入字符的组合,是由一个自动机接受。
注意:如果你真的想了解NFAS和的DFA的,我会建议做进一步阅读这些主题。它作为一个练习是有用的转换从一个到另一个,要充分理解上的差异,这里使用的算法转换NFA到DFA的(见后)。
现在,我们所有数学的背景下,我们需要了解正则表达式,我们需要开始思考什么是我们的目标。作为第一步,我们意识到,我们需要从正则表达式的方式(如AB *(一个| B)*)的数据结构,这将是容易操作和使用模式匹配。但是,让我们先寻找一个正则表达式转换到NFA的方法。也许最有名的算法做这种转换是汤普森的算法。这种算法是不是最有效的,但它确保任何正则表达式(假设它的语法是正确的),将成功地转换为一个NFA的。随着从下图看到的基本NFA的的帮助下,我们可以构造任何其他:
使用上述的基本要素,我们将构建三个操作,这是我们想实现我们像下面的正则表达式解析器:
但是,我们如何从类似(A | B)* AB上面的图?如果我们认为我们真正需要做的,我们可以看到,评估正则表达式类似评估算术表达式。例如,如果我们想评价R = AB *光盘,我们可以做到这一点像:

PUSH乙
按C
MUL
添加
PUSH ð

的POP ř
PUSH和POP栈和MUL,ADD和SUB采取从堆栈中的2个操作数,并做相应的操作。从正则表达式构造NFA的,我们可以使用这方面的知识。让我们来看看为了构造NFA的正则表达式(A | B),需要执行的操作序列* CD:

PUSH b
联盟
之星
按C
CONCAT
PUSH ð
CONCAT
的POP ř
我们可以看到,这是非常相似的算术表达式的评价。不同的是明星操作,在正则表达式从堆栈中弹出只有一个元素,并评估星级操作员。此外,串联操作是没有任何符号表示,所以我们就检测到它。的文章中提供的代码,从而简化了前处理正则表达式,每当检测到串联插入一个字符的ASCII代码0x8问题。显然,这是可以做这个"飞",在正则表达式的评价,但我想尽可能简化评估。前处理什么也不做,但检测的符号,例如一样,会导致在串联的组合:AB,(,),*,*(,)(。
PUSH和POP操作的实际工作与简单的NFA对象的堆栈。如果我们将推动在堆栈上的标志,操作将在堆上创建两个状态的对象,并创建一个过渡的象征,从状态1到状态2对象。这里是推动在栈上的一个字符的代码部分:无效CAG_RegEx:推(chinput的字符){ / /创建2堆新的国家 CAG_State * S0 =新CAG_State(m_nNextStateID); CAG_State * S1 =新CAG_State(m_nNextStateID); / /添加输入字符S1从S0 - GT的过渡; S0 - GT; AddTransition(chinput的,S1); / /创建一个NFA的这2个国家  60; FSA_TABLE NFATable; NFATable.push_back(S0); NFATable.push_back(S1); / /推入操作数栈 m_OperandStack.push(NFATable); / /添加这个字符输入字符集 m_InputSet.insert(chinput的);}
我们可以看到,字符转换为一个简单的NFA,然后由此产生的NFA是添加到堆栈。 CAG_State类是一个简单的类,它可以帮助我们的结构,因为我们需要一个NFA的。它包含一个转换到其他国家的特定字符数组。 EPSILON过渡字符0x0的过渡。在这一点上,很容易看到背后NFA的结构。一个NFA和DFA存储作为一个国家的顺序(CAG_State deque的指针)。每个州作为一个成员,所有的转换存储在multimap中。过渡是没有别的比从字符映射到一个国家(CAG_State *)。 CAG_State类的详细定义,请参阅代码。
现在回到正则表达式到NFA的转换。现在我们知道如何入栈NFA的,在弹出的操作实在是微不足道。检索从堆栈中的NFA,就是这样。正如我刚才所说,NFA的表被定义为一个双端队列(STL容器dequelt; CAG_State * GT)。这样,我们知道,数组中的第一个国家总是起始状态,而最后的状态是最后/接受状态。维护这个顺序,我们可以迅速获得的第一个和最后一个国家以及作为追加在前面加上更多的国家在执行操作时(如星运营商)。下面是代码评估每一个人的操作:BOOL CAG_RegEx:CONCAT(){ / /弹出2个元素 FSA_TABLE甲,乙;& #160; 如果(POP(乙)| |!流行(一)) 返回FALSE; / /现在评估AB / /基本上采取从最后状态 / /添加一个EPSILON过渡到  0; / / B的商店,结果到的第一个国家 / /新NFA_TABLE和入栈 [A.size()-1] - GT; AddTransition(0,B [0]); B.end A.insert(A.end(),B.begin(),()); / /入栈结果 m_OperandStack.push(一); 返回TRUE;}
我们可以看到,串联是从堆栈中弹出两个NFAS。第一NFA是改变,所以,现在是新的NFA,然后将其压入堆栈。请注意,我们第一个弹出第二个操作数。这是因为在正则表达式中,操作数的顺序的重要性是因为AB = BA(不可交换)BOOL CAG_RegEx:!:星(){ / /弹出1元 FSA_TABLE甲,乙;   ;如果(!流行(一)) 返回FALSE;   ;/ /现在评估* / /创建2个新的国家,这将是插入& #160; / /在每个deque的结束。还需要A和 / /从去年EPSILON过渡到第一 / /在队列中的状态。添加EPSILON过渡 / /两个新的国家之间,插入一个 0; / /在开始将源和一个 / /插到底,将目标 CAG_State * pStartState =新CAG_State(m_nNextStateID); CAG_State * pEndState =新CAG_State(m_nNextStateID); pStartState - GT; AddTransition(0,pEndState); / /添加EPSILON从开始的状态过渡到第一状态 pStartState - GT; AddTransition(0,A [0]); / /添加从最后一个状态EPSILON过渡到最终状态 [A.size()-1] - GT; AddTransition(0 pEndState); / /从最后一个到第一个状态 [A.size()-1] - GT; AddTransition(0,A [0]); / /构造新的DFA和存储到堆栈 A.push_back(pEndState); A.push_front(pStartState); / /入栈结果 m_OperandStack.push(一); 返回TRUE; }
星运营商从堆栈中弹出一个元素,改变它根据汤普森的规则(见上文),然后把它stack.BOOL CAG_RegEx:联盟(){ / /弹出2个元素 FSA_TABLE甲,乙; 如果(POP(乙)| |!流行(一)) 返回FALSE; / /现在评估|乙 / /创建2个新的国家,一开始状态和 / /一个结束状态。从创建EPSILON过渡 / /启动状态,一开始国家和B  60;/ /创建结束EPSILON过渡 / /状态A和B的新的最终状态 CAG_State * pStartState =新CAG_State(m_nNextStateID); CAG_State * pEndState =新CAG_State(m_nNextStateID); pStartState - GT; AddTransition(0,A [0]); pStartState - GT; AddTransition(0,B [0]); & #160; [A.size()-1] - GT; AddTransition(0 pEndState);   ;乙 - GT; AddTransition(0,pEndState);  60; / /创建一个新的NFA B.push_back(pEndState); &# 160; A.push_front(pStartState); B.end A.insert(A.end(),B.begin(),()); / /入栈结果 &# 160; m_OperandStack.push(一); 返回TRUE;}
最后,联盟弹出两个元素,使改造,并将结果在栈上。请注意,我们在这里要留意的经营秩序。
最后,我们现在能够评估正则表达式。如果一切顺利,我们将在堆栈上的单一的NFA,这将是我们造成的NFA。下面的代码,利用上述functions.BOOL CAG_RegEx::CreateNFA(字符串strRegEx)/ /解析定期expresion使用类似 / /方法来计算算术表达式 / /但是,首先我们会检测连接和 / /插入CHAR(8)的位置  60; / /级联需求发生 strRegEx = ConcatExpand(strRegEx); (我= 0; ILT; strRegEx.size();我)  0; { / /得到的charcter & #160; 字符C = strRegEx [I];   ; (IsInput(C)) &# 160;PUSH(C); 否则,如果(m_OperatorStack.empty()) m_OperatorStack.push(C); 否则,如果(IsLeftParanthesis(C)) & #160; m_OperatorStack.push(C); &# 160; 否则,如果(IsRightParanthesis(C))  0; { / /评估括号everyting 而(!IsLeftParanthesis(m_OperatorStack.top()))   ; (EVAL())  60; 返回FALSE; & #160;/ /删除左括号后的评价 &# 160; m_OperatorStack.pop(); } & #160; 其他 { &# 160; (!m_OperatorStack.empty()放大器;放大器; Presedence(C,m_OperatorStack.top()))   ; (EVAL())  60; 返回FALSE; & #160; m_OperatorStack.push(C); } &# 160;} / /评估其余的运营商 而(!m_OperatorStack.empty()) (EVAL())  0; 返回FALSE; / /从堆栈中弹出结果 如果(!流行(m_NFATable))   ; 返回FALSE; / /最后NFA的状态始终是接受状态 m_NFATable [m_NFATable.size()-1] - GT; m_bAcceptingState = TRUE; 返回TRUE;}
函数eval实际上是评估在栈上的下一个经营者。函数eval()从操作栈中弹出未来的运营商,使用switch语句,它决定使用哪个操作。括号被视为运营商,因为他们判断评估的顺序。功能Presedence(CHAR左右,CHAR)确定的两家运营商,并返回TRUE,如果的优先级优先级的左边的运算符LT =右运算符的优先级。请检查执行的代码。
现在,我们知道如何将任何一个NFA的正则表达式,下一步是将其转换NFA到DFA的。起初,这个过程似乎是非常具有挑战性。我们有一个与零个或多个EPSILON转换图形,和多个单个字符的转换,我们需要一个没有EPSILON转换的等效图和每个输入字符的接受顺序的唯一路径。就像我说的,这似乎是非常具有挑战性的,但它是真的不。数学家实际上已经为我们解决了这个问题,然后使用结果,计算机科学家创建的子集构造算法。我不知道谁在这里给予信贷,但子集构造算法是这样的:
首先,让我们定义两个功能:EPSILON封闭:此函数作为参数,一套美国T,并再次返回一个包含所有这些国家,可以从每个个别国家EPSILON过渡的集合T达到的国家。移动:移动采取了一套美国T和输入字符a和返回可以在给定的输入字符形式达成的所有国家在T
使用这些功能,我们可以进行改造:DFA的开始状态是通过NFA的开始状态EPSILON封闭对于每一个新的DFA状态,请执行以下为每个输入字符:执行移动到新创建的状态EPSILON封闭的结果(一)创建新的状态。请注意,在这里我们可以得到一个国家,这已经是在我们现有的设置。这将导致在一组状态,这将形成新的DFA状态。请注意,这里从一个或多个NFA的国家,我们正在建设一个单一的DFA状态。对于每一个新创建的的状态,执行步骤2。DFA的接受状态,所有这些国家中,至少包含从NFA的接受国之一。请记住,我们在这里从一个或多个NFA的国家建设一个单一的DFA状态。
是不是很简单吗?如果没有,那么进一步阅读。以下是伪代码本书的118-121页的"编译器 - 原理,技术和工具"阿霍,Sethi和乌尔曼。下面的算法是相当于上述算法,但以不同的方式表达出来。首先,让我们的定义EPSILON封闭功能:S EpsilonClosure(T){& #160; 所有国家在T入栈 初始化的结果为T  60; 而堆栈不为空 { 从堆栈弹出吨 每一个从T边缘的状态u,ü标示EPSILON { &# 160; 如果U是不EpsilonClosure(T)   ; { 添加u到结果 推入堆栈的U } &# 160; } } 返回结果}
基本上,这个函数的是,经过T和其他国家可以从这些没有输入达成的检查中的所有国家。请注意,每个国家可以达到至少有一个国家没有投入,即本身。然后在功能上没有投入,通过进一步转换所有这些国家和检查。例如,让我们看看下面的:
如果我们称之为EPSILON转型的国家{S0,S2}产生的状态将{S0,S2,S1,S3}。这是因为从S0,我们可以达到S1上没有投入,但是从S1,我们可以达到S3上没有投入,因此,从S1,我们可以达到S3没有输入。
现在我们知道EPSILON过渡是如何工作的,让我们看看在伪代码转换NFA到一个DFA:国家= EpsilonClosure(NFA的启动状态),它是无人盯防同时也有在D国的任何无人盯防的状态{ 马克T 每个输入的象征 { U = EpsilonClosure(移动(T,A)); 如果U是不是在D -国 { 添加ü作为一个无人盯防的状态为D -国 }  60; DTran [T] U = }}
最后的DTran是DFA表,相当于NFA的。
之前,我们去下一个步骤,让我们转换NFA到一个DFA的手,用这个过程。如果你想掌握这个过程中,我会强烈建议您执行更多类似的转换,使用此方法。让我们转换以下的NFA到其相应的DFA使用的子集构造算法:{五}
使用的子集构造算法,我们将做如下(每个新创建的的国家会以粗体显示):创建通过采取EPSILON关闭NFA的开始状态开始DFA的状态。这一步产生的国家:{S1,S2,S4}执行移动('A',{S1,S2,S4}),在结果集:{S3,S4}执行EpsilonTransition({S3,S4}),它创建了一个新的DFA状态:{S3,S4}执行移动('B',{S1,S2,S4}),结果集:执行EpsilonTransition(),创建新的DFA状态:注:在这里,我们必须记录2个新的DFA {S3,S4}和,DFA的开始状态{S1,S2,S4}。同时,我们也必须记录字符过渡从{S1,S2,S4} {S3,S4}和{S1,S2,S4字符b} 。执行移动('A',{S3,S4}),它返回:{S4}执行与结果EpsilonTransition({S4}):{S4}执行移动('B',{S3,S4}),在结果集:{S3,S5}执行结果EpsilonTransition({S3,S5}):{S3,S5}{S3,S4} - > {S4}上{S3,S4} - GT;对b {S3,S5}执行移动('A',),它返回一个空集,所以我们并不需要检查EPSILON转换执行移动('B',),它返回一个空集,就这样算了吧。执行移动('A',{S4}),它返回:{S4}。但是,这不是一个新的状态,就这样算了吧。但是,我们必须记录的过渡:{S4} - > {S4}上执行移动('B',{S4})返回:执行EpsilonTransition()返回:(不新,但我们必须创记录的转变){S4} - > 对B执行移动('A',{S3,S5})返回一个空集,就这样算了吧。执行移动('B',{S3,S5}),其中生产:EpsilonTransition():,一个新的DFA状态{S3,S5} - GT; 对B移动('A',)是一个空集移动('B',这是不是新的,但必须记录过渡! - > 对B
有没有新的国家,所以我们所做的一切。以下是绘制的DFA:{中六}
起始状态是{S1,S2,S4},因为那是EpsilonClosure(NFA的开始状态)。接受状态,{S3,S4}和{S3,S5},因为它们包含S3和/或S5,这是接受NFA的状态。
,现在,我们已经所有的知识转换成一个NFA正则表达式,然后将其转换的NFA等价的DFA,我们实际上可以停止在这一点上,它使用模式匹配。最初,当我准备写这篇文章,以保持它作为简单的只显示原则可能时,DFA的优化没有考虑。但它发生,我认为,首先所有大的正则表达式,我们正在创造非常大的NFAS(汤普森的算法的性质),这反过来又偶尔会产生复杂的DFA。如果我们将搜索模式,这可能会降低大幅降低,所以我决定把优化作为一个正则表达式解析器的一部分。这里的优化是一个复杂的。因此,让我们来看看下面的例子:
{七}
,如果我们看一下在这个DFA,我们注意到,状态3,首先是所有不是最终状态。此外,我们注意到有从这个国家没有出边除循环。换句话说,一旦我们进入状态3,有没有机会去接受状态。这是由于这样的事实:一个DFA,除了事实,它具有独特的路径,并为每个接受字符串不包含EPSILON转换,它也必须对所有输入字符从一个特定的状态过渡(这里所有输入字符的意思是,可能会接受输入的字符集,例如:A | B | C,输入字符集为{A,B,C})。下面是我们滥用数学一点点,为了使一个DFA简单。删去状态3,我们的DFA变得更简单,它仍然接受同一套模式。在这种情况下,我们的DFA不再正是一个DFA。如果你问自己,为什么这是重要的,很好的回答是:是不是!至少我们!我们将利用这一非常基本的优化机制,以删除所有国家具有这样的特点,所以我们将获得更小,致密的DFA的模式匹配。总之,我们将删除状态(导致这些国家从其他国家和所有转换)以下特点:国家不接受状态国家没有任何转换到任何其他的不同的状态。
因此,结果如下:

上面的DFA,肯定似乎比前一个小。我仍然会调用这个一个DFA,尽管事实上,它是不是真的一个DFA。
最后,我们准备使用的所有部件,从上面一些文字模式匹配。一旦我们的DFA,所有我们需要做的的是采取输入字符和对初始状态运行。这里是这样做的伪代码:查找(字符串s){ s中的每个字符c { 每个活跃状态  0; { 如果有对C的过渡 { & #160; 进入下一个状态吨 &# 160; 如果T是接受状态  60; {  0; 记录模式   ; } 作为活跃的标志吨 } & #160; 标记小号为非活动 } 如果有从开始C状态的过渡 { & #160; 去下一个状态 如果S是接受状态 & #160; { 记录模式 }  60; 马克作为活跃 } }}
上面的代码可以发现,在查找(...)函数的正则表达式类。要跟踪活动状态,我使用一个链表,所以我可以快速添加和删除活动/非活动状态,分别。之后的所有字符都处理,所有结果都存储在一个向量,它包含模式匹配。使用功能FINDFIRST (...)和FindNext (...),你可以遍历的结果。请参阅CAG_RegEx类文档如何使用类的信息。此外,在这一点上,我要强调,演示程序加载到丰富的编辑控制的完整的文件,然后搜索完成时,它存储为一个字符串,使用FindFirst函数的一个参数传递。根据您的RAM大小,我想避免巨大的文件加载,因为它可以采取了大量的时间来复制数据从一个字符串到另一个,因为虚拟内存的使用。就像我刚才说的,计划的目的是显示在文本文件中的模式匹配背后的原则。根据时间,未来的版本可能包含一个更完整的正则表达式分析器,搜索任意大小的文件,并提供以不同的方式结果。
在这一点上,文章的完整性,我必须注意,有一个正则表达式直接转换成一个DFA的方式。这种方法是没有解释,但但如果时间允许,将在以后的文章(或文章更新)。此外,还有一些不同的方法构造一个正则表达式的NFA的。
好了,这就是它!我希望你喜欢阅读尽可能多的文章,因为我喜欢写。请使用在任何类型的应用程序的演示代码,但给我的地方当之无愧的信贷。如果你想建立一个更完整的资料库,使用这里介绍的演示代码,请给我增加的副本。
注:类CAG_RegEx SaveDFATable(包含两个函数)和SaveNFATable,这在调试模式下保存NFA与DFA到C:\ NFATable.txt和C:\ DFATable.txt分别。由于名称已经透露,这些都是NFA与DFA表。此外,类SaveNFAGraph()功能和SaveDFAGraph(),这在调试模式下创建两个文件C:\ NFAGraph.dot和C:\ DFAGraph.dot。这些文件是简单的文本文件,包含使用graphviz的(退房下面的参考文献4)绘制这些图形的指示。小号放大器;使用的工具"离散数学" - 理查德Johnsonbaugh(第五版)"离散数学及其应用" - 肯尼斯H.罗森(第四版)"编译器 - 原理,技术和工具" - 阿霍,Sethi和乌尔曼graphviz的从AT&T(任何类型的图表的绘图工具)。你可以找到它。
关于作者:阿米尔Gerzic


中国
我是一名编程爱好者,
谢谢orcode.com为我们提供一个学习和分享的平台。
有什么问题。可以就本内容回复,我看到时。会尽量回复的。
评论会员:Aaron_Redmond 时间:2011/11/30
伟大的代码,感谢一百万
评论会员:阿米尔Gerzic 时间:2011/11/30
!欢迎您
有一个很好的!
阿米尔Gerzic

评论会员:mbue 时间:2011/11/30
无用的代码
评论会员:mbue 时间:2011/11/30
!太多的编译器错误
一旦编译崩溃每次。大多数成员没有初始化
正则表达式的结果==零
很多文本(eplanations),但代码是没用的
评论会员:!SonOfPirate 时间:2011/11/30
我印象非常深刻,你的正则表达式内部的知识,并怀疑如果你也许可以帮助我学习如何我们可以比较一下正则表达式模式,以确定是否一个正则表达式是另一个的子集,或者如果它们是等价的。例如,"*"的格局是".*".的一个子集任何方向,资源或见解将赞赏
评论会员:阿米尔Gerzic 时间:2011/11/30

这听起来像是有趣的(非常复杂)问题。我从来没有跑进,poblem,因此,也没有提供任何资源。我最初的想法是要找出如果一个正则表达式字符串是另一个正则表达式字符串的一个"部分"。我会做的比较正则表达式字符串的解析树,然后寻找匹配的子树。如果您发现子树,然后你可以看到字符子集,如"。"是任何其他的字符表达式
等的超集
希望这有助于!
阿米尔

有一个很好的!
阿米尔Gerzic

评论会员:langtugacon 时间:2011/11/30
伟大的教程!
我这篇文章翻译成越南?我们正在做一个关于编译器的excercise,我觉得这是一个很好的的文章,这是很容易理解。
再次感谢^ ^
评论会员:阿米尔Gerzic 时间:2011/11/30
是的,不是一个问题... ...使用它,你的愿望。
很高兴我能帮助!

有一个很好的!
阿米尔Gerzic

评论会员:阿米尔Gerzic 时间:2011/11/30
另外,我也设计一个编译器,可在http://www.amergerzic.com/post/TinyPascal.aspx发现。这篇文章可能会更有帮助。

感谢

有一个很好的!
阿米尔Gerzic

评论会员:米赞拉赫曼 时间:2011/11/30
您好,

我已经发布了一篇文章,代码项目"在C#中的regurlar表达implemenation"


米赞
评论会员:阿米尔Gerzic 时间:2011/11/30
看起来不错,谢谢!

有一个很好的!
阿米尔Gerzic

评论会员:乌戈Moschini 时间:2011/11/30
您好,
这里的网站链接

乌戈Moschini

2008年8月20日,12:17
修改
评论会员:阿米尔Gerzic 时间:2011/11/30
嗯...没有提及原来的工作?

有一个很好的!
阿米尔Gerzic


感谢


感谢
















再次感谢。











最好的问候,
 文章分类
 桌面
 网页开发
 移动开发
 数据库
 多媒体
 编程语言
 平台,框架和库
 编程通用
 图形/设计
 开发周期
 一般阅读
 第三方产品
 作者资源
 其他
快速解答标签
c x 6850
VC x 7405