词法分析主要是读入远程的输入字符,组成词素,生成词法单元序列,每个词法单元对应一个词素。
词法分析的主要任务
词法分析的主要任务是从左向右逐行扫描源程序的字符,识别出各个单词,确定单词的类型。
将识别出的单词转换成统一的机内表示——词法单元(token)形式
名词解释
词法单元:由词法单元名和可选的属性组成;譬如关键字可以是一个词法单元;或者是代表标识符、数字常量、字符常量等。
模式:一个词法单元的词素所具有的所有可能的形式。
词素:源程序的一个具体的字符序列,能够匹配某个模式,并被词法分析器识别。
正规式
定义
正规式又称正则表达式, 是一种特殊的字符串用来描述一类的字符串的集合。我们把可用正规式描述(其结构)的语言称为正规语言或正规集。
字母表:符号的有限集合, 例: $\sum$ = { 0, 1 }
串:符号的有穷序列,例:0110, \varepsilon
语言:字母表上的一个串集 { \varepsilon , 0, 00, 000, …}, { \varepsilon }, \phi
句子:属于语言的串
在词法分析中,最重要的语言上运算是并、连接和闭包运算。下面是运算的正规定义:
正规式举例
如果字母集 $\sum$ = {a, b}
–则a | b表示的语言是 {a, b}
–(a | b) (a | b ) 表示的语言是{aa, ab, ba, bb}
–aa | ab | ba | bb表示的语言是 {aa, ab, ba, bb}
–a* 由字母a构成的所有串集
–(a | b)* 由a和b构成的所有串集
C语言中无符号整数的RE
- 十进制
(1|…|9)(0|…|9)*|0 - 八进制
0(1|…|7)(0|…|7)* - 十六进制
0x(1|…|9|a|…|f|A|…|F)(0|…|9|a|…|f|A|…|F)*RE的代数定律
定律 描述 r*=(r $\varepsilon$) r*=r *具有幂等性 正则文法与正则表达式等价
状态转换图
定义
在定义好正则表达式之后,怎么基于正则表达式构造代码来检查输入字符串,并返回和模式匹配的词素呢?作为构造词法分析器的中间步骤,首先将模式转换为具有特定风格的流图,称为“状态转换图”。
状态转换图(transitiondiagram)包括称为状态(state)的节点,图中还包括有向边,每条边上面有一个或多个标号,代表从一个状态转到另一个状态的条件。转换图的每一个状态代表了词法分析器扫描输入串的过程中可能遇到的情况。
重要约定
状态转换图重要约定如下:
- 某些状态被称为接收状态或者最终状态,这些状态表明已经找到了一个词素,可以有多个接收状态。
- 如果相应的词素并不包括在最后一步使我们到达接受状态的符号,那么可以在该接受状态附近加一个*。
- 有一个状态被指定为开始状态,也成为初始状态,该状态由一条没有出发节点的,标号为start的边指明。在读入任何输入符号之前,状态转换图总是处于开始状态。
存在问题
转换图可能存在的问题是,会将保留的关键字作为标识符识别出来。
问题可以通过两种方式解决。
- 初始化时将各个保留字填入符号表。符号表中的相关字段会指出该串不是普通的标识符,并指出它们代表的词法单元,当使用installID函数向符号表中插入条目时,根据匹配的词素以及符号表中的信息,就可以判断出来是一般的标识符还是关键字。
- 为每个关键字建立单独的状态转换图。
如果使用这种方式,需要制定词法单元之间的优先级,使得then作为关键字而不是标识符返回。