编译原理原理与技术

2020/1/23《编译原理与技术》讲义1编译原理与技术词法分析(1)2020/1/23《编译原理与技术》讲义2词法分析词法分析器介绍正规式与正规集有限自动机词法分析器的自动生成－Lex2020/1/23《编译原理与技术》讲义3词法分析器介绍词法分析器的功能高级语言源程序词法分析器语法分析器tokenget_next_token编译器其它阶段符号表字符流记号（流）2020/1/23《编译原理与技术》讲义4词法分析器介绍词法分析器的功能读源程序，产生记号序列剥去源程序中的注释（块、行）和“空白”符预处理－宏处理与文件包含2020/1/23《编译原理与技术》讲义5词法分析器介绍词法分析器作为独立子程序简化设计提高编译效率增强可移植性2020/1/23《编译原理与技术》讲义6词法分析器介绍记号、模式与单词记号－同类单词的总称模式－描述构成记号的字符串的规则单词－源程序中能匹配任一记号的字符串2020/1/23《编译原理与技术》讲义7程序语言的记号（1）记号单词模式关键字WHILEwhilewhileFORforfor标识符IDtemp,i,max字母开头的字母数字串常数NUM3.14100数字字符串{.数字字符串}2020/1/23《编译原理与技术》讲义8程序语言的记号（2）记号单词模式运算符MUL**GT界符,,,串常量STRING“hello”‘there’双（单）引号中间的字符串（不包括引号本身）2020/1/23《编译原理与技术》讲义9词法分析器介绍词法分析器的二元输出记号，记号的属性单词（字符串）的类别匹配记号的单词多于一个时，须提供额外的信息以区别之2020/1/23《编译原理与技术》讲义10词法分析器介绍词法分析器的二元输出记号，记号的属性记号影响语法分析的决策属性（如类型、偏移）则关系到记号的翻译2020/1/23《编译原理与技术》讲义11词法分析器介绍e.g.1pascal源程序片段：beginlength:=length+1;iflength20thenread(nextch);end;2020/1/23《编译原理与技术》讲义12e.g.1pascal源程序片段的字符流(SP表示空格)begin\n\tlengthSP:=SPlengthSP+SP1;\n\tifSPlength20SPthenSPread(nextch);\nend;2020/1/23《编译原理与技术》讲义13e.g.1词法分析器的输出记号流(1)BEGIN,-ID,指向符号表length条目的指针ASSIGN,-ID,指向符号表length条目的指针//不是多余的！！+,-NUM,1//属性是常量“值”本身;,-IF,-2020/1/23《编译原理与技术》讲义14e.g.1词法分析器的输出记号流(2)ID,指向符号表length条目的指针LT,-NUM,20THEN,-READ,-(,-ID,指向符号表nextch条目的指针),-END,-;,-2020/1/23《编译原理与技术》讲义15词法分析器介绍超前搜索FORTRAN中的关键字“不保留”1）DO100K=1,102）DO100K=1.103）IF(5.EQ.M)I=104）IF(5)=55有关算符的识别C/C++,java的++,--,=,!=,==等，与之对应+,-,!,=2020/1/23《编译原理与技术》讲义16词法分析器介绍词法错误可检测非法字符的出现ifVSfi词法分析器的设计手工编写－采用汇编语言或高级语言自动生成－Lex2020/1/23《编译原理与技术》讲义17词法分析器介绍状态转换图用于记号的识别。状态之间用带有标记（字符）的有向边连接；每读入一个字符会引起状态变化，直至单词（记号）被识别出来。开始状态：状态转换图的初始状态（尚未读字符）接受状态：某个单词被识别时所处的状态（终态）单词（记号）的识别过程即是从开始状态出发到某接受状态的变化过程。2020/1/23《编译原理与技术》讲义18词法分析器介绍状态转换图012字母其它字母或数字识别标识符的转换图*034数字其它数字识别整数的转换图*2020/1/23《编译原理与技术》讲义19词法分析器介绍状态转换图05数字.识别Pascal无符号数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它2020/1/23《编译原理与技术》讲义20词法分析器介绍状态转换图05数字.（红线）识别Pascal无符号整数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它2020/1/23《编译原理与技术》讲义21词法分析器介绍状态转换图05数字.识别Pascal无符号小数的转换图*数字67891011数字数字E+|-数字数字其它E数字其它其它2020/1/23《编译原理与技术》讲义22状态转换图的实现e.g.2简单词法分析的转换图（识别关键字、标识符、无符号整数、算符和界符）01空白符（\n,\t,SP）字母或数字字母非字母数字2*return(ID,符号表条目指针）orreturn(关键字，－）3数字数字非数字字符4*return(NUM,常量值或者常量表条目指针）tobecontinued2020/1/23《编译原理与技术》讲义23e.g.2简单词法分析的转换图+5return（+,－）-6return（-,－）7*非*字符8*return（*,－）9return（**,－）*tobecontinued2020/1/23《编译原理与技术》讲义24e.g.2简单词法分析的转换图10=11return（LE,－）12return（NE,－）13return（LT,－）其它字符=14return（EQ,－）*15=16*return（GE,－）17return（GT,－）其它字符tobecontinued2020/1/23《编译原理与技术》讲义25e.g.2简单词法分析的转换图18：=19return（ASSIGN,－）20return（:,－）其它字符*；21return（；,－）其它22Error()简单扫描程序状态转换程序2020/1/23《编译原理与技术》讲义26串与语言语言语言L＝{s|s是∑上任一字符串}，s称为语言L的一个句子。字母表∑－符号/字符的非空有限集合e.g.二进制数的∑＝{0,1}，而十进制数的∑＝{0,1,…,9}∑*－表示∑上所有字符串的集合；L∑*字符串－∑上若干字符组成的有穷序列2020/1/23《编译原理与技术》讲义27串与语言语言字符串e.g.∑＝{0,1}上的0，1串（二进制数）如0111，10101；∑＝{a,b}上的a,b,aa,abab,…空串－，∈∑*，串长－|s|＝{s中所含字符的个数}，||=0串的连接运算－任意串x，y，一般地，xyyx，x=x串的前缀－任意串x，从其第一个字符（最左字符）起的字符序列是其前缀。亦是。e.g.x=abc,则，a，ab，abc均是x的前缀2020/1/23《编译原理与技术》讲义28语言的运算语言的运算描述运算语言L和语言M连接（积）LM={xy|x∈L且y∈M}合并（和）L∪M={x|x∈L或x∈M}闭包L*=L0∪L1∪L2∪…=正闭包L+=L1∪L2∪L3∪…=0iiL1iiL2020/1/23《编译原理与技术》讲义29语言e.g.L={a,b,…,z},D={0,1,…,9},B={_}L∪D={…}LD={…}L*={…}L(L∪D)*={…}(L∪B)(L∪D∪B)*={…}D+={…}2020/1/23《编译原理与技术》讲义30正规式与正规集正规式－用于描述记号的构成规则正规集－正规式描述的语言（匹配正规式的串集）正规式正规集{}∅∅a∈{a}2020/1/23《编译原理与技术》讲义31正规式与正规集正规式正规集R|SL(R)∪L(S)R·SL(R)·L(S)R*(L(R))*(R)L(R)如果R和S是上的正规式，分别对应上的正规集L(R)和L(S)，则2020/1/23《编译原理与技术》讲义32正规式与正规集运算符优先级结合性或|低左结合连接·高左结合闭包*最高左结合上的正规式，其运算有|、·和*2020/1/23《编译原理与技术》讲义33正规式与正规集代数定律描述交换律R|S＝S|R结合律R|(S|T)=(R|S)|TR(ST)=(RS)T分配律R(S|T)=(RS)|(RT)(R|S)T=(RT)|(ST)同一律R=R=R上的正规式，满足如下代数定律－－2020/1/23《编译原理与技术》讲义34正规式与正规集上的正规式，也具有如下代数定律－－(R*)*=R*(R|)*=R*R+=RR*2020/1/23《编译原理与技术》讲义35正规式与正规集e.g.3设={a,b},则正规式正规集a(a|b)*上以a开头的串集ba*上以b开头后跟任意个a的串集(a|b)*a(a|b)(a|b)上倒数第三个字符是a的串集2020/1/23《编译原理与技术》讲义36正规式与正规集e.g.3设={a,b}，R=a(a|b)*，事实上有L(R)=L(a(a|b)*)=L(a)L((a|b)*)=L(a)(L(a|b))*=L(a)(L(a)∪L(b))*={a}({a}∪{b})*={a}({a,b})*={a}{,a,b,aa,ab,ba,bb,abb,…}={a,aa,ab,aaa,aab,aba,abb,aabb,…}即L(R)是上以a开头的串集。2020/1/23《编译原理与技术》讲义37正规式与正规集正规定义d1r1d2r2…dnrn各个di的名字不同；每个ri是∪{d1,d2,…di-1}上的正规式2020/1/23《编译原理与技术》讲义38正规式与正规集e.g.4Pascal标识符letterA|B|…|Z|a|b|…|zdigit0|1|…|9idletter(letter|digit)*英文字母集合十进制数字集合标识符的正规定义2020/1/23《编译原理与技术》讲义39正规式与正规集e.g.5Pascal无符号数digit0|1|…|9digitsdigitdigit*fraction‘.’digits|exponent(E(+|-|))digits|numdigitsfractionexponent数字串集合小数部分（可空）指数部分（可空）2020/1/23《编译原理与技术》讲义40正规式与正规集e.g.6email地址：[e-mail]letterletter*field(’.’name)*emailname‘@’namefield