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

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

正则表达式有多种规则，如下所示-

ε是正则表达式。

两个正则表达式R1和R2的并集。

即，R1+R2或R1|R2也是一个正则表达式。

两个正则表达式R1和R2的串联。

即，R1R2也是一个正则表达式。

正则表达式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)+R3R1 (R2|R3)=(R1R2)R3 (Associative) R1| (R2|R3)=R1R2| R1R3 (Distributive) Or R1 (R2+ R3)=R1R2+R1R3ε R=R ε=R (Concatenation)

Example1-在$\sum$={a,b}上为以下语言编写正则表达式

长度为零或一的字符串。

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

长度为2的字符串。

答案：aa|AB|bb或(aa+ab+ba+bb)

等长字符串

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

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

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

Example2-查找以下语言的正则表达式。

L={ε,1,11,111,....}

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

答案：1*

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

答案：(11)$\ast$

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

答案：(0+1)$\ast$或(0|1)$\ast$

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

答案：(0+1)$\ast$11

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

答案：0(0+1)$\ast$1

Example3-编写正则表达式，其中从字符串右端的第二个字母是1，其中$\sum$={0,1}。

答案：(0+1)$\ast$1(0+1)

Example4-在$\sum$={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)