《编译原理 第四章 词法分析.》由会员分享，可在线阅读，更多相关《编译原理 第四章 词法分析.（99页珍藏版）》请在金锄头文库上搜索。
1、第四章 词法分析 *1 课前思考 词法分析程序的功能是什么？ PL/0词法分析程序识别哪几种单词？ 画出PL/0词法分析程序的流程图。 C语言，PASCAL语言的标识符和数的表 示分别有什么规定？ 编写一个程序（C的，或PASCAL的）识 别C+语言的标识符。 *2 学习目标 明确词法分析在编译过程所处的阶段和 作用。 掌握词法分析程序的手工实现方法。 理解通常的单词分类和构词规则。 会使用单词的描述和识别机制。 了解词法分析程序的自动构造原理。 *3 学习指南 词法分析程序是编译程序的一个构成成分， 它的主要任务是扫描源程序，按构词规则识别单 词，并报告发现的词法错误。词法分析也是语法 分析
2、的一部分，把词法分析从语法分析中独立出 来是为了使编译程序结构清晰，也是为了便于使 用自动构造工具，提高编译效率。 本章首先介绍词法分析程序的功能和设计原 则，然后引入正规式和其对单词的描述，接着讲 述有穷自动机理论，最后给出词法分析程序的自 动构造原理。 *4 难重点 如何设计和实现词法分析程序 正规式的定义-如何用作单词的描述工具 有穷自动机的定义和分类-如何用作单词 的识别系统 正规式到有穷自动机的转换算法-词法分 析程序的自动构造原理 *5 知识结构 *6 *7 *8 本章要点 掌握词法分析程序的设计原则和实现的办法 首先需要描述和刻画语言中的原子单位 单词，其次需要识别单词和执行某些
3、相关的动 作。 描述程序设计语言的词法的机制是3型文法 和正则表达式，识别机制是有穷状态自动机。 *9 4.1词法分析程序的设计 n词法分析（lexical analysis） 逐个读入源程序字符并按照构词规则切分成一系列 单词。 单词是语言中具有独立意义的最小单位，包括保留 字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法分析前 进行 。也可以和语法分析结合在一起作为一遍，由 语法分析程序调用词法分析程序来获得当前单词供 语法分析使用。 *10 4.1.1词法分析程序与语法分析程序的接口方式 n主要任务： 读源程序，产生单词符号，并转换为token表示 n其他任
4、务： 滤掉空格，删除注释、换行符 对行列计数 发现并定位词法错误，并尽量改正 建立符号表、常数表等表格， 源程序词法分析程序语法分析程序 Token get token . *11 4.1.2词法分析程序的输出 n输出的单词符号(Token)用二元式表示： （单词种别，单词自身的值） 例如：Pascal语句const i=25，yes=1;中单词25和1的种别 都是常数，常数的值分别为25和1 nToken的种类： 有些单词，只需要值，如基本字 有些单词，还需要其他信息，如标识符 (标识符，指向该标识符所在符号表中位置的指针) 例：上述语句中的单词i和yes的表示为： （标识符，指向i的表项的
5、指针） （标识符，指向yes的表项的指针） *12 n单词符号一般可分为下列五种： 基本字（关键字）：可统归一种，也可一符 一种 标识符：统归一种 常数（量）：可统归一种，也可按类型（整 型、实型）分种 运算符：一符一种，也可按类型分种 界符：一符一种 *13 n例： A:=B+2 (Id的整数码,指向A的符号表的入口指针） (运算符的整数码,:=) (Id的整数码,指向B的符号表的入口指针) ( 运算符的整数码,+) ( 常数的整数码, 2) 假如标识符编码为1，常数为2，保留字为3，运算符为 4，界符为5，程序段 if i=5 then x:=y；在经词法分析 器扫描后输出的单词符号和它们
6、的表示如下： - 保留字if (3，if) - 标识符i (1，指向i的符号表入口) - 等号= (4，=) - 常数5 (2，5) - 保留字then (3，then) - 标识符x (1，指向x的符号表入口) - 赋值号:= (4，:=) - 标识符 y (1，指向y的符号表入口) - 分号; (5，;) * 14 4.1.3将词法分析工作分离出来的原因 n使整个编译程序的结构更简洁、清晰和 条理化。 n编译程序的效率会改进。 n增强编译程序的可移植性。 *15 4.2 单词的描述工具 4.2.1正规文法 n3型文法G=VN，VT，S，P的P中的规则有两 种形式： A aB或A a，其中A
7、，B VN，a VT* n正规文法所描述的是VT上的正规集。 *16 n程序设计语言中的几类单词可用下述规则描述： l | l l | d | l| d d | d无符号整数 + | - | * | / | = | = , | ；| ( | ) | n无符号实数，如25.55e+5和2.1，可以由如下规 则描述: 无符号数d余留无符号数| .十进小数 | e指数部分 余留无符号数d余留无符号数| .十进 小数| e指数部分| 十进小数d余留十进小数 余留十进小数e指数部分| d余留十 进小数| 指数部分d余留整指数| s整指数 整指数d余留整指数 余留整指数d余留整指数| n正规集 由正规文法
8、产生的语言 n注：正规集是集合，可有穷也可无穷。 可通过正规式来形式化表示 *20 4.2.2 正规式 n正规表达式（regular expression）是说明单词的 模式(pattern)的一种重要的表示法（记号）。 n正规式也称正则表达式，是描述单词符号的一种 方便工具，是定义正规集的工具。 定义（正规式和它所表示的正规集）： n设字母表为，辅助字母表=， ， ，。 和都是上的正规式，它们所表示的正规集 分别为和 ； 任何a ，a是上的一个正规式，它所表示的 正规集为a； *21 *22 假定e1和e2都是上的正规式，它们所表示的正 规集分别为L(e1)和L(e2)，那么，(e1)，e1
9、 e2，e1 e2，e1也都是正规式，它们所表示的正规集分别 为L(e1)，L(e1)L(e2)，L(e1)L(e2)和(L(e1)。 仅由有限次使用上述三步骤而定义的表达式才 是上的正规式，仅由这些正规式所表示的字集 才是上的正规集。 *23 其中的“”读为“或”（也有使用“+”代替 “” 的） ；“”读为“连接”；“”读为“闭包”（即，任意有限 次的自重复连接）。在不致混淆时，括号可省去 规定算符的优先顺序为： “”、“”、“”、“”、“” 高 低 连接符“ ”一般可省略不写。 “”、“”和“” 都是左结合的。 *24 n例4.2 令=a，b， 上的正规式和相应的正 规集的例子有： 正规式
10、 正规集 a a ab a,b ab ab (ab)(ab) aa,ab,ba,bb a ,a,aa, 任意个a的 串 (ab) ,a,b,aa,ab 所有 由a和b 组成的串 (ab)(aabb)(ab) 上所有含有两个相继 的a或 两个相继的b组成的串 *25 n若两个正规式e1和e2所表示的正规集相同 ，则说e1和e2等价，写作e1=e2。 例如： e1= ab， e2 = ba 又如： e1= b(ab) , e2 =(ba)b 再如： e1= (ab) , e2 =(ab) n例：证明b(ab)*=(ba)*b n证明：因为 L(b(ab)*)=b, bab, babab, L(ba
11、)*b)=b, bab, babab, 又因为正规集的前n项相同， 所以，可知它们的正规集是相等的， 故：正规式b(ab)*=(ba)*b * 27 n设r，s，t为正规式，正规式服从的代数规 律有： rs=sr“或”服从交换律 r(st)=(rs)t“或”的可结合律 (rs)t=r(st) “连接”的可结合律 r(st)=rsrt (st)r=srtr 分配律 r=r, r=r 是“连接”的恒等元素 零一律 rr=r “或”的抽取律 r*=(r| )* r*=r* r*=r+| r+=rr* *28 n例2，=l, d，r=l(ld) 定义的正规集？ l, ll, ld, ldd, n例3，
12、=d, ., e, +, -，则上的正规式 d(.dd )(e(+- )dd)表示的是无符 号数的集合。其中d为09的数字。 *29 4.2.3 正规文法和正规式的等价性 n对任意一个正规文法，存在一个定义 同一个语言的正规式 n对于每一个正规式，存在一个生成同 一语言的正规文法 *30 n 上的正规式r正规文法G=VN，VT，S，P 初始VT= ，S VN ，生成正规产生式(或定义式) :Sr （r为正规 式） (R1) 对形如 Ar1r2的正规产生式： Ar1B Br2 BVN (R2)对形如Ar1r2的正规产生式： Ar1B Ar2 Br1B Br2 BVN (R3)对形如Ar1r2的正
13、规产生式: Ar1 A r2 不断应用R做变换，直到每个产生式右端只含一个VN *31 n例 r=a(ad)转换为正规文法 VT=a,d Sa(ad) R1 SaA A(ad) R2 A(ad)B A B(ad)B B R3 Gs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B P *32 n例：将标识符集合的正规式：letter(letter|digit)*转 换为正规文法 SletterA A(letter|digit)* A(letter|digit)B| B(letter|digit)B| n结果：SletterA Aletter B|digitB| BletterB|digitB| *33 正规文法正规式 正规文法 正规式 AxB, By 转换成： A=xy AxAy 转换成：
