词法分析与有限自动机.ppt

该【词法分析与有限自动机 】是由【qingqihe】上传分享，文档一共【93】页，该文档可以免费在线阅读，需要了解更多关于【词法分析与有限自动机 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。词法分析与有限自动机演示文稿
当前1页,总共93页。
优选词法分析与有限自动机
当前2页,总共93页。
教学内容




、正规文法和有限自动机的等价性
——LEX

当前3页,总共93页。

词法分析器的任务和输出形式
1
将词法分析工作分离的考虑
2
当前4页,总共93页。
1、词法分析器的任务和输出形式
(1)词法分析器的任务
自左至右逐个字符地对源程序进行扫描,按语言的构词规则识别出一个个单词,把作为字符串的源程序改造为单词符号串的中间程序。
字符串流
单词流
源语言程序
单词符号
当前5页,总共93页。
1、词法分析器的任务和输出形式
(2)单词符号
单词符号是程序设计语言的基本语法单位和最小语义单位。
(3)单词符号的种类

标识符:标记常量、变量、函数等的名字,如fun、i
关键字:具有固定意义的标识符,如if、while、for
常数:各种类型的常数,,布尔型TRUE
运算符:如+、-、*、/、<=、<、>、>=、==
界符:如,、;、(、),{,}
单词符号
当前6页,总共93页。
1、词法分析器的任务和输出形式
(4)单词符号的输出形式
二元式:(单词种别,单词符号的属性值)
表示单词的种类,它是语法分析所需要的信息。一个语言的单词符号如何划分种类、分为几类、如何编码都属于技术性问题,主要取决于处理上的方便。通常让每种单词对应一个整数码,这样可最大限度地把各个单词区别开来。
用来区分该类单词中的哪一个单词,它是单词本身的机内编码。单词符号的属性是指单词符号的特性或特征。属性值是反应特性或特征的值。例如,对于某个标识符,常将存放它的有关信息的符号表项的指针作为其属性值;而对于某个常数,则是将存放它的常数表项的指针作为其属性值。
当前7页,总共93页。
1、词法分析器的任务和输出形式
(4)单词符号的输出形式
常用单词种别编码方案
标识符:一种
关键字:全体视为一种或一字一种
常数:按类型分种,如整数、实数、布尔型
运算符:一符一种
界符:一符一种
单词种别编码
当前8页,总共93页。
1、词法分析器的任务和输出形式
(5)举例
假定单词类别用整数编码,标识符、常数、关键字、运算符和界符的编码依次为1、2、3、4、5。C++语句if(a>=90)b=c;在经过词法分析器处理后输出的二元式及其单词表示如下:
二元式 单词
(3,’if’) 关键字if
(5,’(’) 界符(
(1,指向a的符号表项的指针) 标识符a
(4,’>=’) 运算符>=
(2,90) 常数90
(5,’)’) 界符)
(1,指向b的符号表项的指针) 标识符b
(4,’=’) 运算符=
(1,指向c的符号表项的指针) 标识符c
(5,’;’) 界符;
返回
当前9页,总共93页。
2、将词法分析工作分离的考虑
(1)将词法分析器设计为语法分析器的子程序
在实现编译程序时,常将词法分析程序从语法分析中独立出来,将其设计为语法分析器的子程序,每当语法分析器需要一个单词符号时就调用词法分析器,每一次调用,词法分析器就从输入串中识别出一个单词符号,并将该单词类别和单词值返回给语法分析器。
字符串形式
的源程序
字符
词
法
分
析
器
语
法
分
析
器
符
号
表
单词
取下一单词
当前10页,总共93页。