正则表达式词法分析

为什么重复的字符串如[wcw | w是a和b的字符串]不能用正则表达式表示？请.给我详细的答案,作为词法分析的新手.谢谢 ...

原始形式的正则表达式描述了常规语言/语法.那些不能包含嵌套结构,因为这些语言可以用简单的有限状态机来描述.简化后你可以想象出语言的每个单词都是从左到右(或从右到左)严格增长,其中重复结构必须明确定义并且是静态的.

这意味着,以前的状态中没有任何信息可以转移到以后的状态(输入中的一些字符).所以,如果你有你的符号W¯¯你不能指定的输入必须具有完全相同的字符串W¯¯的序列中较晚.类似地,你不能确保每个开头的paranthesis也需要一个closin paren(因此正则表达式本身甚至不是常规语言,因此不能用正则表达式来描述:-)).

在理论计算机科学中,我们使用了一组非常有限的正则表达式算子,基本上只包括序列,替代(|)和重复(*),其他一切都可以用这些操作来描述.

但是,通常正则表达式引擎允许将某些子模式分组为匹配,然后可以引用或提取这些匹配.一些引擎甚至允许在搜索表达式字符串本身中使用这样的反向引用,从而允许表达式不仅仅描述常规语言.如果我没记错的话,使用反向引用甚至可以产生不具备上下文的语言.

附加指针:

这个 StackOverflow问题

维基百科