第3章词法分析和词法分析程序.pps

文档介绍：编译原理
第三章词法分析和词法分析程序
设计扫描器时应考虑的问题
词法分析程序亦称为扫描器
任务:扫描程序,识别单词
扫描器的输出是语法分析程序的输入
词法分析的必要性
描述单词的结构比其它语法结构简单,仅用3型文法就够了;
将单词识别从语法分析识别分离出来,可采用更有效的工具实现;
有些语言的单词识别与前后文相关,不宜将其与语法分析合并;
使编译程序各部分独立出来,有利于设计、调试和维护
单词符号的内部表示
常用的内部表示方法: (class,value)
为便于阅读,常用助记符(或常量标识符、宏定义等)表示class。
在识别出变量名、函数(过程)名时,还应进行查填符号表的工作。
识别标识符的若干约定和策略
在允许长度下,应按最长匹配原则进行识别
有时需要超前扫描来进行单词识别。
由正规文法构造状态转换图
例:正规文法如下:
正规文法和状态转换图
<无符号数> → d.<余留无符号数>
<无符号数> →.<十进小数>
<无符号数> → E<指数部分>
<余留无符号数> → d<余留无符号数>
<余留无符号数> →.<十进小数>
<余留无符号数> → E<指数部分>
<余留无符号数> →
<十进小数> → d<余留十进小数>
<余留十进小数> → d<余留十进小数>
<余留十进小数> → E<指数部分>
<余留十进小数> →
<指数部分> → d<余留整指数>
<指数部分> →+<整指数>
<指数部分> →-<整指数>
<整指数> → d<余留整指数>
<余留整指数> → d<余留整指数>
<余留整指数> →
由正规文法构造状态转换图
所对应的状态转换图
0
1
2
3
4
5
6
d
d
•
•
d
d
d
d
d
E
E
+ | -
无符号数的状态转换图
由正规文法构造状态转换图
程序设计语言的单词都能用正规文法描述
一般说来,凡能用正规文法描述的语言,均可由某种有限状态算法——状态转换图进行分析
状态转换图:
有向图(一个初态+N个终态)
射出结点,进入结点
正规文法和状态转换图
构造状态转换图(一)
由右线性文法构造状态转换图
|VN|=K,则所要构造的状态转换图共有K+1个状态(结点)
构造规则: AaB, Aa, A
A
F
B
a
a
A
构造状态转换图(二)
2. 识别串:字符串w=a1a2…an, aiVT
实际:建立推导 S* w
(1) 自顶向下
(2) 从S出发:a1a2…akAk
(3) 对任一句子y,必存在一条路从S至F,各标记相连即y
显然,若我们从初态出发,分别沿一切可能的路径到达终态结点,并将中径中矢线上所标记的字符依次连接起来,便得到状态转换图所能识别的全部符号串,这些符号串组成的集合构成了该文法识别的语言——句子必有一条从初态S到终态F的路径,此路径上各矢线的标记依次拼接起来所组成的符号串恰为该句子