Microsoft PowerPoint - lexicalAnalysis

Size: px

Start display at page:

Download "Microsoft PowerPoint - lexicalAnalysis"

獭次苏
5 years ago
Views:

1 本章内容词法分析编译原理和技术张昱中国科学技术大学计算机科学与技术学院记号 token 源程序词法分析器语法分析器取下一个记号符号表词法分析及问题向前看 Lookhed 歧义miguities 词法分析器的自动生成词法记号的描述 : 正规式 ; 词法记号的识别 : 转换图有限自动机 :NF DF 张昱 : 编译原理和技术词法分析 2 词法记号模式词法单元记号名词法单元举例模式的非形式描述 if if 字符 i, f 2. 词法记号及属性记号词法单元模式 for for 字符 f, o, r reltion <, <=, =, < 或 <= 或 = 或 id sum, count, D5 由字母开头的字母数字串 nume.,, 2.8 E2 任何数值常数 literl seg. error 引号和之间任意不含引号本身的字符串 whitespce 换行符换行符 \n 无意义, 被丢弃, 不提供给语法分析器张昱 : 编译原理和技术词法分析 4 词法定义中的问题关键字保留字关键字 keyword: 有专门的意义和用途, 如 if else 保留字 : 有专门的意义, 不能当作一般的标识符使用例如, 语言中的关键字是保留字历史上词法定义中的一些问题忽略空格带来的困难, 例如 Fortrn DO 8 I 等同于 DO8I DO 8 I 3, 75 关键字不保留 IF THEN THEN THEN=ELSE; ELSE 歧义和 lookhed 词法分析从左到右读取输入串, 每次识别出一个 token 可能需要 lookhed 来判断当前是否是一个 token 的结尾下一个 token 的尤其是在 Fortrn 语言中 DO 5 I = DO 5 I =.25 DO 5 I =, 25 if then.gt. else then then = else else else = then endif 张昱 : 编译原理和技术词法分析 5 张昱 : 编译原理和技术词法分析 6

