编译原理第4章 词法分析.ppt

第4章 词法分析 词法分析程序的设计 单词的描述工具 有限自动机 正规式和有穷自动机的等价性 正规文法和有穷自动机间的转换 词法分析程序的自动构造工具 4.1 词法分析程序的设计 词法分析（lexical analysis） 词法分析程序 单词符号 单词符号一般可分为下列五种： 基本字（关键字）：begin, end, if, while, var等。 标识符：各种名称，如常量名、变量名、过程名等。 常数（量）：25, 3.1415, TRUE, “ABC”等 运算符：如 + - * / =等。 界符：逗号，分号，括号等。 输出表示（单词种别，单词自身的值）。 程序段 if i=5 then x∶=y - 保留字if(3，if)　- 标识符i(1，指向i的符号表入口)　- 等号=(4，=)　- 常数5(2，5)　- 保留字then(3，then)　- 标识符x(1，指向x的符号表入口)　- 赋值号∶=(4，∶=) 　- 标识符 y(1，指向y的符号表入口)　- 分号；(5，；) 　 单词的描述工具 文法G=（VN，VT，P，S），P中每一产生式的形式都为：A→aB或A→a，其中A∈VN ，B∈VN ，a∈VT。 无符号整数：〈无符号整数〉→d | d〈无符号整数〉 运算符：〈运算符〉→ + | - | * | / | = | 〈等号〉| 〈等号〉……〈等号〉→ = 界符：〈界符〉→ , | ; | ( | ) |…… 无符号实数：〈无符号实数〉→ d 〈余留无符号数〉| . 〈十进小数〉| e〈指数部分〉〈余留无符号数〉→ d 〈余留无符号数〉| . 〈十进小数〉| e〈指数部分〉|ε〈十进小数〉 → d 〈余留十进小数〉〈余留十进小数〉 → e〈指数部分〉| d 〈余留十进小数〉| ε〈指数部分〉 → d 〈余留整指数〉| s〈整指数〉〈整指数〉 → d 〈余留整指数〉〈余留整指数〉 → d 〈余留整指数〉 |ε 其中s表示正或负号。 如 25.55e+5 和 2.1 正规式(regular expression) 正规式和它所表示的正规集 设字母标为?，辅助字母表?={?，?，?，?，?，?，?}。 4。仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的字集才是?上的正规集。 例4.2 令?={a，b}， ?上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} a?b {a,b} ab {ab} 例 ?={l，d}，r=l(l ?d) ?定义的正规集: {l,ll,ld,ldd,……}，其中l代表字母，d代表数字，正规式，即是字母(字母|数字)*，它表示的正规集中的每个元素的模式是“字母打头的字母数字串”，就是Pascal和多数程序设计语言允许的的标识符的词法规则。 例4.3 ?={d，.，e，+，-},则?上的正规式 d?(.dd ?? ? )(e(+?- ??)dd? ??)表示的是无符号数的集合，其中d为0~9的数字。 两个正规式等价 若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。 正规式的运算律 设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?… “或”的抽取律  对于?上的正规式r ,存在一个G=(VN,VT,P,S) 使得L(G)=L(r) ，反之亦然。 1. 将正规式转换成正规文法 VT= ?,S ? VN ，生成正规产生式 S?r (2)对形如A?x?y的正规产生式：A?xB A?y B?xB B?y B?VN 例 r = a(a?d)? VT={a,d} S?a(a?d)? 2. 将正规文法转换成正规式