编译器设计中正则表达式的规则是什么?
有限自动机接受的语言可以用简单的表达式(称为正则表达式)简单地定义。它是一种描述任何语言的有效方法。正则表达式也可以表示为表示字符串的一系列模式。正则表达式用于连接字符串中的字符序列。字符串搜索算法使用此模式来发现字符串上的操作。
正则表达式有各种规则,如下所示:
ε 是一个正则表达式。
两个正则表达式R1 和 R2 的并集。
即,R1 + R2 或 R1|R2 也是一个正则表达式。
两个正则表达式R1 和 R2 的连接。
即,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)