编译原理234词法详解.pptx

引论复习第二章主要内容词法分析的软件工程引入的数学模型正规式状态转换图2第二章词法分析while，_(，_id，指向i的符号表指针=，_id，指向j的符号表指针)，_id，指向i的符号表指针--，_；，_源程序扫描器scanner1、关键字2、标识符5、界符4、运算符3、常数由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：Pascal中的begin，end，if等。界符：如逗号、分号、括号、/*，*/等。它是确定的。运算符：如+、-、*、/等。它是确定的。常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。用来表示各种名字，如变量名、数组名、过程名等。它是不限的。词法分析与语法分析的关系词法分析器的设计词法记号、模式、词法单元记号名 词法单元例举 模式的非形式描述if if 字符i,ffor for 字符f,o,rrelation ,=,=,… 或=或=或…id sum,D5 由字母开头的字母数字串number 3.1,2.8E12 任何数值常数literal “seg.error” “和”之间任意不含 引号本身的字符串 id，指向符号表中position条目的指针 assign_op id，指向符号表中initial条目的指针 add_op id，指向符号表中rate条目的指针 mul_op number，整数值60position=initial+rate*60的记号和属性值例题position=initial+rate*60id,1=id,2+id,3*60字符流语法分析position=initial+rate*60id,1=id,2+id,3*60position=initial+rate*60id,1=id,2+id,3*60三地址中间代码MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1历史上词法定义中的一些问题忽略空格带来的困难 DO8I=3.75 等同于 DO8I=3.75DO8I=3,75关键字不保留 IFTHENTHENTHEN=ELSE；ELSE…关键字、保留字和标准标识符的区别保留字是语言预先确定了含义的词法单元标准标识符也是预先确定了含义的标识符，但程序可以重新声明它的含义词法错误词法分析器对源程序采取非常局部的观点例：难以发现下面的错误 fi(a==f(x))…在实数是“数字串.数字串”格式下，可以发现下面的错误 123.x紧急方式的错误恢复 删掉当前若干个字符，直至能读出正确的记号错误修补 进行增、删、替换和交换字符的尝试2.2.1串和语言字母表：符号的有限集合，例：∑={0,1}串：符号的有穷序列，例：0110,ε语言：字母表上的一个串集 {ε,0,00,000,…},{ε},∅句子：属于语言的串串的运算连接（积）: xy，sε=εs=s幂: s0为ε，si为si-1s（i0）语言的运算并： 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+含有偶数个0和偶数个1的01串(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*作业解答2.3叙述由下列正规式描述的语言0(0|1)*0((ε|0)1*)*(0|1)*0(0|1)(0|1)0*10*10*10*(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*23作业0(0|1)*0((ε|0)1*)*(0|1)*0(0|1)(0|1)0*10*10*10*(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*24要点：1）字符串的长度2）特定字符串出现在特定位置3）肯定出现（不出现）的字符串以0开头和结尾的长度至少是2的01串所有的01串倒数第三位是0的01串含有3个1的01串含有偶数个0和偶数个1的01串不含字串011的01串例题写出正规定义不含字串001的01串25每个0的后面紧挨着这个0的1至多有一个：(0|01)*在最前面一个0的前面可以有任意多个1：1*(0|01)*每个1的前面紧挨着这个1的0至多有一个:(1|01)*在最后一个1的后面可以有任意多个0：(1|01)*0*2.2.3正规定义对正规式命名，使表示简洁 d1→r1 d2→r2 ... dn→rn各个di的名字都不同每个ri都是∑∪{d1,d2,…,di-1}上的正规式2.2词法记号的描述与识别正规定义的例子C语言的标识符是字母、数字和下