清华大学编译原理Chapter4PPT课件
- 格式：ppt
- 大小：2.91 MB
- 文档页数：25
下载文档原格式
合集下载
编译原理课件CHAPTER 4(Syntax Analysis-3)
初态是活前缀 ε 的有效项目集 活前缀γ的有效项目集是从初态出发经过γ道路 所到达的那个状态所代表的项目集 分析过程中分析栈中的活前缀的有效项目集是 栈顶状态 Sm 所代表的那个集合，栈顶状态体 现了栈里一切有用的信息
32
2013-9-10
4.5
LR分析
例：文法G’ S’ E E T + E E T T int * T T int T (E)
例： 求 closure ( { E’ ·E } )
E’ E EE+T | T TT*F | F F ( E ) | id
2013-9-10
28
4.5
LR分析
goto 函数
goto ( I, X ) goto ( I, X ) = closure (A→αX·β)，其中 A→α·Xβ在 I 中
0
a
c
B
6 9
8
aAcBe b Ab d
分析句子的过程可以看作在上面这个 DFA 上运 行的过程
13
2013-9-10
例子：
步骤 1 0 栈 输入串 abbcde$ ACTION S2 GOTO
S
1 * 2
b
A c B
4 3
b e
0
a
6
5
d
2013-9-10
7
9
14
8
例子：
步骤 1 2 0 0a2 栈 输入串 abbcde$ bbcde$ ACTION S2 S4 GOTO
例子：
分析句子：abbcde
2013-9-10
6
编译原理课件第四章
中间代码生成的过程和方法
过程
中间代码生成是将源代码转换为中间表示形式的过 程，可以使用三地址码等中间代码表示。
方法
中间代码生成可以应用常见的优化技术，如常量折 叠、公共子表达式消除等。
编译优化的基本原理和技术
基本原理
编译优化的基本原理包括消除冗余、提高并行度和改进数据局部性等。
技术
编译优化的常用技术有指令调度、循环优化和内函数等。
编译原理课件第四章
在这一章中，我们将介绍编译原理课件中的第四章内容。我们将探讨编译器 前端和后端的概念，以及它们各自的任务和流程。
编译器前端和后端
1
编译器后端
2
编译器后端负责中间代码生成、代码优 化和目标代码生成等任务。
编译器前端
编译器前端负责词法分析、语法分析和 语义分析等任务。
语法分析器的作用和原理
1 作用
语法分析器用于分析源代码的语法结构，并生成抽象语法树。
2 原理
语法分析器使用文法规则和语法分析算法进行解析，如LL(1)分析和LR分析。
语法制导翻译的概念和实现
概念
语法制导翻译是在语法分析的同时进行翻译，通过 语法规则和语义动作实现。
实现
语法制导翻译可以使用语义动作和符号表等技术来 实现语义分析和中间代码生成。
编译原理_第4章_第3节_LR分析法63页PPT文档
关键问题
❖ 采用自底向下语法分析方法，在分析过程中的每一步，都会面 对两个关键问题：
（1）如何确定句柄 （2）找出的句柄应规约到哪一个非终结符
解决方法：（移进-规约法） （1）引入一个先进后出的符号栈来存放符号，按照顺序把当前
输入符号入栈（移进），然后查看栈顶符号串是否形成一个句柄。 （2）形成一个句柄时，便对此句柄直接规约，把它代替为相
(s0 s1…sms, #X1X2…Xmai, ai+1…an#)
(2) Action[sm, ai]=rn: {Aβ}，且s=Goto[sm-|β|, A]，则三元式变为：
(s0 s1…sm-|β|s, #X1X2…Xm-|β|A, aiai+1…an#) (3) Action[sm, ai]=acc，宣布接受，三元式不再变化。 (4) Action[sm, ai]=err，报错，三元式不再变化。
A c
d
3
EaA•
Ac•A A•d A•cA
d Ad•
4A c
5
6 AcA•
例：识别acd
状态栈 0 02
024 0245 0246 023
01 0
活前缀栈 当前符号
#
a
#a
c
#ac
d
#acd
#
#acA
#
#aA
#
#E
#
#S
#
输入串 cd# d# #
0
E
S•E E•aA
a
1
SE•
2 Ea•A A•d A•cA
A c
d
3
EaA•
Ac•A A•d A•cA
d Ad•
4A c
5
6 AcA•
❖ 采用自底向下语法分析方法，在分析过程中的每一步，都会面 对两个关键问题：
（1）如何确定句柄 （2）找出的句柄应规约到哪一个非终结符
解决方法：（移进-规约法） （1）引入一个先进后出的符号栈来存放符号，按照顺序把当前
输入符号入栈（移进），然后查看栈顶符号串是否形成一个句柄。 （2）形成一个句柄时，便对此句柄直接规约，把它代替为相
(s0 s1…sms, #X1X2…Xmai, ai+1…an#)
(2) Action[sm, ai]=rn: {Aβ}，且s=Goto[sm-|β|, A]，则三元式变为：
(s0 s1…sm-|β|s, #X1X2…Xm-|β|A, aiai+1…an#) (3) Action[sm, ai]=acc，宣布接受，三元式不再变化。 (4) Action[sm, ai]=err，报错，三元式不再变化。
A c
d
3
EaA•
Ac•A A•d A•cA
d Ad•
4A c
5
6 AcA•
例：识别acd
状态栈 0 02
024 0245 0246 023
01 0
活前缀栈 当前符号
#
a
#a
c
#ac
d
#acd
#
#acA
#
#aA
#
#E
#
#S
#
输入串 cd# d# #
0
E
S•E E•aA
a
1
SE•
2 Ea•A A•d A•cA
A c
d
3
EaA•
Ac•A A•d A•cA
d Ad•
4A c
5
6 AcA•
【编译原理】chap4
∑*上的符号串t被M接受
若t ∑*，f(S，t)=P，其中S为 M的开始状态，P Z，Z为终态集。
则称t为DFA M所接受(识别)。
符号串t被DFA M接受的示例
例：证明t=baab被例的DFA所接受。
f(S,baab)=f(f(S,b),aab)=f(V,aab)
=f(f(V,a),ab)=f(U,ab)=f(f(U,a),b)
NFA确定化的方法
假设NFA N=(K, ,f,K0,Kt)可按如下办法构造一个DFA M=(S, ,d,S0,St)，使得L(M)=L(N)： 1.M的状态集S由K的一些子集组成。用[S1 S2... Sj]表示S的 元素，其中S1, S2,,... Sj是K的状态。并且约定，状态S1, S2,,... Sj是按某种规则排列的，即对于子集{S1, S2}={ S2, S1,}来说，S的状态就是[S1 S2]； 2.M和N的输入字母表是相同的，即是； 3.转换函数是这样定义的： d([S1 S2,... Sj],a)= [R1R2... Rt] 其中 {R1,R2,... , Rt} = closure(move({S1, S2,,... Sj},a)) 4.S0=-closure(K0)为M的开始状态； 5.St={[Si Sk... Se]，其中[Si Sk... Se]S且{Si , Sk,,... Se}Kt}
=f(Q,b)=Q
Q属于终态。 得证。
a S b
b
U a
a
a,b Q b
V
DFA的结论
DFA M所能接受的符号串的全体记为L(M) 结论：
上一个符号串集V是正规的，当且仅当 存在一个上的确定有穷自动机M，使得
编译原理课件PPT 第4章
CHAPTER 4 Syntax ANALYSIS Section 2 TOP-DOWN PARSING 1、Ideas of top-down parsing – Find a leftmost derivation for an input string – Construct a parse tree for the input starting from the root and creating the nodes of the parse tree in preorder.
3、Parsing methods – Universal parsing method • Too inefficient to use in production compilers – TOP-DOWN method • Build parse trees from the top(root) to the bottom(leaves) • The input is scanned from left to right • LL(1) grammars (often implemented by hand) – BOTTOM-UP method • Start from the leaves and work up to the root • The input is scanned from left to right • LR grammars(often constructed by automated tools)
CHAPTER 4 Syntax ANALYSIS Section 0 Approaches to implement a Syntax analyzer 1、The syntax description of programming language constructs – Context-free grammars – BNF(Backus Naur Form) notation Notes: Grammars offer significant advantages to both language designers and compiler writers
编译原理课件chapter4
三地址代码的生成
总结词
三地址代码是一种常见的中间代码形式，它由一系列的三元 式组成，每个三元式包含一个操作符和两个操作数。
详细描述
三地址代码的生成是编译过程中的一个重要步骤，它通过对 源代码进行语法分析和语义分析，将高级语言转换为一系列 的三元式。这些三元式表示了源代码中的运算和数据传输操 作，可以进一步转换为目标代码。
常见的寄存器分配算法包括基于 图的方法、线性扫描算法和遗传
算法等。
目标代码的生成
01
02
03
04
目标代码的生成通常涉及指令 选择、指令调度和代码优化等
步骤。
指令选择是根据中间代码选择 合适的目标指令的过程，需要 考虑指令集架构、语义等约束
。
指令调度是为了确定指令的执 行顺序，以充分利用处理器资
源并提高指令级并行度。
为了能够处理连续输入的字符流，词 法分析器需要使用一个输入缓冲区来 存储尚未处理的字符。
设计状态转换图
根据正则表达式的规则，可以设计出 一个状态转换图，用于描述如何将输 入的字符转换为相应的词法单元。
词法分析器的实现
编写词法分析器程序
根据状态转换图和输入缓冲区的处理 逻辑，可以编写出相应的词法分析器 程序。
循环展开
将循环体多次执行，减 少循环次数，提高程序
运行效率。
循环优化
通过优化循环结构，减 少循环次数，提高程序
运行效率。
函数内联
将函数调用替换为函数 体中的代码，减少函数
调用的开销。
循环优化
01
02
03
04
循环展开
将循环体多次执行，减少循环 次数，提高程序运行效率。
循环合并
将多个循环合并为一个循环， 减少循环次数，提高程序运行
编译原理第4章PPT课件
2、主旨：对任何输入串，试图用一切可能的 办法，从开始符号出发，自上而下 地为输入串建立一棵语法树。
4
§4.2自上而下面临的问题
二、举例： 自上而下方法的分析过程本质上
是一种试探过程，是反复使用不同产生 式谋求匹配输入串的过程。
5
§4.பைடு நூலகம்自上而下面临的问题
例：文法 SxAy A**|*
输入串α :x*y
（１）把文法Ｇ的所有ＶＮ按任一种顺序排列成 P1,P2,…,Pn;按此顺序执行； （２）FOR i = 1 To n Do
Begin For j :=1 To i-1 Do 把形如PiPjγ的规则改写成 Piδ1γ|δ2γ|…|δkγ 其中Pjδ1|δ2|…|δk是关 于Pj的所有规则； 消除关于Pi规则的直接左递归性
Ｆ Ｔ’ + T
iℇ
Ｅ’ ℇ
F（E） ｜i
F
Ｔ’
输入串：ｉ＋ｉ； 如右图所示
ｉ
ℇ
19
§4.３LL(1)分析法
２、由上分析是不是就意味着：当非终结符 Ａ面临输入符号ａ，且ａ不属于Ａ的任意候 选首符集，但Ａ的某个候选首符集包含ℇ时， 就一定可以使Ａ自动匹配？
分析：只有当ａ是在文法的某个句型中允许跟在Ａ 后的终结符时，才可能允许Ａ自动匹配，否则，ａ 在这里的出现是一种语法错误。
14
§4.３LL(1)分析法
２、当不得回溯时，对文法有什么要求？
∀ 非终结符Ａ的各个候选的首符集的交集均为空。
分析：Ａα
first(α)={a|α⇒* a…,a∈ VT} 若α⇒* ℇ ,则规定ℇ∈ first(α)
即:first(α)是α的所有可能推导的开头终结符或可能
的ℇ。
此时，当要求A匹配输入串时，A根据它所面临的第
4
§4.2自上而下面临的问题
二、举例： 自上而下方法的分析过程本质上
是一种试探过程，是反复使用不同产生 式谋求匹配输入串的过程。
5
§4.பைடு நூலகம்自上而下面临的问题
例：文法 SxAy A**|*
输入串α :x*y
（１）把文法Ｇ的所有ＶＮ按任一种顺序排列成 P1,P2,…,Pn;按此顺序执行； （２）FOR i = 1 To n Do
Begin For j :=1 To i-1 Do 把形如PiPjγ的规则改写成 Piδ1γ|δ2γ|…|δkγ 其中Pjδ1|δ2|…|δk是关 于Pj的所有规则； 消除关于Pi规则的直接左递归性
Ｆ Ｔ’ + T
iℇ
Ｅ’ ℇ
F（E） ｜i
F
Ｔ’
输入串：ｉ＋ｉ； 如右图所示
ｉ
ℇ
19
§4.３LL(1)分析法
２、由上分析是不是就意味着：当非终结符 Ａ面临输入符号ａ，且ａ不属于Ａ的任意候 选首符集，但Ａ的某个候选首符集包含ℇ时， 就一定可以使Ａ自动匹配？
分析：只有当ａ是在文法的某个句型中允许跟在Ａ 后的终结符时，才可能允许Ａ自动匹配，否则，ａ 在这里的出现是一种语法错误。
14
§4.３LL(1)分析法
２、当不得回溯时，对文法有什么要求？
∀ 非终结符Ａ的各个候选的首符集的交集均为空。
分析：Ａα
first(α)={a|α⇒* a…,a∈ VT} 若α⇒* ℇ ,则规定ℇ∈ first(α)
即:first(α)是α的所有可能推导的开头终结符或可能
的ℇ。
此时，当要求A匹配输入串时，A根据它所面临的第
编译原理 Chapter 4
expression expression + term expression expression – term expression term term term * factor term term / factor term factor factor ( expression ) factor id
码生成 支持语言的演化和迭代
3
语法分析器的作用
• 基本作用
– 从词法分析器获得词法单元的序列，确认该序列是否 可以由语言的文法生成
– 对于语法错误的程序，报告错误信息 – 对于语法正确的程序，生成语法分析树 (简称语法树)
• 通常并不真的生产这棵语法分析树
4
语法分析器的分类
• 通用语法分析器
– 可以对任意文法进行语法分析 – 效率很低，不适合用于编表示形式
– 根结点的标号时文法的开始符号 – 每个叶子结点的标号是非终结符号、终结符号或ε – 每个内部结点的标号是非终结符号 – 每个内部结点表示某个产生式的一次应用
• 内部结点的标号为产生式头，结点的子结点从左到右是产生 式的体
• 树的叶子组成的序列是根的文法符号的一个句型 • 一棵语法分析树可对应多个推导序列，但每颗分
18
词法分析和语法分析的比较
阶段
输入
输出
描述体系
词法分析 源程序符号串 词法单元序列 正则表达式
语法分析 词法单元序列 语法树 上下文无关文法
19
上下文无关文法和正则表达式 (1)
• 上下文无关文法比正则表达式的能力更强
– 所有的正则语言都可以使用文法描述 – 但是一些用文法描述的语言不能用正则表达式描述
| other open_stmt if expr then stmt
码生成 支持语言的演化和迭代
3
语法分析器的作用
• 基本作用
– 从词法分析器获得词法单元的序列，确认该序列是否 可以由语言的文法生成
– 对于语法错误的程序，报告错误信息 – 对于语法正确的程序，生成语法分析树 (简称语法树)
• 通常并不真的生产这棵语法分析树
4
语法分析器的分类
• 通用语法分析器
– 可以对任意文法进行语法分析 – 效率很低，不适合用于编表示形式
– 根结点的标号时文法的开始符号 – 每个叶子结点的标号是非终结符号、终结符号或ε – 每个内部结点的标号是非终结符号 – 每个内部结点表示某个产生式的一次应用
• 内部结点的标号为产生式头，结点的子结点从左到右是产生 式的体
• 树的叶子组成的序列是根的文法符号的一个句型 • 一棵语法分析树可对应多个推导序列，但每颗分
18
词法分析和语法分析的比较
阶段
输入
输出
描述体系
词法分析 源程序符号串 词法单元序列 正则表达式
语法分析 词法单元序列 语法树 上下文无关文法
19
上下文无关文法和正则表达式 (1)
• 上下文无关文法比正则表达式的能力更强
– 所有的正则语言都可以使用文法描述 – 但是一些用文法描述的语言不能用正则表达式描述
| other open_stmt if expr then stmt
编译原理---第4章_新
国家精品课程
30
——《编译原理》
三、重要问题——提取左因子
将形如
A→αβ1|αβ2|…|αβm |γ1|γ2|… | γp
的规则改写为
A→αA' |γ1|γ2|… | γp和 A'→β1|β2|…|βm
❖结果：
▪S→ if E then SS’|other ▪S'→ε|else S
S
x
A
y
国家精品课程
13
——《编译原理》
E→E+E | E-E | E*E | E/E | (E) | id
二、重要概念回顾
EE+E
❖推导: αＡβαγβ (依据:Ａ→γ)
a1+E
❖最左(Left-most)推导——最左分析
▪ 左句型 ▪ 最左推导对应最右归约
a1+E*E a1+a2*E a1+a2*a3
❖ 最右(Right-most)推导——最右分析 EE+E
规范推导、规范句型(右句型)
E+E*E
最右推导对应最左归约(规范归约) E+E*a3
❖ 二义性(先天二义性语言、二义性文法) E+a2*a3 a1+a2*a3
国家精品课程
——《编译原理》
三、重要问题——虚假匹配
国家精品课程
27
——《编译原理》
消除左递归的一般方法
❖对产生式组
▪ A→Aα1|Aα2|…|Aαn|β1|β2|…|βm
❖用如下产生式组替换
▪ Aβ1 B|β2 B |…|βm B ▪ Bα1 B|α2 B |…|αn B|ε ▪ 其中：B为新变量，相当于A’
精品课件-编译原理(第四版)-第4章
我们再举一例说明属性文法。一简单变量类型说明的文法G[D] 如下：
G[D]：D→int L∣float L
L→L, id∣id
其对应的属性文法为
（1）D→TL
L.in=T.type
（2）T→int
T.type=int
（3）T→float
T.type=float
（4）L→L(1)，id L(1).in=L.in; addtype ( id.entry, L.in )
（1）赋值语句：左部 表达式
（2）条件语句：表达式 语句1 语句2
与抽象语法相对应的语法树称为抽象语法树或抽象树， 如赋值语句x=a−b*c的抽象语法树如图4-4(a) 所示，而图4-4(b) 则是该赋值语句的普通语法树。
图4–4 x=a−b*c的语法树
(a) 抽象语法树；(b) 普通语法树 图
语义栈 _ __ _7 _7_ _7_ _ _7_9 _7_9_ _7_9_ _ _7_9_5 _7_45 _52
输入串 7＋9*5#
＋9*5# ＋9*5#
9*5# *5# *5# 5# # # # #
主要动作 s3 r4 s4 s3 r4 s5 s3 r4 r2 r1 acc
Hale Waihona Puke 4.2 属 性 文 法一个源程序经过词法分析、语法分析之后，表明该源程序 在书写上是正确的，并且符合程序语言所规定的语法。但是语 法分析并未对程序内部的逻辑含义加以分析，因此编译程序接 下来的工作是语义分析，即审查每个语法成分的静态语义。如 果静态语义正确，则生成与该语言成分等效的中间代码，或者 直接生成目标代码。直接生成机器语言或汇编语言形式的目标 代码的优点是编译时间短且无需中间代码到目标代码的翻译， 而中间代码的优点是使编译结构在逻辑上更为简单明确，特别 是使目标代码的优化比较容易实现。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
f
a
b
-0 1 2
132
213
+3 3 3
状态转换表的行标表示状态，列标表示输入 符号，表元素表示f(W,a)的值。
19
定义4.6 字母表V上的状态图SG是如下有向图：
(1)至少有一个初始结点，用“－”标记； (2)至少有一个终止结点，用“＋”标记；
确定，可全体编为一类，称作“一字一类”） ②标识符：用户定义的常量名、变量名、过程名和
类型名（个数不确定，作为一类，称作“一符一 类”） ③常量：12,1997,4.14,‘A’,‘scnu’等（个数不 确定，按类型分类） ④运算符 ＋,－,＊,／, >,>=,<,<=,#等（个数 确定，“一符一类”） ⑤界限符 ；,（）等（个数确定，“一符一类”）
5
词法分析程序输出的单词符号通常用二元式 表示：（单词种别，单词自身的值）
单词种别：表示单词种类，常用整数编码， 它是语法分析需要的 单词自身的值：是编译中其他阶段所需要 的信息
6
(4)词法分析程序的设计过程
3G 3型文法 RE 正则表达式
3G RE
SG 状态图 εFA ε确定自动机
εDFA
εNFA ε非确定自动机
A→0S|1A|ε A=ε+0S+1A ② 解:
17
4.3 有穷自动机(FA)
(1)确定有穷自动机（DFA） 定义4.5 一个确定有限自动机(DFA)M是一个五元 组：M=(K,VT,f,S,Z) 其中 K：有穷状态集； VT：有穷的输入字母表； f：K×VT→K是状态转换函数，即f(W,a)=U
(ba)*b ={(ba)nb|n≥0} b(ab)* =(ba)*b
11
定理4.1 对正则式P,Q,R，以下关系成立：
(1) P|Q=Q|P
“或”交换律
(2) P|(Q|R)=(P|Q)|R “或”结合律
(3) P(QR)=(PQ)R
“联结”结合律
(4) P(Q|R)=PQ|PR “联结 ”对“或” 的左分配律
3
(2)实现方式
①相对独立方式
Token
源程序
词法分析程序
语法分析程序 ….
get token
②完全独立方式
属性字序列
源程序
词法分析程序
语法分析程序….
4
(3)单词类别及其输出形式 单词可作各种分类，典型地分为５类： ① 保 留 字 ： AND,BEGIN,FOR,TYPE,VAR 等 （ 个 数
FA 确定自动机 NFA 非确定自动机 minFA 最小确定自动机
DFA minDFA
Scanner 扫描器
Scanner
SG εNFA NFA
7
4.2 正则表达式(正则式)和 正则集(正则语言)
(1)正规式和正规集 定义4.1（正则式和正则集） 在字母表V上定义的正则式及其描述的正则 集递归地定义如下：
第四章 词法分析
1
4.1 词法分析程序的设计
(1)任务 ①主要任务 逐个字符地扫描源程序，识别单词符号 （终结符）。在拼单词时作词法检查。每 识别出一个单词，就翻译成相应的机内表 示（语法分析时的终结符）。
2
②删去注解、空格、续行符等 ③插入某些信息
有些语言（如FORTRAN）无语句结束符 “；”，就要插入句末符。 为了语法分析出错处理的错误定位，要为 源程序增加行号（在列表文件中可见）。 ④输出源程序清单
(5) (Q|R)P=QP|RP “联结 ”对“或” 的右分配律
(6) εP=Pε=P
(7) ΦP=PΦ=Φ Φ|P=P|Φ=P
12
(2) 由正则文法构造正则式(3G->RE) 定理4.2 正则文法规则
U→a1W1|a2W2|…|anWn|b1|b2|…|bm 的等价正则式方程为其中
U=(b1+b2+…+bm)+a1W1+a2W2+…+anWn 其中Wi是正则变量
其中，aij是正则式，但不含变量； Xi是正则变量（待定正则式）。
15
例：对文法G: S→aA A→bS | a 用正则式来描述文法定义的语言： 解: 根据定理4.2 S=aA ①
A=a+bS ② 把②式代入①式， S = a(a+bS)
= aa+abS 根据定理4.3 S=(ab)*ab
16
例：对正则文法G建立正则式方程： G:S→0A|0|1 S =(0+1)+0A ①
(1)Φ是正则式，表示空集； (2)ε是正则式，表示{ε}； (3)每个a∈V是正则式，表示｛a｝；
8
(4) 若P和Q是正则式，分别表示正则集L(P) 和L(Q)，则
①P|Q是正则式，表示L(P)∪L(Q) “或”
②PQ是正则式，表示L(P)L(Q) “联结”
③P*是正则式上的全体整数
例：PASCAL的无符号实数的正则式： d* (.dd*|ε)(E(+|-|ε)dd*|ε) (d为0-9中的数字) 在前面加上(+|-|ε)后，就是符号实数的定义。
10
定义4.2 对正则式P和Q，若L(P)＝L(Q)， 则P与Q等价，记为P=Q。 例： b(ab)* ={b(ab)n|n≥0}
表示当前状态W下，输入a时，转到状态U。 S：唯一的开始状态，S∈K; Z：终止状态集，是K的非空子集。
18
例：设有M1=({0,1,2,3},{a,b},f,0,{3}),
其中：
f(0,a)=1 f(1,a)=3 f(2,a)=1 f(3,a)=3
f(0,b)=2 f(1,b)=2 f(2,b)=3 f(3,b)=3
13
定理4.3 设X是正则变量，a和b是正则 式，且X=aX+b 则 X=a*b。
若X=Xb+a 则 X=ab*。 证：由定理4.2，正则式方程X=aX+b等 价于以下正则规则：X→aX|b 其定义的语言和正则式a*b一样，同为：
{anb|n>=0}
14
定义4.4 n元正则式方程组的标准形式： X1=a10+a11X1+a12X2+ … +a1nXn X2=a20+a21X1+a22X2+ … +a2nXn …… Xn=an0+an1X1+an2X2+ … +annXn
④(P)是正则式，表示L(P)
(5) 仅由有限次使用上述步骤得到的正则式，
才是V上的正则式。运算的优先次序为：* .
|(其中“|”可写作“+”)。
9
例：设V={a,b,0,1}, 则
(a|b)(0|1)
{a0,a1,b0,b1}
(a|b)(a|b|0|1)* 表示V上的全体标识符
(0|1)(0|1)*