第四章词法分析.ppt

第四章 词法分析 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 4.1 词法分析程序 4.2 正规表达式与正规集（正规语言） 4.3 有穷自动机 4.4 词法分析程序的自动构造 ? 本章重点 单词的描述工具 单词的识别系统 设计和实现词法分析程序 首先需要描述和刻画程序设计语言中的原子单位——单词，其次需要识别单词和执行某些相关的动作。 描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。 回顾 什么是词法分析程序 实现词法分析（lexical analysis）的程序 逐个读入源程序字符并按照构词规则切分成一系列单词。 词法分析工作从语法分析工作独立出来的原因： 简化设计 改进编译效率 增加编译系统的可移植性 4.2单词的描述工具 程序设计语言中的单词是基本语法成分.单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造. 多数程序设计语言的单词的语法都能用正规文法(3型文法)来描述. 正规文法 3型文法（正规文法）：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN ，B∈VN ，a∈VT * 正规式 正规式也称正则表达式,正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。 定义（正规式和它所表示的正规集）： 设字母表为?，辅助字母表?`={?，?，?，?，?，?，?}。 1。 ?和?都是?上的正规式，它们所表示的正规集分别为{?}和{ }； 2。任何a? ?，a是?上的一个正规式，它所表示的正规集为{a}； 3。假定e1和e2都是?上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么， (e1), e1? e2, e1?e2, e1? 也都是正规式, 它们所表示的正规集分别为 L(e1), L(e1)?L(e2), L(e1)L(e2)和(L(e1))?。 其中的“?”读为“或”（也有使用“+”代替 “?” 的）；“? ”读为“连接”；“?”读为“闭包”（即，任意有限次的自重复连接）。 在不致混淆时，括号可省去，但规定算符的优先顺序为“?”、“? ”、“?” 。连接符“? ”一般可省略不写。“?”、“? ”和“?” 都是左结合的。 4。仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的集合才是?上的正规集。 正规式与正规集的例子 令?={a，b}， ?上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} a?b {a,b} ab {ab} (a?b)(a?b) {aa,ab,ba,bb} a ? {? ,a,a, ……任意个a的串} (a?b)? {? ,a,b,aa,bb,ab ……所有由a,b组成的串} (a?b)?(aa?bb)(a?b)? {??上所有含有两个相继的a或两个相继的b组成的串} 例?={d，?，e，+，-}, 则?上的正规式 d?(?dd ?? ? )(e(+?- ??)dd? ??) 其中d为0-9的数字。 表示的是无符号数的集合。 程序设计语言的单词都能用正规式来定义. 若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。 例如： e1= (a?b)， e2 = b?a 又如： e1= b(ab)? , e2 =(ba)?b e1= (a?b)? , e2 =(a??b?)? 设r,s,t为正规式，正规式服从的代数规律有： 1。r?s=s?r “或”服从交换律 2。r?(s?t)=(r?s)?t “或”的可结合律 3。(rs)t=r(st) “连接”的可结合律 4。r(s?t)=rs?rt (s?t)r=sr?tr 分配律 5。 ?r=r, r?=r ?是“连接”的恒等元素 零一律 6。 r?r=r “或”的抽取律 r?=??r?rr?… 4.3 有穷自动机 有穷自动机是一种数学模型，有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分