工大编译原理课件-chapter3词法分析

1、编译程序总体结构中间代码目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表 格 管 理出 错 处 理中间代码目标代码语法单位单词符号词法分析器源程序例 一个语句的翻译参见第8页图1-10第三章 词法分析School of Computer Science & Technology Harbin Institute of Technology重点：词法分析器的输入、输出， 用于识别符号的状态转移图的构造， 根据状态转移图实现词法分析器。 难点：词法的正规文法表示、正规表达式表示、 状态转移图表示，它们之间的转换。 本章主要内容3.1 词法分析器(Scanner)的功能3.2 单词的种类

2、和词法分析器的输出形式3.3 相关问题3.4 正规表达式3.5 状态转换图3.6 词法分析器的设计与实现3.1 词法分析（扫描）器的功能功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成单词符号的序列根据词法规则识别及组合单词，进行词法检查对数字常数完成数字字符串到二进制数值的转换删去空格字符和注释3.2 单词的种类和词法分析程序的输出形式一、单词的种类 1. 关键字：begin、end、for、do.2. 标识符：由用户定义，表示各种名字3. 常 数：无符号数、布尔常数、字符串常数等4.运算符：算术运算符、逻辑运算符、关系运算符5. 分界符：逗号、分号、括号等二、词

3、法分析程序的输出形式-单词的内部形式几种常用的单词内部形式：1、按单词种类分类2、保留字和分界符采用一符一类3、标识符和常数的单词值又为指示字（指针值）单词类别 属性值表示单词的种类，可用整数编码或记忆符表示不同的单词不同的值单词名称标识符无符号常数无符号浮点数布尔常数字符串常数保留字分界符类别编码1234567单词值内部字符串整数值数值0 或 1内部字符串保留字或内部编码分界符或内部编码1、按单词种类分类2、保留字和分界符采用一符一类单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数BEGINENDFORDO:+*,(类别编码12345678920212223单词值内部字符串整数值

4、数值0 或 1内部字符串-例 3-1: 单词符号序列while(*pointer!=0)pointer+; while (WHILE， _ )( (SLP， _ )* (FETCH， _ )pointer (IDN， 符号表入口指针)!= (RELOP， NE )0 (CONST， 0 )(SRP， _ ) (LP， _ )pointer (IDN， 符号表入口指针)+ (INC， _ ); (SEMI， _ ) (RP， _ ) 跟实现有关3.3 相关问题超前扫描双字符运算符（*, /*,:=,）DO 90 k=1,10DO 90 k=1.10 预处理问题剔除源程序中的无用符号、空格、换行、

5、注释等1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析S.P.(符号串)语法分析第一遍第二遍单词串优点: 结构清晰、 各遍功能单一缺点：效率低S.P.(字符串)词法分析程序语法分析程序取单词单词优点: 效率高3.3 相关问题-扫描器的运行方式3.3 相关问题符号表的查填兼顾问题兼顾：token自身值作为符号表的入口Token串长度统一，可放宽对标识符的限制，但要增加额外负担不兼顾： token自身值就是标识符、常数本身的符号串速度快，但要限制标识符的长度词法错误的检测行、列计数发现并定位词法错误一种符号表的数据结构3.3 相关问题工作区(token)单词开始指

6、针扫描指针正拼单词输入缓冲区每次移动向前指针都需要做两次测试3.3 相关问题双缓冲区问题_超前扫描导致的效率问题？如何设计和实现扫描器大小问题128Byte*2|1024Byte*2|4096Byte*2if forward在缓冲区第一部分末尾 then begin重装缓冲区第二部分;forward := forward +1endelse if forward在缓冲区第二部分末尾 then begin 重装缓冲区第一部分; 将forward移到缓冲区第一部分开始endelse forward:= forward +1; forward := forward + 1;if forward= e

7、of then beginif forward在第一部分末尾 then begin 重装第二部分; forward := forward +1endelse if forward在第二部分末尾 then begin 重装第一部分; 将forward 移到第一部分开始endelse /* eof 在表示输入结束 */ 终止词法分析end 3.4 记号的描述_正规(表达)式例：标识符的文法描述约定：用digit表示数字：0,1,2,9; 用letter表示字母：A,B,Z,a,b,zG =(digit,letter, S, P, S)Sletter Lletter|letter TSS digit

8、TLetter T|letterSS letterTdigit T|digit左线性右线性表示集合：letterletter,digit* 1) 正规式：正规语言的另一种描述方法例3-2：标识符的另一种表示letter(letter|digit)* | 表示或 * 表示Kleene闭包Letter和(letter|digit)*的并列表示两者的连接正规式 r 表示正规集,相应的正规集记为 L(r) 正规(表达)式(Regular ExpressionRE)设是一个字母表， 是上的RE，L()=； 是上的RE，L()=； 对于a，a是RE，L(a)=a；如果r和s是RE，L(r)=R,L(s)=

9、S，则：r与s的“和” (r|s)是RE，L(r|s)=RS；r与s的“乘积” (rs)是RE，L(rs)=RS；r的克林闭包(r*)是RE，L(r*)=R*。 只有满足、的才是RE。 运算的优先级运算优先级和结合性:*高于“连接” 和| ， “连接” 高于 |具有交换律、结合律“连接” 具有结合律、和对|的分配律( )指定优先关系意义清楚时，括号可以省略例：L(a(a|b)*(|(.|_)(a|b)(a|b)*)aa,b*(.,_a,ba,b* )2) 正规文法与正规式正规文法与正规式等价对任何正规文法，存在定义同一语言的正规式对任何正规式，存在生成同一语言的正规文法例 3-3 标识符定义的

10、转换引入 S Sletter (letter|digit)*引入A消除闭包 Sletter A A(letter|digit)A|执行连接对|的分配律 Sletter A Aletter A|digit A| 例3-4正规式到正规文法的转换a(a|b)*(|(.|_)(a|b)(a|b)*)= a(a|b)* |a(a|b)*.(a(a|b)*|b(a|b)*) |a(a|b)*_(a(a|b)*|b(a|b)*)=aA|aCA=aA|bA| C=aC|bC|.B|_BB=aA|bASaA|aC AaA|bA| CaC|bC|.B|_BBaA|bA正规式到正规文法的转换按如下方法构造正规定义式

11、，并逐步将其转换成正则文法引入开始符号S，从如下正规定义式开始Sr对r中的形如r1|r2|rn的子串用产生式组A r1|r2|rn 表示正规式到正规文法的转换对r中的形如r1*的子串用产生式组 A|r1A 表示对r中的形如r1+的子式子，用产生式组 A r1| r1A 表示执行连接对|的分配律正规式到正规文法的转换用到了正规定义式的概念。正规文法到正规式的转换代入：对于 AxB, By，构造 Axy递归：对于 AxA|y，构造 Ax*y多候选式：对于 Ax，Ay，构造Ax|yS0A A1B B2B|2C C3C|3S01B S012*2C S012*23*3=012+3+ 一个语言的文法描述不

12、是唯一的（文法的等价）3) 高级语言词法的简单描述词法单词符号的文法，用来描述高级语言中的：标识符、常数、运算符、分界符、关键字参考教材P6466，了解如何定义高级语言中的整数、实数等的相应正则文法。例 3-5：某简易语言的词法正规定义式 词法规则 单词种别 属性(|)* IDN 符号表入口 ()* NUM 数值 := ASG 无 其它单词字符本身 单词名称 无 变换为正规文法letter|letter|digitdigit | digit :=+=(其它：实数、算术运算符、关系运算符、分号、括号等）问题：如何识别记号？3.5 记号的识别状态转换图1 状态转换图（有穷自动机 FA M=(Q，q

13、0，F) ）用来描述词法分析器识别记号时要做的动作结点：状态用表示；终态用表示 有向弧 箭头 弧标记 输入字符标识符的状态图(|)* 123letterletter,digit其它开始终态初态例3-5的状态图letter,digitletter（IDN，入口）digitdigit(其它) (其它)（NUM，值）（ASG，_）=：+（ADD，_）s+（INC，_）其它IDNletter(letter|digit)*NUMdigit(digit)*ASG:=INC+利用状态转换图识别单词1. 从初态出发2. 读入一字符3. 按当前字符转入下一状态4. 重复 2,3 直到无法继续转移#. 在遇到读入

14、的字符是Token的分割符时，若当前状态是终止状态，说明读入的字符组成一单词；否则，说明输入不符合词法规则。2、从正规文法出发，构造状态图1.以每个非终结符为状态结点，开始符号对应初态 S；2.增设一个终态 T；3.对于规则 AaB，画从状态 A 到 B 的弧，标为 a；4.对于规则 Aa，画从状态 A 到终态 T 的弧，标为 a。* 对于规则 Ars*，画从状态 A 到状态 N 的弧，标为 r和状态N到N的标记为s的弧AsrABaAa例 3-6 语言无符号整数的识别1、正规定义式描述八进制数: ( OCT，值 )oct0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十

15、进制数: ( DEC，值 )dec(1|.|9)(0|.|9)* |0十六进制数: ( HEX，值 )hex0 x(0|1|.|9|a|.|f|A|F)(0|.|9|a|.|f |A|F)*2、识别不同进制数的状态图342100-70-7(其它)56101-90-9 (其它)十进制整数八进制整数oct0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*dec(1|.|9)(0|.|9)* |02、识别不同进制数的状态图910810 (其它)十六进制整数7x0-9,a-f0-9,a-f状态图合并1、从开始状态出发；2、选择输入符号，构成目标状态集3、从新状态集出发，重复1、2

16、hex0 x(0|1|.|9|a|.|f|A|F)(0|.|9|a|.|f |A|F)*（HEX，值）（OCT，值）3、语言无符号整数识别的状态图9,10810其他2,6,7x0-9 ,a-f0-9,a-f 3,40-70-7其他51-90-9其他（DEC，值）其他3.6 词法分析程序的设计与实现状态转移图教材P68状态转移图的实现教材P68-72子程序 scan( )输入：字符流输出：Symbol:单词种别Attr:属性（全局变量）数据结构与子例程数据结构ch 当前输入字符token 输入缓冲区(字符数组)symbol 单词种别（子程序的返回值）attr 属性（全局变量）子例程Lookup(

17、token):将 token 存入符号表，返回入口指针isKeyword(token):判别 token是关键字？返回关键字种别或 -1getchar():从输入缓冲区中读入一个字符放入chisLetter() isalpha() 例3-3的状态图的实现算法1. getchar()2. WHILE ch 是空格/跳过空格2.1 DO getchar();3. CASE ch OF4. isdigit(ch) :4.1 chtoken; getchar();4.2 WHILE isdigit(ch) DO chtoken; getchar();4.3 输入指针回退一个字符；4.4 将token中

18、的字符串变成数值attr4.5 返回 NUM5. isalpha(ch) :5.1 chtoken; getchar();5.2 WHILE isalpha(ch) OR isdigit(ch) DO chtoken; getchar();5.3输入指针回退一个字符;5.4 key = isKeyword(token);5.5 IF key0 THEN 返回 key5.6 Lookup(token)attr;5.7 返回 IDN6 : : getchar(); 6.1 IF ch等于= THEN 返回 ASG6.2 出错处理7 + : 返回 ADD8 - : 返回 SUB9 * : 返回 MU

19、L10 / : 返回 DIV11 = : 返回 EQ12 : 返回 GT13 : 返回 LT14 ( : 返回 LP15 ) : 返回 RP16 ; : 返回 SEMI17 其它 : 出错处理18 END OF CASE需要说明的问题缓冲区预处理，超前搜索关键字的处理，符号表的实现Lookup：查找效率，算法的优化实现词法错误处理由于高级语言的词组成的集合为3型语言，所以，这里讨论的词法分析技术可以用于处理所有的3型语言，也就是所有的可以用3型文法描述的语言。如：信息检索系统的查询语言、命令语言等3LEX简介：实现过程Lex源程序Lex.yy.cLex编译器词法分析器LLex.yy.cC编译器

20、Token序列词法分析器L输入流LEX简介：Lex程序结构声明部分(正规定义式)%转换规则(识别规则)%辅助过程%常量定义%正规定义扫描器的自动生成：LEX简介1、正规定义式letterA|B|C|Z|a|b|c|zdigit0|1|2|9identifierletter(letter|digit)*integerdigit(digit)* 2、识别规则正规式动作描述token1action1token2action2tokennactionn%#include #include #include #define BEGIN 1#define END 2 #define IF 3#define

21、 THEN 4#define ELSE 5#define ID 6#define INT 7#define LT 8#define LE 9#define EQ 10#define NE 11#define GT 12#define GE 13%digit 0-9alpha a-zA-Zalnum a-zA-Z0-9%begin OUT(BEGIN,NULL); end OUT(END,NULL); if OUT(IF,NULL); then OUT(THEN,NULL); else OUT(ELSE,NULL); alphaalnum* OUT(ID,yytext); digit+ OUT(

22、INT,yytext); “” OUT(LT,NULL); “=” OUT(LE,NULL); “=” OUT(EQ,NULL); “” OUT(NE,NULL); “” OUT(GT,NULL); “=” OUT(GE,NULL); %OUT(int c, char *val)LEX二义性问题的两条原则1.最长匹配原则 在识别单词过程中，有一字符串 x x x x x 根据最长匹配原则，应识别为这是 一个符合Pk规则的单词， 而不是Pj和Pi规则的单词。PjPiPk2.优先匹配原则 如有一字符串，有两条规则可以同时匹配时，那么用规则序列中位于前面的规则相匹配，所以排列在最前面的规则优先权最高。如:begin:=LEX的功能是根据LEX源程序构造一个词法分析程序，该词法分析器实质上是一个有穷自动机。LEX生成的词法分析程