2 词法分析器 : 实现一个词法分析器的实现必须做两件事. 识别子串并对应到 tokens 2. 返回 token 的值或词法单元 lexeme 词法单元是子串 token 的实例词法记号的属性 position = initil + rte 6 的记号和属性值 : id, 指向符号表中 position 条目的指针 ssign _ op id, 指向符号表中 initil 条目的指针 dd_op id, 指向符号表中 rte 条目的指针 mul_ op numer, 整数值 6 张昱 : 编译原理和技术词法分析 7 张昱 : 编译原理和技术词法分析 8 串和语言 2.2 词法记号的描述与识别描述 : 正规式识别 : 转换图术语字母表 : 符号的有限集合, 例 : = {, 串 : 符号的有穷序列, 例 :, 语言 : 字母表上的一个串集 {,,,,, {, 句子 : 属于语言的串串的运算连接积 xy,s = s = s 幂 s 为,s i 为 s i- si > 张昱 : 编译原理和技术词法分析串和语言语言的运算并 : L M = {s s L 或 s M 连接 : LM = {st s L 且 t M 幂 : L 是 {,L i 是 L i- L 闭包 : L = L L L 2 正闭包 : L + = L L 2 例 L: {,,, Z,,,, z, D: {,,, 9 L D, LD, L 6, L, LL D, D + 优先级 : 幂连接并张昱 : 编译原理和技术词法分析正规式 regulr expression 正规式用来表示简单的语言, 叫做正规集正规式定义的语言备注 { { r Lr r 是正规式 r s Lr Ls r 和 s 是正规式 rs LrLs r 和 s 是正规式 r Lr r 是正规式 c 可以写成 c 优先级 : 闭包连接选择张昱 : 编译原理和技术词法分析 2 2

3 正规式举例 = {, {, {,,, {,,, 由字母构成的所有串的集合由和构成的所有串的集合复杂的例子句子 : 张昱 : 编译原理和技术词法分析 3 正规定义 regulr definition 对正规式命名, 使正规式表示简洁 d r d 2... d n r n 各个 d i 的名字都不同每个 r i 都是 {d, d 2,,d i- 上的正规式语言的标识符是字母数字和下划线组成的串 letter_ Z z_ digit 9 id letter_letter_ digit 张昱 : 编译原理和技术词法分析 4 正规定义举例无符号数集合, 例 946,.28,63E8,.99E6 digit 9 digits digit digit optionl_frction.digits optionl_exponent E+ digits numer digits optionl_frction optionl_exponent 简化的表示 numer digit +.digit +? E+-? digit +? 张昱 : 编译原理和技术词法分析 5 词法记号的识别 : 转换图转换图 trnsition digrm 关系算符的转换图 < = > 5 6 other = > 2 3 returnrelop, EQ = other returnrelop, LT 4 7 双圈表示接受 returnrelop, LE returnrelop, NE 星号表示将输入回退一个位置 returnrelop, GE returnrelop, GT 8 张昱 : 编译原理和技术词法分析 6 转换图标识符和关键字的转换图 letter 或 digit letter other 9 无符号数的转换图 digit returninstllid numer digit +.digit +? E+-? digit +? E digit digit digit digit. digit E +/ digit other other other 张昱 : 编译原理和技术词法分析 7 return instllnum 9 转换图空白的转换图 delim lnk t newline ws delim+ delim delim other 张昱 : 编译原理和技术词法分析 8 3

4 基于转换图的词法分析例 :relop 的转换图的概要实现 TOKEN getrelop { TOKEN rettoken = newrelop; while { switch stte{ cse : c = nexthr; if c == '<' stte = ; else if c == '=' stte = 5; else if c == '>' stte = 6; else fil; rek; 出错处理, 要 cse :... 能从错误恢复... cse 8: retrct; 回退 rettoken.ttriute = GT; returnrettoken; = 2 > 3 < other 4 = 5 > = 7 6 other 8 张昱 : 编译原理和技术词法分析 9 词法分析中的冲突及解决 R = Whitespce Integer Identifier + 分析 foo+3 f 匹配 R, 更精确地说是 Identifier 但是 fo 也匹配 R, foo 也匹配, 但 foo+ 不匹配如何处理输入? 如果 x x i LR 并且 x x K LR Mximl munch 规则 : 选择匹配 R 的最长前缀最长匹配规则在实现时 :lookhed, 不符合则回退张昱 : 编译原理和技术词法分析 2 词法分析 : 分类的不确定性 R = Whitespce new Integer Identifier 分析 new foo new 匹配 R, 更精确地说是 new 但是也匹配 Identifier, 此时该选哪个? 一般地, 如果 x x i LR j 和 x x i LR k 规则 : 选择先列出的模式 j 如果 j < k 必须将 new 列在 Identifier 的前面词法错误词法分析器对源程序采取非常局部的观点例 : 难以发现下面的错误 fi == f x 在实数是数字串. 数字串格式下, 可以发现下面的错误 23.x 紧急方式的错误恢复删掉当前若干个字符, 直至能读出正确的记号错误修补进行增删替换和交换字符的尝试张昱 : 编译原理和技术词法分析 2 张昱 : 编译原理和技术词法分析 22 例题写出语言所有相邻数字都不相同的非空数字串的正规定义解答 : nswer no_ no_ no_ no_ no_ no_- no_- no_- no_-... no_-8 9 将这些正规定义逆序排列就是答案例题 2 下面语言编译器编译下面的函数时, 报告 prse error efore else long gcdp,q long p,q; { if p%q == / then prt / return q 此处遗漏了分号 else / else prt / return gcdq, p%q; 张昱 : 编译原理和技术词法分析 23 张昱 : 编译原理和技术词法分析 24 4

5 例题 2 现在少了第一个注释的结束符号后, 反而不报错了 long gcdp,q long p,q; { if p%q == / then prt return q else / else prt / return gcdq, p%q; 2.3 有限自动机描述分析器 :NF DF 自动机的转换 NFDF 化简的 DF 张昱 : 编译原理和技术词法分析 25 有限自动机不确定的有限自动机 NF 一个数学模型, 它包括 : 有限的集合 S 2 集合 3 转换函数 move : S { PS 4 s 是唯一的 5 F S 是接受集合识别语言的 NF nondeterministic finite utomton 接受 2 张昱 : 编译原理和技术词法分析 27 转换表 NF 的转换表识别语言的 NF {, { {2 2 2 张昱 : 编译原理和技术词法分析 28 例题 3 识别的 NF 张昱 : 编译原理和技术词法分析 29 确定的有限自动机确定的有限自动机 DF 一个数学模型, 它包括 : 有限的集合 S 2 集合 3 转换函数 move : S S, 且可以是部分函数 4 s 是唯一的 5 F S 是接受集合识别语言的 DF 2 张昱 : 编译原理和技术词法分析 3 5

6 例题 4 构造一个 DF, 它能识别 {, 上能被 5 整除的二进制数解答已读过尚未读已读部分的值某时刻 5 读进 5 2 = 读进 2 + = 2 引入 5 个即可, 分别代表已读部分的值除以 5 的余数张昱 : 编译原理和技术词法分析 3 例题 4 构造一个 DF, 它能识别 {, 上能被 5 整除的二进制数解答 2 = 2 = 7 张昱 : 编译原理和技术词法分析 32 4 例题 5 构造一个 DF, 它能接受和的个数都是偶数的字符串偶奇偶偶奇偶 2 3 奇奇张昱 : 编译原理和技术词法分析 33 NF 到 DF 的变换子集构造法 suset construction. DF 的一个是 NF 的一个集合 2. 读了输入 i 后, NF 能到达的所有 :s, s 2,, s k, 则 DF 到达一个, 对应于 NF 的 {s, s 2,, s k { {, {, 2 未画完 2 张昱 : 编译原理和技术词法分析 34 NF 到 DF 的变换子集构造法 suset construction - 闭包 -closure s 的 - 闭包是 s 经转换所能到达的集合 2. NF 的初始的 - 闭包对应于 DF 的初始 3. 针对每个 DF NF 子集, 求输入每个 i 后能到达的 NF 的 - 闭包并集, 该集合对应于 DF 中的一个已有, 或者是一个要新加的 DF 张昱 : 编译原理和技术词法分析 35 正规式对应的 NF 如下, 把它变换为 DF 张昱 : 编译原理和技术词法分析 36 6

7 = {,, 2, 4, 7 张昱 : 编译原理和技术词法分析 37 张昱 : 编译原理和技术词法分析 38 = {,, 2, 4, 7 = {, 2, 3, 4, 6, 7, 8 = {,, 2, 4, 7 = {, 2, 3, 4, 6, 7, 8 张昱 : 编译原理和技术词法分析 39 张昱 : 编译原理和技术词法分析 4 = {,, 2, 4, 7 = {, 2, 3, 4, 6, 7, 8 = {, 2, 4, 5, 6, 7 张昱 : 编译原理和技术词法分析 4 = {,, 2, 4, 7 = {, 2, 3, 4, 6, 7, 8 = {, 2, 4, 5, 6, 7 张昱 : 编译原理和技术词法分析 42 7

8 = {,, 2, 4, 7 = {, 2, 3, 4, 6, 7, 8 = {, 2, 4, 5, 6, 7 张昱 : 编译原理和技术词法分析 43 = {,, 2, 4, 7 = {, 2, 3, 4, 6, 7, 8 = {, 2, 4, 5, 6, 7 D = {, 2, 4, 5, 6, 7, 9 D 张昱 : 编译原理和技术词法分析 44 = {,, 2, 4, 7 = {, 2, 3, 4, 6, 7, 8 = {, 2, 4, 5, 6, 7 D = {, 2, 4, 5, 6, 7, 9 D D 张昱 : 编译原理和技术词法分析 45 = {,, 2, 4, 7 = {, 2, 3, 4, 6, 7, 8 = {, 2, 4, 5, 6, 7 D = {, 2, 4, 5, 6, 7, 9 D D 张昱 : 编译原理和技术词法分析 46 = {,, 2, 4, 7 = {, 2, 3, 4, 6, 7, 8 = {, 2, 4, 5, 6, 7 D = {, 2, 4, 5, 6, 7, 9 D D 张昱 : 编译原理和技术词法分析 47 D D D 张昱 : 编译原理和技术词法分析 48 8

9 识别语言的 DF D 2 张昱 : 编译原理和技术词法分析 49 识别语言的 DF 子集构造法不一定得到最简 DF D 2 张昱 : 编译原理和技术词法分析 5 DF 的化简该方法用于化简转换函数是全函数的 DF 死 ded stte 当转换函数由部分函数改成全函数表示时引入左图引入死 E, E D 张昱 : 编译原理和技术词法分析 5 D DF 的化简可区别的 distinguishle sttes s 和 t 分别从 s t 出发, 存在一个 w, 使得一个到达接受, 另一个到达非接受和是可区别的 : 从出发, 读入后到达非接受 ; 从出发, 读过后到达接受 D 和是不可区别的 : 无任何可用来区别它们 D 张昱 : 编译原理和技术词法分析 52 DF 的化简方法. 按是否是接受来区分 {,,, {D move{,,, = { move{,,, = {, D 2. {,, {, {D move{,, = { move{,, = { 2 D 张昱 : 编译原理和技术词法分析 53 例题 7 叙述下面的正规式描述的语言, 并画出接受该语言的最简 DF 的转换图解答描述的语言是, 所有不含子串的由和组成的串. strt 2 刚读过的不是连续读过一个连续读过不少于两个张昱 : 编译原理和技术词法分析

10 例题 8 解答用转换图表示接受如下正规式的 DF strt 张昱 : 编译原理和技术词法分析从正规式到有限自动机分析器的自动构造正规式 NFDF 化简的 DF 采用语法制导的算法来构造 NF 语法制导的构造算法语法制导 : 按正规式的语法结构来指导构造构造识别和字母表中一个符号的 NF 重要特点 : 仅一个接受 i 识别正规式的 NF f 对于带括号的正规式 s, 使用 s 对应的 NF Ns 本身作为它的 NF i 识别正规式的 NF f 语法制导的构造算法构造识主算符为选择的正规式的 NF 重要特点 : 仅一个接受 N s i N t 识别正规式 s t 的 NF f 张昱 : 编译原理和技术词法分析 57 张昱 : 编译原理和技术词法分析 58 语法制导的构造算法构造识主算符为连接的正规式的 NF 重要特点 : 仅一个接受语法制导的构造算法构造识主算符为闭包的正规式的 NF 重要特点 : 仅一个接受, 且接受没有出边 i N s N t f i N s f 识别正规式 st 的 NF 张昱 : 编译原理和技术词法分析 59 优化 i N s f 识别正规式 s 的 NF 张昱 : 编译原理和技术词法分析 6

11 语法制导的构造算法 NF 构造过程举例本方法产生的 NF 有下列性质 Nr 的数最多是 r 中符号和算符总数的两倍 Nr 只有一个接受, 接受没有向外的转换的分解 r 5 r 7 r 6 r 8 Nr 的每个有一个用的符号标记指向其它结点的转换, 或者最多两个指向其它结点的转换 r 张昱 : 编译原理和技术词法分析 6 张昱 : 编译原理和技术词法分析 62 NF 构造过程举例 NF 构造过程举例的分解 r 7 r 8 的分解 r 7 r 8 r 5 r 6 r 5 r 6 r r 张昱 : 编译原理和技术词法分析 63 张昱 : 编译原理和技术词法分析 64 NF 构造过程举例 NF 构造过程举例的分解 r 7 r 8 的分解 r 7 r 8 r 5 r 6 r 5 r 6 r r 张昱 : 编译原理和技术词法分析 65 张昱 : 编译原理和技术词法分析 66

12 NF 构造过程举例 NF 构造过程举例的分解 r 7 r 8 的分解 r 7 r 8 r 5 r 6 r 5 r 6 r r 张昱 : 编译原理和技术词法分析 67 张昱 : 编译原理和技术词法分析 68 NF 的手工构造和算法构造的两个 NF 的比较手工构造 : 2 算法构造 : 张昱 : 编译原理和技术词法分析词法分析器的生成器 Lex: flex jflex ntlr 用 Lex 建立词法分析器 Lex 程序词法分析器 - Lexicl nlyzer, scnner 生成器 - genertor Flex ; JFlex Lex 源程序 lex.l lex.yy.c Lex 编译器编译器 lex.yy.c.out Lex 程序包括三个部分声明 %% 翻译规则 %% 辅助过程 Lex 程序的翻译规则 p { 动作 p 2 { 动作 2 p n { 动作 n 输入流.out 记号序列张昱 : 编译原理和技术词法分析 7 张昱 : 编译原理和技术词法分析 72 2

13 Lex 文件举例声明部分 %{ / 常量 LT, LE, EQ, NE, GT, GE, %{ 和 % 包含的代码将直接复制到生成的分析器源程序文件中 WHILE, DO, ID, NUMER, RELOP 的定义 / % / 正规定义 / delim [ \t \n ] ws {delim+ letter [ Z z] digit [9] id {letter{letter{digit numer {digit+\.{digit+?e[+\]?{digit+? 张昱 : 编译原理和技术词法分析 73 Lex 文件举例翻译规则部分 {ws {/ 没有动作, 也不返回 / while {return WHILE; do {return DO; {id {yylvl = instll_id ; return ID; {numer {yylvl = instll_num ; return NUMER; < {yylvl = LT; return RELOP; <= {yylvl = LE; return RELOP; = {yylvl = EQ; return RELOP; <> {yylvl = NE; return RELOP; > {yylvl = GT; return RELOP; >= {yylvl = GE; return RELOP; 张昱 : 编译原理和技术词法分析 74 Lex 文件举例辅助过程部分 instllid { / 把词法单元装入符号表并返回指针 yytext 指向该词法单元的第一个字符, yyleng 给出的它的长度 / instllnum { / 类似上面的过程, 但词法单元不是标识符而是数 / 张昱 : 编译原理和技术词法分析 75 NTLR 的文法文件.g4 格式 rulenme grmmr MyG; 词法 : 大写字母开头 options { 语法 : 小写字母开头 import ; 纯词法分析器 tokens { lexer grmmr { 词法规则 INT : DIGIT+ ; rulenme : <stuff> ; frgment DIGIT : [-9] ; LQUOTE : '"' -> more, modestr ; 正规定义, DIGIT 不是记号 mode STR; STRING : '"' -> modedefult_mode; 模式定义词法模式调用张昱 : 编译原理和技术词法分析 76 NTLR:Lexer 命令命令格式 TokenNme : < 选项 > -> 命令名 [ 参数 ] 命令 skip: 不返回记号给 prser, 如识别出空白符或注释 typet: 设置当前记号的类型 chnnel: 设置当前记号的通道, 缺省为 Token.DEFULT_HNNEL 值为 ;Token.HIDDEN_HNNEL 值为 modem: 匹配当前记号后, 切换到模式 M pushmodem: 与 modem 类似, 但将当前模式入栈 popmode: 从模式栈弹出模式, 使之成为当前模式张昱 : 编译原理和技术词法分析 77 本章要点词法分析器的作用和接口, 用高级语言编写词法分析器等掌握下面的相关概念, 它们之间转换的技巧方法或算法非形式描述的语言正规式正规式 NF 非形式描述的语言 NF NF DF DF 最简 DF 非形式描述的语言 DF 或最简 DF 张昱 : 编译原理和技术词法分析 78 3

大侠素材铺

大侠素材铺编译原理与技术词法分析 Ⅱ 计算机科学与技术学院李诚 13/09/2018 主要内容记号 (token) 源程序词法分析器 getnexttoken 语法分析器符号表词法分析器的自动生成正则表达式 NFA DFA 化简的 DFA 词法分析器的生成器 Lex: flex jflex Fst lexicl nlyzer genertor 2/51 Regulr Expr to NFA 正则表达式