编译器设计中正则表达式的规则是什么?


有限自动机接受的语言可以用简单的表达式(称为正则表达式)简单地定义。它是一种描述任何语言的有效方法。正则表达式也可以表示为表示字符串的一系列模式。正则表达式用于连接字符串中的字符序列。字符串搜索算法使用此模式来发现字符串上的操作。

正则表达式有各种规则,如下所示:

  • ε 是一个正则表达式。

  • 两个正则表达式R1R2 的并集。

即,R1 + R2R1|R2 也是一个正则表达式。

  • 两个正则表达式R1R2 的连接。

即,R1 R2 也是一个正则表达式。

  • 正则表达式 R 的闭包,即 R* 也是一个正则表达式。

  • 如果 R 是一个正则表达式,则 (R) 也是一个正则表达式。

代数法则

R1|R2=R2|R1 or R1+ R2=R2+ R1 (Commutative)
R1| (R2|R3)=(R1| R2)|R3 (Associative)
Or
R1+ (R2+ R3)=(R1+ R2)+R3
R1 (R2|R3)=(R1R2)R3 (Associative)
R1| (R2|R3)=R1R2| R1R3 (Distributive)
Or
R1 (R2+ R3)=R1R2+R1R3
ε R=R ε=R (Concatenation)

示例1 - 为在 Σ={a,b} 上的以下语言编写正则表达式

  • 长度为零或一的字符串。

答案:ε | a | b 或 (ε+a+b)

  • 长度为二的字符串。

答案:aa | ab | bb 或 (aa+ab+ba+bb)

  • 偶数长度的字符串

答案:(aa|ab|ba|bb)* 或 (aa+ab+ba+bb)*

  • 所有 a 和 b 字符串的集合,至少出现两次 aa。

答案 -(a+b)*aa(a+b)aa(a+b)*

示例2 - 为以下语言查找正则表达式。

  • L={ε,1,11,111,….}
{∴ 10=ε,11=1,12=11,13=111…..}

答案:1*

  • L={ε,11,1111,111111,…..}

答案:(11)

  • L = 0 和 1 的所有字符串集合 = {ε,0,1,01,11,00,000,101,……}

答案:(0+1) 或 (0|1)

  • L = 以 11 结尾的所有 0 和 1 字符串的集合。

答案:(0+1) 11

  • L = 以 0 开头并以 1 结尾的所有 0 和 1 字符串的集合。

答案:0(0+1) 1

示例3 - 编写正则表达式,其中字符串右端第二个字母为 1,其中 Σ={0,1}。

答案:(0+1) 1(0+1)

示例4 - 为在 Σ={a,b} 上的以下语言编写正则表达式

  • L=至少出现一次双字母的字符串集合

答案:(a+b)*(aa+bb)(a+b)*

  • L = 字符串开头和结尾都有双字母的字符串集合。

答案:(aa+bb)(a+b)*(aa+bb)

  • L = 字符串开头或结尾有双字母的字符串集合。

答案:(aa+bb)(a+b)*+ (a+b)*(aa+bb)+(aa+bb)(a+b)*(aa+bb)

更新于:2021年10月26日

4K+ 次查看

启动您的职业生涯

通过完成课程获得认证

开始
广告