第3章_词法分析与有穷自动机.ppt

第三章 词法分析 3.1词法分析程序的功能 3.2单词符号及输出单词的形式 3.3语言单词符号的两种定义方式 3.4正规式与有穷自动机 3.5正规文法与有穷自动机 3.6词法分析程序的编写方法 3.1 词法分析程序的功能 一、词法分析（lexical analysis） 1、任务：逐个读入源程序字符并按照构词规则切分成一系列单词。 2、单词的含义：单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 二、词法分析程序 3.2 单词符号及输出单词的形式 1、单词符号一般可分为下列五种： 基本字（关键字）：begin, end, if, while, var等 标识符：各种名称，如常量名、变量名、过程名等 常数（量）：25, 3.1415, TRUE, “ABC”等 运算符：如 + - * / =等 界符：逗号，分号，括号等 2、词法分析程序所输出的单词符号通常表示成如下的二元式： （单词种别，单词自身的值） 单词种别：单词的种类 通常的方法是每种单词对应一个整数码，其目的是最大限度地把每个单词区别开来。 单词自身的值 （1）如果一个种别只含有一个单词符号，种别编码代表单词自身的值 （2）含有多个符号的，则需给出单词自身的值 注：标识符自身的值，是标识符自身的字符串 常数自身值，是常数本身的二进制数值。 3.3语言单词符号的两种定义方式 一、正规文法：文法G=（VN，VT，P，S），P中每一产生式的形式都为：A→aB或A→a，其中A∈VN ，B∈VN ，a∈VT 3、运算符：〈运算符〉→ + | - | * | / | = | 〈等号〉| 〈等号〉…… 4、〈等号〉→ = 5、界符：〈界符〉→ , | ; | ( | ) |…… 6、无符号实数：〈无符号实数〉→ d 〈余留无符号数〉| . 〈十进小数〉| e〈指数部分〉〈余留无符号数〉→ d 〈余留无符号数〉| . 〈十进小数〉| e〈指数部分〉|ε〈十进小数〉 → d 〈余留十进小数〉〈余留十进小数〉 → e〈指数部分〉| d 〈余留十进小数〉| ε〈指数部分〉 → d 〈余留整指数〉| s〈整指数〉〈整指数〉 → d 〈余留整指数〉〈余留整指数〉 → d 〈余留整指数〉 |ε其中s表示正或负号。 如 25.55e+5 和 2.1 二、正规式(regular expression) 1、定义（正规式和它所表示的正规集）： 设字母标为?，辅助字母表?={?，?，?，?，?，?，?}。 ?和?都是?上的正规式，它们所表示的正规集分别为{?}和?； 任何a? ?，a是?上的一个正规式，它所表示的正规集是由单个符号构成，为{a}； 假定e1和e2都是?上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1?e2, e1?e2, e1?也都是正规式,它们所表示的正规集分别为L(e1), L(e1)∪L(e2), L(e1)L(e2)和(L(e1))?。 仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的字集才是?上的正规集。 例：令?={a，b}， ?上的正规式和相应的正规集的例子有： 两个正规式等价 若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。 例如： e1= (a?b)， e2 = b?a 又如： b(ab)? = (ba)?b (a?b)? = (a??b?)? 三、正规文法与正规式 对?上的正规式r ,存在一个G=(VN,VT,P,S)使得L(G)=L(r) ，反之亦然。 正规式到正规文法 例： r = a(a?d)? VT={a,d} S?a(a?d)? S?aAA?(a?d)?A?(a?d)B A?? B?(a?d)B B?? 3.4 正规式和有穷自动机 确定的有穷自动机（DFA） 非确定的有穷自动机（NFA） 由正规表达式构造NFA NFA 确定化为 DFA 的转换 DFA的化简 有穷自动机到正规式的转换 3.4.1 确定的有穷自动机（DFA） 一个确定的有穷自动机（DFA）M是一个五元组： M=（Q，Σ，f，S，Z） 其中： Q是一个有穷集，它的每个元素称为一个状态； Σ是一个有穷字母表，它的每个元素称为一个输入符号，