编译原理第3章.ppt

1、第三章词汇分析，牙齿章节应介绍编译第一阶段词汇分析的设计原则和设计方法，明确牙齿阶段的任务。理解常见的词语分类和构词规则。使用单词的说明和识别机制。要掌握正则语法、状态、DFA、NFA、正则表达式、正则集的基本概念及其之间的关系。掌握词汇分析程序的手动实现方法。教学目标，3.1有限自动机3.2正则语法和正则集3.3正则语法和有限自动机3.4公式和DFA 3.5 DFA的简化3.6 3.7 3.8词法分析器配置，教学内容，S.P，O.P，(1)分析和识别单词和属性(包括识别)(3)删除注释。(4)进行词汇检查，报告发现的错误。(5)创建符号表。导入课程：词汇分析任务，main()/*ADD*/i

2、nt x=10，y=20，sum总计=x y；词汇分析节目的设计与实现？专门为识别单词而设计的方向性图是设计词汇分析程序的好方法。(1)按照词汇规则写正规语法。(2)将正规语法转换为状态图。(3)将状态图转换为流程图。状态图表，3.1可怜的机器人1。状态图表(补充)，上面定义的方向图表，满足以下条件a .一个或多个初始节点b .具有一些结束节点(也可以为空):c .每个边都标有上面的符号(或)，状态图包括贫困，L(TG)=ab，Bab，babbb，abbb，=a，b，节点表示状态，以圆表示。2.规则语法(左侧线性语法)转换状态图表(集中):教材3.3，针对每个非终止符号的规则(例如Qq)，针对

3、QRq等规则，结束语法起始符号的状态范例3-2:语法gz: zza | aa | bbaba | a Bab为什么？(3分)，贫困的机器人是具有离散输入和输出的数学模型，可以准确地识别正规集。也就是说，识别正规语法中定义的语言和正规表达式中表示的集合，引入穷机器人这一理论。就是找到语法分析程序自动结构的特殊方法和工具。有限自动机将每个元素分为两个茄子类别：deterministic finite automata(DFA)不确定的非deterministic finite automata(NFA)，每个元素称为输入符号q:有限集，每个元素称为状态SK，唯一的初始状态Z K是最终状态集b)=b

4、 (b，a)=a，(b，b)=z，DFA M牙齿可接受的符号字符串的完整记录是L(M)，符号字符串abaab？ 和abab？能被牙齿DFA识别吗？示例3-5指示识别C语言注释/* */的DFA，状态1:注释开始状态。状态2:进入注释正文之前的中间状态。状态3:指示当前在注释正文中的状态。状态4:离开注释前的中间状态。状态5:注释结束状态，即接受状态。，是多值函数，是Q*到Q子集的映射。Q2Q其中，2Q是q的功率集，即q的所有子集的集合。3.1.2不确定的有限自动机(NFA) M=(，Q，S，Z)，有限自动机的不确定性在特定状态下对一个输入字符有多个后续状态。换句话说，状态的转换是不确定的(示例

5、3-；示例3-2采用一般语法标识NFA，gz 3360 z ZA | AA | BB A | ZA | A B AB | BA | B | B，标识符号字符串babbabb的过程3360，当前状态输入字符串其馀部分可能的后续状态选择状态1S BAB ABB这表明，在NFA中，特定状态的转换必须在多个可茄子的后续状态中进行选择。这种不确定性重复认识过程，并影响生产率。，3.1.4从NFA到DFA的等效转换(例如，3-2:=(q，z)，如NFA的矩阵表示中所示，表条目通常由NFA到相应DFA组成的基本思想是，DFA的每个状态对应于NFA的一组状态。NFA的初始状态集S从DFA的初始状态S=，S开始

6、，将遇到输入符号A的后续状态集重复为DFA的新状态，直到不再出现新状态为止。DFA上具有NFA关闭状态的所有状态都是DFA关闭状态。NFA到DFA转换算法(集中)，示例3-2=(Q，Z)，其中s S=，Q=，=a，b Z=，(1 (1)计算蓝色框中的所有状态，直到它们出现在表列中。练习1:样例NFA a a=(Q0，Q1，Q2，a，b，m，Q0，Q1)，m=(Q0，a)=Q1，q2m=(Q0)，常规运算符： (闭包、连接和)，| -或(选择)-连接(可跳过)* -闭包()-括号2。有些a，a是的正则表达式。它表示的正规房子是：a。3.假设U和V的正则表达式，分别用L(e1)和L(e2)表示，则

7、e1|e2、e1e2、E1E2、e1*也是正则表达式，分别表示L(e1) L(e2)。a、b、a | b、ab、示例1:=a、b、正则表达式也是描述单词的重要工具。正则表达式：L()=，L()=，L(a)=a L(a |b)=a，b，l (a b)=ab l ()=，a设置=x，y，描述用正则表达式定义的语言。(1)x(x | y)* x(2)(x | y)*(xx | YY)(x | y)*，性质：设定r，s，t为公式(2)按顺序分解正则表达式的过程是继续添加节点和弧的过程，直到转换图中所有弧的表示成为字母表的元素或元素。3.4正则表达式和NFA，正则表达式和穷机器人在语言上是等效的。a a

8、b a|b，b，、常规集配置P:A A| A: L (A)=，=| N0正则表达式正则集L()=，正则语法，NFA，正则表达式等价DFA中DFA的状态数最小的话，牙齿DFA最简单所有DFA都具有唯一状态最小的等效DFA，最简单的DFA具有不必要的状态和等效状态，3.5 DFA的简化，1冗馀状态定义：从启动状态开始就无法达到。定义死亡状态2，如S1。无法到达结束状态的状态。例如，对于所有输入符号，S2、状态S和T必须转换为S和T的等价状态集，定义三等虚态S和T的等价条件为：终止符号和非终止符号不一定相同。S1和S3等价体，思考：S1和S3等价体，一个字母A，(1)将所有状态分成两个子集。最终状态集和非最终状态集(2)将等效状态组成一个子集。如果每个子集具有连续分割(3)的牙齿，则合并等效状态。关注：机器人的简化(是否具有同等状态)。对于状态Si，Sj B，B，例如，解释：输入字符，状态，状态，表示状态映射的矩阵，(，b)=(，b)=(，b)=(，b)=(，)1，2，3，4=1，2 3，4，3，4=3 4，等价物：所有输入字符都达到集合级别。1、2、3、4=1、2 3 4 5、6、7=5 6、7、1、2、3、4=1、2 3 4 5 6、7、6、3、2单词类型(1)关键字(基本单词，保留字):指已在高级语言中定义的单词，用