《词法分析江西师大计算机课件.》由会员分享，可在线阅读，更多相关《词法分析江西师大计算机课件.（82页珍藏版）》请在金锄头文库上搜索。
1、第三章 词法分析 3.1 词法分析器的作用 3.2 词法单元的规约 3.3 词法单元的识别 3.5 有穷自动机 3.6 从正则表达式到自动机 1 3.1 词法分析 l主要任务是读入源程序的输入字符、将 它们组成单词，生成并输出一个词法单元 序列，每个词法单元对应于一个单词。 词法分析程序的其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开， 2 词法单元由一个词法单元名和一个可选 的属性值组成。 模式描述了一个词法单元的单词可能具 有形式。 单词是源程序中的一个字符序列，它和 某个词法单元的模式匹配，并被词法分 析器识别为该词法单元的一个实例。 包括保留字、标识符、
2、运 算符、标点符号和常量等 。 3 词法分析器通常还要和符号表进行交互 。当词法分析器发现了一个标识符的单 词时，它将此单词添加到符号表中。 在某种情况下，词法分析器会从符号表 中读取有关标识符种类的信息，以确定 向语法分析器传送哪个词法单元。 4 符号表：是一种供编译器用于保存有关源 程序构造的各种信息的数据结构。 这些信息在编译器的分析阶段被逐步收集 并放入符号表，它们在综合阶段用于生成 目标代码。 符号表的每个条目中包含与一个标识符相 关的信息，比如它们的字符串，类型、存 储位置和其他相关信息。 5 6 词法分析是编译过程中的一个阶段， 在语法分析前进行 。也可以和语法分 析结合在一起作
3、为一遍，由语法分析 程序调用词法分析程序来获得当前单词 供语法分析使用。 7 单词的描述工具-正则表达式 单词的识别系统-有穷自动机 设计词法分析程序 8 3.2 词法单元的规约 串和语言 字母表：一个有限的符号集合。 串：是该字母表中符号的一个有穷序列。 语言：是某个给定字母表上一个任意的可数 的串集合。 空集 和仅包含空串的集合 都是语言。 9 串的相关术语 串s的长度：记为|s|,指s中符号出现的 次数。 串s的前缀：从s的尾部删除0个或多个符 号后得到的串。 串s的后缀：从s的开始删除0个或多个符 号后得到的串。 串s的子串：删除s的某个前缀和某个后 缀之后得到的串。 10 串s的真前
4、缀、真后缀、真子串分别是s的 既不等于 ，也不等于s本身的前缀、后 缀和子串。 串s的子序列：从s中删除0个或多个符号 后得到的串，这些被删除的符号可能不相 邻。如：baan是banana的一个子序列。 11 相关运算 串的连接运算:xy 空串是连接运算的单位元： 符号串集合的乘积： 例：符号串集合A=ab,aa;B=ba,bb; 乘积AB=abba,abbb,aaba,aabb 12 例：x=ab 串的方幂运算 ： 例：A=a,b,cd,B=bc,ad,则 13 （自反）闭包：*称为的闭包，若*表示上的 所有有穷长的串的集合，可表示为：（其中用U代 表逻辑或运算） 正闭包：+称为的正闭包，可
5、表示为 例： =a,b +=a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,ba b,bba,bbb,. *= U + 14 语言是由句子组成的集合，是由一组符 号所构成的集合。字母表上的一个语 言是上的一些符号串的集合 (字母表 上的每个语言是* 的一个子集)。 集合B=a,aa,aaa, 是字母表上的一个语言 或记作w|w*且w=an,n1 例： =a,b 15 有关语言的运算 是一个语言。 即 是一个语言。 设L是（上的）一个语言,M是（上的）一个语言， 则语言L和M的并，交，差，补是一个语言。 A.语言L和M的并表示为 LM，是一个语言，满 足: w|w is
6、in L or is in M 如： L1 =a,b,y,z M1 =1,28,9 L1M1 =a,b, y,z，1,28,9 16 B.语言L和M的连接是一个语言，记为 LM=st |sL且 tM 如： L1M1 =a1,b1,y1,z1,a2,b2a9z9 有L = L=L C. L的n次连接Ln= LL.L D. 语言L的闭包记为 L* L* = L0 L1 L2 . L0= ， Ln = L Ln-1 = Ln-1 L,n1 17 如：（L1M1）* =a,b, y,z，1,28,9 ，a,1a,xyz,6789st E. 语言L的正闭包记为 L+， L+= L1 L2 L3 . L+
7、 = LL* = L*L L* = L+ 18 例令L表示字母表A，B，,Z,a,b,z,令D 表示数位的字母表0，1，9，也可把L和D 看成所有串长度为1的语言。 LUD是字母和数位的集合。也可是说是包 含62个长度为1的串组成的语言。 LD： L4： L*： L（LUD）*： D+： 19 有穷自动机（FA） 自动机：按一定步骤识别每个字符的算法。 有穷自动机作为一种识别装置，它能准确地识 别正规集，即识别正规式所表示的集合.应用 有穷自动机这个理论，为词法分析程序的自动 构造寻找有效的方法和工具。 确定有穷自动机DFA（P40） 不确定有穷自动机NFA （P42） 20 确定的有穷自动机
8、DFA DFA定义： 一个确定的有穷自动机（DFA）M是一个五 元组：M=（K，f，S，Z）其中 1.K是一个有穷集，它的每个元素称为一个状 态； 2.是一个有穷字母表，它的每个元素称为 一个输入符号，所以也称为输入符号表； 21 DFA定义 3.f是转换函数，是在KK上的映射，即， 如 f（ki，a）=kj，（kiK，kjK）就 意味着，当前状态为ki，输入符为a时，将转 换为下一个状态kj，我们把kj称作ki的一个后 继状态； 4.SK是唯一的一个初态； 5.Z K是一个终态集，终态也称可接受状态 或结束状态。 22 一个DFA 的例子： DFA M=（S，U，V，Q，a，b，f，S， Q
9、）其中f定义为： f（S，a）=Uf（V，a）=U f（S，b）=Vf（V，b）=Q f（U，a）=Qf（Q，a）=Q f（U，b）=Vf（Q，b）=Q 23 DFA 的状态图表示 l 一个DFA可以表示成一个状态图 (或称状 态转换图)。 l假定DFA M含有m个状态，n个输入字符； l那么这个状态图含有m个结点，每个结点最 多有n个弧射出； l整个图含有唯一一个初态结点和若干个终 态结点； l初态结点冠以箭头“ ”；终态结点用双圈 表示； l若 f(ki,a)=kj，则从状态结点ki到状态结点 kj画标记为a的弧； 24 状态 转换边 接受(终止)状态 开始状态 25 判断字符串abaab
10、b,babb是否 能被接受？ 26 例1:确定有限自动机dfa1表示所有正整数的集合。 符号集 = 0,1,2,.,9 ； 状态集合SS= S0 , S1 ； 开始状态 S0； 转换函数:SS SS；(S0 ,d) = S1,(S1 ,d)= S1，其中d ； 终止(接受)状态集: S1 ； d d 确定有穷自动机dfa1的状态转换图表示 S0 S 1 27 例2： 实数可表示为d1d2.dn . d1d2.dm 。 d d . d d 确定有限自动机状态转换图 2 1 03 28 例3：接受第二个位置上的数字为2的所有正整数 的确定有穷自动机dfa2(包括所有一位的)。 d 2 d 图 确定
11、有穷自动机dfa2 29 例3：考虑可带下划线的标识符集IDE， 其中L表示字母，D表示数字。 _ L,D L,D L 确定有限自动机dfa3 30 DFA 的矩阵表示 一个DFA还可以用一个矩阵表示，该 矩阵的行表示状态，列表示输入字符， 矩阵元素表示相应状态行和输入字符列 下的新状态，即k行a列为f(k,a)的值。 字符 状态 31 32 不确定的有穷自动机NFA 一个不确定的有穷自动机（NFA）M是一个五 元组：M=（K，f，S，Z） 有输入 上的转换动作； S1 S2 对每个状态s和每个输入符号a,可以有多条标号 为a的边离开。 S3 S1 S2 aa 33 34 有穷自动机A所能接受
12、的字符串集L(A) L(A)=| S00 Si* ， Si* F 特例：空字符串集 35 从NFA到DFA的转换 DFA是NFA的特例.对每个NFA N一定 存在一个DFA ，使得 L(M)=L(N)。 对每个NFA N存在着与之等价的DFA M 。 有一种算法，将NFA转换成接受同样语言 的DFA.这种算法称为子集法(造表法）. 与某一NFA等价的DFA不唯一. 36 空移环路的寻找和消除 37 38 NFA到DFA的构造思想是该DFA的每一 个状态对应NFA的一组状态，该DFA使 用它的状态去记录在NFA读入一个输入 符号后可能达到的所有状态。 39 S表示N的单个状态，而T表示N的一个状
13、态 集 40 I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2； move(1,2,a)=5,3,4 -closure(5,3,4)=2,3,4,5,6,7,8； 12 5 3 4 6 8 7 a a a 41 4 f 3 5621i a a a a b b bb 42 等价的DFA a C DB AE F S b a a a a a b b b b b a b F 43 44 最小化DFA 从任意一个接受相同语言的DFA出发， 通过分组合并等价的状态，我们总是可 以构建得到这个状态数最少的DFA。 如果分别从状态s和t出发，沿着标号为x 的路径到达的两
14、个状态中只有一个是接 受状态，我们就说串x区分状态s和t。 如果存在某个能够区分状态s和状态t的 串，那么它们就是可区分的。 45 工作原理 将一个DFA的状态集合分划成多个组， 每个组中的各个状态之间相互不可区分 。 分割法 46 DFA的最小化算法 DFA M =（K,f, k0, kt),最小状态DFA M 1.构造状态的一初始划分： 终态kt 和非终态K- kt两组(group) 2.对施用过程如图构造新划分new 47 3. 如new =,则令 final= 并 继续步骤4，否则:=new重复2 . 4.为final中的每一组选一代表，这 些代表构成M的状态。若k是一代表 且f(k,
15、a)=t,令r是t组的代表，则M 中有一转换f(k,a)=r M 的开始状态是含有S0的那组的代 表 M 的终态是含有F的那组的代表 48 49 首先将M的状态分成两个子集：一个由终态(可接 受态)组成，一个由非终态组成，这个初始划分P0 为：P0=(1，2，3，4，5，6，7)，显然第一 个子集中的任何状态都与第二个子集中的任何状 态不等价。 P1=(1，23，45，6，7) P2=(1，2，3，4，5，6，7) P3=(1，2，3，4，5，6，7) 50 C和D同是终态,读入a到达C和F, C和F 同是终态, C和F读入a都到达C,读入b都到 达E. C和D等价 a C DB AE F S b a a a a a b b b b b a b F 51 0:S,A,B
