Presentation is loading. Please wait.

Presentation is loading. Please wait.

第三章 词法分析.

Similar presentations


Presentation on theme: "第三章 词法分析."— Presentation transcript:

1 第三章 词法分析

2 第三章 词法分析 本章内容 词法分析器:把构成源程序的字符流翻译成记号流,还完成和用户接口的一些任务 围绕词法分析器的自动生成展开
第三章 词法分析 词法分析器 语法分析器 符号表 记号(token) 取下一个记号 源程序 本章内容 词法分析器:把构成源程序的字符流翻译成记号流,还完成和用户接口的一些任务 围绕词法分析器的自动生成展开 介绍正则式、状态转换图和有限自动机概念

3 词法分析初步:正则表达式,状态转换图 3.1~3.4

4 3.1 词法记号及属性 3.1.1 词法记号、模式、词法单元 if if 字符i, f for for 字符f, o, r
记号名 词法单元例举 模式的非形式描述 if if 字符i, f for for 字符f, o, r relation < , <= , = , … < 或 <= 或 = 或 … id sum, count, D5 由字母开头的字母数字串 number 3.1, 10, 2.8 E12 任何数值常数 literal “seg. error” 引号“和”之间任意不含 引号本身的字符串

5 3.1 词法记号及属性 历史上词法定义中的一些问题 关键字、保留字和标准标识符的区别 忽略空格带来的困难
DO 8 I  等同于 DO8I  3. 75 DO 8 I  3, 75 关键字不保留 IF THEN THEN THEN=ELSE;ELSE … 关键字、保留字和标准标识符的区别 保留字是语言预先确定了含义的词法单元 标准标识符也是预先确定了含义的标识符,但程序可以重新声明它的含义

6 3.1 词法记号及属性 3.1.2 词法记号的属性 position = initial + rate  60的记号和属性值:
id,指向符号表中position条目的指针 assign _ op id,指向符号表中initial条目的指针 add_op id,指向符号表中rate条目的指针 mul_ op number,整数值60

7 3.1 词法记号及属性 3.1.3 词法错误 词法分析器对源程序采取非常局部的观点 例:难以发现下面的错误
fi (a == f (x) ) … 在实数是“数字串.数字串”格式下,可以发现下面的错误 123.x 紧急方式的错误恢复 删掉当前若干个字符,直至能读出正确的记号 错误修补 进行增、删、替换和交换字符的尝试

8 3.2 词法记号的描述与识别 3.2.1 串和语言 串的运算 字母表:符号的有限集合, 例: = { 0, 1}
串:符号的有穷序列,例:0110,  语言:字母表上的一个串集 {, 0, 00, 000, …}, {},  句子:属于语言的串 串的运算 连接(积) xy,s = s = s 幂 s0为,si为si-1s(i > 0)

9 3.2 词法记号的描述与识别 语言的运算 例 并: L  M = {s | s L 或 s  M }
连接: LM = {st | s  L 且 t  M} 幂: L0是{},Li是Li-1L 闭包: L = L0  L1  L2  … 正闭包: L+ = L1  L2  … L: { A, B, …, Z, a, b, …, z }, D: { 0, 1, …, 9 } L  D, LD, L6, L*, L(L  D )*, D+

10 3.2 词法记号的描述与识别 3.2.2 正则式 正则式用来表示简单的语言,叫做正则集 正则式 定义的语言 备注  {}
正则式 定义的语言 备注  {} a {a} a   (r) | (s) L(r)∪L(s) r和s是正则式 (r)(s) L(r)L(s) r和s是正则式 (r)* (L(r))* r是正则式 (r) L(r) r是正则式 ((a) (b)*)| (c)可以写成ab*| c

11 3.2 词法记号的描述与识别 正则式的例子  = {a, b} 复杂的例子 句子:01001101000010000010111001
a | b {a, b} (a | b) (a | b ) {aa, ab, ba, bb} aa | ab | ba | bb {aa, ab, ba, bb} a* 由字母a构成的所有串集 (a | b)* 由a和b构成的所有串集 复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11)  (01 | 10) ) )  句子:

12 3.2 词法记号的描述与识别 正则式等价:表示同样语言的正则式

13 3.2 词法记号的描述与识别 3.2.3 正则定义 对正则式命名,使表示简洁 d1  r1 d2  r2 . . . dn  rn
各个di的名字都不同 每个ri都是 {d1, d2, …, di-1 }上的正则式

14 3.2 词法记号的描述与识别 正则定义的例子 C语言的标识符是字母、数字和下划线组成的串
letter_  A | B | … | Z | a | b | … | z | _ digit  0 | 1 | … | 9 id  letter_(letter_ |digit)*

15 3.2 词法记号的描述与识别 正则定义的例子  无符号数集合,例1946,11.28,63E8,1.99E6
digit  0 | 1 | … | 9 digits  digit digit* optional_fraction  .digits| optional_exponent  ( E ( + |  |  ) digits ) |  numberdigits optional_fraction optional_exponent  简化表示 number  digit+ (.digit+)? (E(+|)? digit+)?

16 3.2 词法记号的描述与识别 正则定义的例子(进行下一步讨论的例子) while  while do  do
relop  < | < = | = | < > | > | > = letter  A | B | … | Z | a | b | … | z id  letter (letter | digit )* number  digit+ (.digit+)? (E (+ | )? digit+)? delim  blank | tab | newline ws  delim+

17 3.2 词法记号的描述与识别 词法单元的识别 stmt  if expr then stmt
| if expr then stmt else stmt | ε expr  term relop term | term term  id | number

18 3.2 词法记号的描述与识别 词法单元的识别 stmt  if expr then stmt
| if expr then stmt else stmt | ε expr  term relop term | term term  id | number digit  [0-9] digits  digit+ number  digits(.digits)?(E[+-]?digits)? letter  [A-Za-z] id  letter (letter | digit)* if  if then  then else  else relop  < | > | <= | >= | = | <>

19 3.2 词法记号的描述与识别 词法单元的识别 词素 词法单元名字 属性值 Any ws - if Then then else Any id
指向符号表条目的指针 Any number number < relop LT <= LE = EQ <> NE > GT >= GE

20 3.2 词法记号的描述与识别 3.2.4 转换图 关系算符的转换图 return(relop, LE) 2 = >
5 1 6 2 4 8 3 7 return(relop, LE) return(relop, NE) return(relop, LT) return(relop, GE) return(relop, GT) return(relop, EQ) 开始 < = > * other

21 3.2 词法记号的描述与识别 标识符和关键字的转换图 开始 letter other letter或digit
9 10 11 开始 letter other * letter或digit return(install_id())

22 3.2 词法记号的描述与识别 无符号数的转换图 number  digit+ (.digit+)? (E (+ | )? digit+)? 开始 19 12 13 14 15 16 17 18 digit other . E +/ return( installNum( ) ) *

23 3.2 词法记号的描述与识别 空白的转换图 delim  blank | tab | newline ws  delim+ 21 22
开始 delim other * 20

24 3.2 词法记号的描述与识别 合成整体转换图 开始 9 12 20

25 字符串匹配。给你两个字符串,寻找其中一个字符串是否包含另一个字符串,如果包含,返回包含的起始位置。
作业 字符串匹配。给你两个字符串,寻找其中一个字符串是否包含另一个字符串,如果包含,返回包含的起始位置。 如下面两个字符串: 时间复杂度<O(N2) char *str = "bacbababadababacambabacaddababacasdsd"; char *ptr = "ababaca";

26 重点 串和语言 语言的运算 正则表达式 状态转换图


Download ppt "第三章 词法分析."

Similar presentations


Ads by Google