[工程科技]编译原理词法分析第3章.ppt

第三章 词法分析 主要内容: 词法分析程序功能 单词符号及输出单词的形式 语言单词符号的两种定义方式 正规式与有穷自动机 正规文法与有穷自动机 词法分析程序的编写方法 3.1 词法分析程序的功能 词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。 词法分析程序,又称词法分析器(Lexical Analyzer); 又称扫描器(Scanner);执行词法分析的程序. 3.2 单词符号及输出单词的形式 3.2.1 语言的单词符号 功能:输入字符串源程序、输出单词符号 单词符号的种类： 关键字，也称基本字：如 if，else，while? 标识符——表示各种名字：如变量名、数组名和函数名等 常数：各种类型的常数 运算符：+，-，*，/，? 界符：逗号、分号、括号和空白 3.2.2 词法分析程序输出单词的形式 例 if(a1)b=100 输出单词符号： 逻辑if (2，-) 左括号 (29，-) 标识符a (10， ‘a’) 号 (23，-) 整常数1 (11， ‘1’的二进制) 右括号 (30，-) 标识符b (10，‘b’) 赋值号= (17，-) 整常数100 (11， ‘100’的二进制) 界符; (26，-) 3.3 语言单词符号的两种定义方式 正规表达式是一种表示法，它可以表示单词符号的结构，从而精确定义单词符号集。正规表达式简称正规式，它表示的集合为正规集。 程序语言中使用的标识符是一个字母开头的字母数字串 如果字母用l表示，数字用d表示，那么标识符就可以表示为：l (l|d)* 其中l与(l|d)*的并表示两者的连接，括号中表示l或d，*表示零次或多次引用*号所标记的表达式， 因此(l|d)*是l|d的0次或n次并置，表示一长度为0,1,2,…的字母数字串 因此l (l|d)*表示字母开头的字母数字串，也即标识符集，l (l|d)*是表示标识符的正规式，标识符集便是这个正规式表示的正规集。 3.3.1 正规式和正规集 正规集可以用正规表达式（简称正规式）表示。 正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。 正规式和正规集的递归定义： 对给定的字母表? 1)? 和?都是?上的正规式，它们所表示的正规集为{?}和?; 2) 任何a?? ，a是?上的正规式，它所表示的正规集为{a} ; 3) 假定e1和e2都是?上的正规式，它们所表示的正规集为L(e1)和L(e2)，则 i) (e1|e2)为正规式，它所表示的正规集为L(e1)?L(e2)， ii) (e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)， iii) (e1)*为正规式，它所表示的正规集为(L(e1))*， 仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式表示的字集才是?上的正规集。 正规式间的运算“|”为或，“·”为连接，通常它可省略，“*”为闭包, 括号是为了限定运算次序。 如果规定*优先于·,·优先于|，括号省略后不会引起混淆，正规式便可以更简洁. [例] 设Σ={a,b,c},则 (a|((b)*c))是一正规式， (b)*是正规式， ((b)*c)是正规式， (a|((b)*c))是正规式，省去括号后，正规式为a|b*c。它的正规集L(a|b*c)=L(a)∪L(b*c)=L(a)∪L(b) *L(c) =L(a)∪L (b) *L(c)={a}∪{b}*{c} ={a}∪{,b,bb,…}{c}={a,c,bc,bbc,…} [例] Σ={a,b}，则R=a(a|b)* 是Σ上的正规式它表示的正规集： L(R)=L(a(a|b)*) =L(a)L((a|b)*) =L(a)(L(a|b))* =L(a)(L(a)∪L(b))* ={a}({a}∪{b})* ={a}{a,b}* ={a}{ε,a,b,aa,ab,ba,bb,aaa,…} ={a,aa,ab,aaa,aab,aba,abb,aaaa,…} 即为Σ上a开头的字符串集。 [例] Σ={a,b,0,1}，则R=(a|b)(a|b|0|1)*正规式，它表示的正规集: L(R)=L((a|b)(a|b|0|1)*) =L(a|b)(L(a|b|0|1))* =L(a)∪L(b))(L(a)∪L(b)∪L(0)∪L(1))* ={a,b}{a,b,0,1}* 是Σ上a,b开头的a,b,0,1字符串的集合。 所有词法结构一般都可以用正规式描述。 若两个正规式所表示的正规集相同，则称这两个正规式等价。如 b(ab)*=(ba)*b 正规式的性质： A|B = B|A 交换律 A |(B|C) = (A|B)|C