《西安电子科技大学《编译原理》课件》由会员分享，可在线阅读，更多相关《西安电子科技大学《编译原理》课件（25页珍藏版）》请在金锄头文库上搜索。
1、1,第二章 词法分析,词法分析： x := y + z * 60.0 ; id1 := id2 + id3 * 60.0 ; 词法的双重含义： 规定单词形成的规则，也被称为构词规则或词法规则。它的作用相当于立法，规定什么样的输入序列是语言所允许的合法单词。 根据构词规则识别输入序列，也被称为词法分析。它的作用相当于执法，根据规则识别出合法的单词和指出非法的输入序列。 本章主要内容： 与词法分析有关的基本概念和相关问题 模式的形式化描述正规式 记号的识别有限自动机（NFA，DFA） 词法分析器的构造从正规式到DFA 上机作业第一部分：函数绘图语言的词法分析器,2,2.1词法分析中的若干问题2.1
2、.1 记号、模式与单词,单词的基本分类： 关键字（保留字） kw(key word) 标识符id(identifier) 字面量literal 特殊符号ks(key symbol, or special symbol),例2.1 语句position := initial + rate * 60 id ks id ks id ks number 注意：称识别出id而不是rate或initial,问题：根据什么识别这些词法的基本单位（词法元素）？,3,2.1.1 记号、模式与单词（续1）,三个术语： 模式（patten）：产生和识别元素的规则 记号（token）：按照某个模式（或规则）识别出的元
3、素（一组） 单词（lexeme）：被识别出的元素自身的值（一个），也称为词值,记号的类别 单词举例 模式的非形式化描述 const(01) const const if(03) if if relation(81) ,= 或=或= id(82) pi,count,D2 字母打头的字母数字串 num(83) 3.1416,0,6.02E23 任何数值常数 literal(84) “core dumped” 双引号之间的任意字符串 Comment x is an integer 括号之间的任意字符串,返回,4,2.1.2 记号的属性,记号是按照某个模式识别出的元素。 再考察赋值句position
4、:= initial + rate * 60 position、initial和rate均为标识符，即它们的种类均是id。 问题：当识别出一个id时，如何判定是哪个id？ 同样，当识别出一个relations时，究竟是=还是 25 由三个记号组成,类别 属性,82 81 83 “mycount” 5 25,记号的类别 单词举例 记号的非形式化描述 if(03) if if relation(81) ,= 或=或= id(82) pi,count,D2 字母打头的字母数字串,注意： 5与25的区别（根据记号的类别） 25与“25”的区别（如何区别？）,5,2.1.3 词法分析器的作用与工作方式,
5、特征： 任务：,编译器中唯一与源程序打交道的部分, 滤掉源程序中的无用成分，如注释、空格、回车等 处理与具体平台有关的输入（如文件结束符的不同表示等） 识别记号，并交给语法分析器。根据模式识别记号 调用符号表管理器或出错处理器，进行相关处理,工作方式： 单独一遍扫描, 作为语法分析器的子程序, 并行方式,6,2.2 模式的形式化描述 2.2.1 字符串与语言,从词法分析的角度看程序设计语言，它是由记号组成的集合。 从本章开始，我们用定义的方式表示一些重要的概念，目的是希望同学们深刻理解并牢固记忆这些基本概念。由于不同的教材（或出版物）对相同的概念有不同的称谓，因此希望同学们掌握概念的实质，而不
6、是死记几个名词术语。,定义2.1 语言L是有限字母表上有限长度字符串的集合。 字母表是组成字符串的所有字符的集合。换句话说，字符串中的所有字符取自字母表。 定义中强调两个有限，因为计算机的表示能力有限 ： 字母表是有限的，即字母表中元素是有限多个； 字符串的长度是有限的，即字符串中字符个数是有限多个。 由于字符串的有序性，使得以字符串作为元素的集合，与一般意义下的集合有所不同，反映在集合运算上，强调了有序。,7,字符串的基本概念（表2.2） 2.2.1 字符串与语言（续1）,表示、术语 |S| S1S2 Sn S的前缀X S的后缀X S的子串X S的真前缀、 真后缀、 真子串 S的子序列X,举
7、例 |abc|= 3 |= 0 “abc”“def”=“abcdef” “abc”3 =“abcabcabc” “abc”的前缀可以是：，a，ab, abc “abc”的前缀可以是：，c，bc, abc “abc”的子串可以是： ，a，b, c, “abc”的真前缀可以是：a，ab ？ ？ “abdf”是“abcdef”的一个子序列（S中去掉0或若干个不一定连续的字符后形成的字符串 ）,8,字符串集合的运算（表2.3） 2.2.1 字符串与语言（续2）,表示、术语 X=LM X=LM X=LM X=L* X=L+,意义 空集合，即元素个数为0的集合 空串作为唯一元素的集合 X是集合L和M的并:
8、 X=s| sL or sM X是集合L和M的交: X=s|sL and sM X是集合L和M的连接: X=st|sL and tM X是集合L的(星)闭包: X=L0L1L2. X是集合L的正闭包: X=L1L2L3.,若 L=a, b, M=c, d 则 LM=ac, bc, ad, bd L*=, a, b, aa, bb, ab, ba, aaa, . L+= a, b, aa, bb, ab, ba, aaa, .,9,2.2.2 正规式与正规集,定义2.2 令是一个有限字母表，则上的正规式及其表示的集合递归定义如下: 1. 是正规式，它表示集合L()= 2. 若a是上的字符，则a是
9、正规式，它表示集合L(a)=a 3. 若正规式r和s分别表示集合L(r)和L(s)，则 （a） r|s是正规式，表示集合L(r)L(s)， （b） rs是正规式，表示集合L(r)L(s)， （c） r*是正规式，表示集合(L(r)*， （d）(r)是正规式，表示的集合仍然是L(r)。（加括弧改变优先级、结合性） 可用正规式描述的语言称为正规语言或正规集。 , 运算的优先级与结合性 若正规式优先级和结合性做下述约定: 1. 三种运算均具有左结合性质； 2. 优先级从高到低顺序排列为: 闭包运算、连接运算、或运算。 则正规式中不必要的括号可以被省略。 例如，(a)|(b)*)(c)可以简化成a|b
10、*c。,10, 正规式的等价 2.2.2 正规式与正规集（续1）,不同算术表达式可以表示同一个数，如3+5、5+3、2+6等均表示8。不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。,定义2.3 若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q。,例2.3 设字母表=a，b，c，则上的部分正规式和正规集如下： 正规式 对应正规集 a，b，c a，b，c a|b , b|a ab=a，b a(a|b)* a，aa，ab，aba，abb，aab，.，a为首的ab字符串 *，a，b，c，aa，ab，ac，ba，bb，bc，abc，.,例2.4 令 L(x)=a，
11、b，L(y)=c，d， 则 L(x|y)=a，b，c，d L(y|x)=a，b，c，d,11, 正规式等价的判定（证明） 2.2.2 正规式与正规集（续2）,正规式的代数性质（表2.4 ） r|s = s|r (rs)t = r(st) r|(s|t) = (r|s)|t r = r = r r(s|t) = rs|rtr* = (r+|) (s|t)r = sr|tr r* = r*,利用正规式的等价性可以化简复杂的正规式。正规式的等价性判定可以采用两种方法： 根据定义，证明不同的正规式表示同一集合（例2.4） 根据下述正规式的代数性质进行运算,12,2.2.3 记号的说明,正规式可以严格地
12、规定记号的模式，用正规式说明记号的公式为： 记号 = 正规式 可以读作为 “（左边）记号定义为（右边）正规式”， 或者 “记号是正规式” 例如 id=a(a|b)* 可以读作为“id定义为a(a|b)* ” 通常在不引起混淆的情况下，也把说明记号的公式简称为正规式，或者规则。,例2.5 记号relation、id和num分别是Pascal的关系运算符、标识 符和无符号数，它们的正规式表示如下所示。,relation = | | = | =,id = (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z |A|B|C|D|E|F|G|H|I|J
13、|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z) (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z |0|1|2|3|4|5|6|7|8|9)*,num = (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* (|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*) (|E(+|-|)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|
14、4|5|6|7|8|9)*),13, 简化正规式描述 2.2.3 记号的说明（续1）,(a) 正闭包 若r是表示L(r)的正规式，则r+是表示(L(r)+的正规式，且下述等式成立: r+ = rr* = r*r，r* = r+| +与*具有相同的运算结合性和优先级 例如： (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* 可以化简为：(0|1|2|3|4|5|6|7|8|9)+,(b) 可缺省 若r是正规式，则r?是表示L(r)的正规式，且下述等式成立: r?=r| ?也可以与*具有相同的运算结合性和优先级 注意：引入算符？的主要目的是为了回避不可以直接通
15、过键盘输入的字符。 例如： E(+|-|) 可以改写为：E(+|-)?,14,2.2.3 记号的说明（续2）,(c) 字符组 若r是仅由|运算构成的正规式，则可改写为r，其中r可以有如下两种形式： 枚举: 如abc，它等价于a|b|c 分段: 如0-9a-z， 它等价于：0123456789abcdefghijklmnopqrstuvwxyz,(d) 非字符组 若r是一个字符组形式的正规式，则r是表示- L(r)的正规式。 例如：若 =a, b, c, d, e, f, g， 则 L(abc) = d, e, f, g , 引入辅助定义 辅助定义的形式与正规式一样，因为它本身也是一个正规式，但
16、它不与任何模式匹配。 换句话说，作为辅助定义的正规式仅供内部使用，而不用于说明记号。,15,2.2.3 记号的说明（续3）,例2.6 引入正规式的缩写形式和辅助定义式后，id和num的正规定义式可重写如下。,char = a-zA-Z digit = 0-9 digits = digit+ optional_fraction = ( . digits )? optional_exponent = ( E (+|-)? digits )?,id = char ( char|digit )* num = digits optional_fraction optional_exponent,对比：,id = (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|
