编译原理课程第2讲

《编译原理课程第2讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、温故知新编译原理的内容及学习意义翻译器、编译器的定义编译器的阶段划分及前端、后端的概念“遍”的概念第二章词法分析本章内容词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务围绕词法分析器的自动生成展开介绍正规式、状态转换图和有限自动机概念词法分析器语法分析器符号表记号取下一个记号源程序词法分析器的功能：词法分析器记号（token）流源代码2.1词法记号及属性2.1.1词法记号、模式、词法单元词法单元：又称单词，是源程序中的字符串。词法记号：满足某种规则的词法单元，采用同一种记法——词法记号。该规则称为模式。模式：描述词法单元与词法记号

2、对应关系的规则。是描述源程序中某个记号的词法单元集合的规则。源程序字符流顺序组合词法单元词法记号模式2.1词法记号及属性2.1.1词法记号、模式、词法单元源程序字符流顺序组合词法单元词法记号模式例：varcount:integer;count=5;词法单元2.1词法记号及属性2.1.1词法记号、模式、词法单元词法记号词法单元例举模式的非形式描述varvarvarforforforrelation<,<=,=,…<或<=或=或…idsum,count,D5由字母开头的字母数字串num3.1,10,2.8E12任何数值常数literal“seg.error”

3、引号“和”之间的任意字符串，但引号本身除外常见记号及模式的例子：2.1词法记号及属性2.1.1词法记号、模式、词法单元词法记号词法单元例举模式的非形式描述relation<,<=,=,…<或<=或=或…idsum,count,D5由字母开头的字母数字串名词大连软件大黑山表示名称的词连词和与或和与或….词法记号词法单元例举模式的非形式化描述词法记号词法单元例举模式的非形式描述中国人江泽民毛泽东具有中国国籍的人美国人布什克林顿具有美国国籍的人2.1词法记号及属性历史上词法定义中的一些问题忽略空格带来的困难DO8I3.75DO8I3.75DO8I3,75

4、关键字是否保留IFTHENTHENTHEN=ELSE；ELSE…2.1词法记号及属性2.1.2词法记号的属性position:=initial+rate*60的记号和属性值：id，指向符号表中position条目的指针assign_op，id，指向符号表中initial条目的指针add_op，+id，指向符号表中rate条目的指针mul_op,*num，整数值602.1词法记号及属性2.1.2词法记号的属性练习题（要求使用伪代码给出算法）：编写一个程序，用于统计文件中单词的总数，不同单词的数目。eg:IloveDalianan

5、dIloveDLUT单词总数：7不同单词数目：52.1词法记号及属性2.1.3词法错误词法分析器对源程序采取非常局部的观点,难以发现下面的错误fi(a==f(x))…但是也有例外，如在实数是a.b格式下，可以发现下面的错误123.2.1词法记号及属性2.1.3词法错误恢复策略“紧急方式”错误修补尝试删除一个多余的字符插入一个遗漏的字符用一个正确的字符代替一个不正确的字符交换两个相邻的字符2.2词法记号的描述与识别2.2.1串和语言字母表/字符类：符号（英文字母、标点符号等）的有限集合，例：={0,1}串：符号的有穷序列，例：0110,语言：字母表上的

6、一个串集{,0,00,000,…},{},句子/字：属于语言的串字母组合串语言集合集合字母表词法单元记号模式长度为0的空串长度的表示

7、a

8、2.2词法记号的描述与识别2.2.1串和语言串的运算连接xy，s=s=s积（指数）s0为，si为si-1s（i>0）2.2词法记号的描述与识别语言的运算和：L∪M={s

9、sL或sM}连接：LM={st

10、sL且tM}指数：L0是{}，Li是Li-1L闭包：L=L0∪L1∪L2∪…正闭包：L+=L1∪L2∪…例2.2（p17）L:{A,B,…,Z,a,b,…,z},D:{0,1,…,9}L∪D,LD

11、,L6,L*,L(L∪D)*,D+2.2词法记号的描述与识别2.2.2正规式正规式：按照一组定义规则，由较简单的正规式构成的，每个正规式r表示一个语言L(r).定义规则说明L(r)是怎样以各种方式从r的子正规式所表示的语言组合而成。正规式用来表示简单的语言，叫做正规集。正规式是用于说明词法单元如何对应到词法记号的模式。与非形式化的描述相比，正规式更具形式化，更加精确。2.2词法记号的描述与识别2.2.2正规式正规式定义的语言备注{}a{a}a(r)

12、(s)L(r)∪L(s)r和s是正规式(r)(s)L(r)L(s)r和s是正规式(r)*(L(r)

13、)*r是正规式(r)L(r)r是正规式运算符的优先级：*>连接运算>

14、((a)(