Lexical Analysis

词法分析器的作用

读入字符流，组成词素，输出词法单元
- 过滤空白、换行、制表符、注释
- 将词素添加到符号表
- 逻辑上独立于语法分析，但通常和语法分析处于同一趟
独立词法分析
- 简化设计
- 提高编译器效率
- 增强编译器的可移植性
概念
- 词法单元 Token：<单元名，属性>
- 模式 Pattern：描述了一类 Token 可能具有的形式
- 词素 Lexeme：源程序中的字符序列

词法单元的规约（正则表达式）

概念
- 字符表：一个有穷符号的集合
- 串：符号的有穷序列
- 语言：给定字母表上串的可数集合
- 前缀，后缀，子串
- 连接： $xy$
- 指数运算： $x^n$
语言运算
- $L\cup M$
- $LM$
- $L^*=\cup_{i=0}^\infty L^i$
- $L^+=\cup_{i=1}^\infty L^i$
正则表达式
- 基本部分
  - $L(\epsilon)=\{\epsilon\}$
  - $L(a)=\{a\}$
- 归纳部分
  - $L((r)|(s))=L(r)\cup L(s)$
  - $L((r)(s))=L(r)L(s)$
  - $L((r)^*)=L(r)^*$
  - $L((r))=L(r)$
- 运算优先级 $*$ 连接 $|$
- 扩展
  - $r+$ = $rr^*$
  - $r?$ = $\epsilon|r$
  - $[a_1\cdots a_n]$ = $a_1|a_2\cdots|a_n$
正则集合：可以用正则表达式定义的语言
正则定义： $d_1\rightarrow r_1$ $d_{1} \to r_{1}$
- 不能重复定义，不能与字母表重复

词法分析的识别（状态转换图）

Transition diagram
- State: 识别词素时可能出现的情况
  - 状态是已处理部分的总结
  - 开始状态
  - 终止状态（带星号表示回退一个符号）
- Edge：一个符号或多个符号
保留字和标识符的处理
- 法一：在符号表中先填保留字
- 法二：建立高优先级的保留字
构造词法分析器
- State 记录当前状态
- switch 跳转状态
- if 对比边
- 失败 fail()
- 接受状态返回词法单元（*标记回退 forward 指针）

词法分析器生成工具及设计

Lex/Flex 编译器：lex.l (Lex compiler)-> lex.yy.c (C compiler)-> a.out
声明部分
- 常量
- 正则定义
转换规则
- 模式 { 动作 }
辅助函数
- 各个动作的函数
各部分用 %% 隔开
%{ %} 之间直接拷贝

%{
  //comment
}%
 
ws { \t\n}
 
%%
 
{ws} {/*no action*/}
if {return(IF)}
{id} {yylval = (int) installID(); return (ID);}
 
%%
 
int installID() {/* install lexeme */}
int installNum() {}

冲突解决
- 多个前缀匹配：选择最长的前缀
- 多个模式匹配：选择前面的模式

有穷自动机

有穷自动机：只回答 Yes/No
- 状态有穷
- 不确定有穷自动机 (NFA)：边上符号限制，一个符号可出现在离开同一个状态的多条边上， $\epsilon$ 可以做符号
- 确定有穷自动机 (DFA)
每个可以用正则表达式描述的语言，均可以用 NFA 和 DFA 来识别，反之亦然
NFA 定义
- 有穷状态集合 $S$
- 输入符号集合 $\Sigma$
- 转换函数： $\Sigma\cup\{\epsilon\}$
- 开始状态： $s_0$
- 接受状态： $F$
转换表表示法
- 行头：条件
- 列头：状态

正则表达式到 DFA

NFA -> DFA：子集构造法
- 构造得到的 DFA 每个状态和 NFA 的状态子集对应
- 最坏情况： $2^n$
- 基本操作
  - $\epsilon$ -closure( $s$ )：从状态 $s$ 开始，只能通过 $\epsilon$ 转换到的状态
  - $\epsilon$ -closure( $T$ )
  - move( $T,a$ )
正则表达式 -> NFA
- 基本规则部分
  - 表达式 $\epsilon$
  - 表达式 $a$
- 归纳部分
  - $s|t$
  - $st$
  - $s^*$
- NFA 合并：引入新的开始状态
  - 转化为 DFA 中一个状态包含 NFA 中不同的结束状态：冲突
  - 关键字是其它模式的一个特例（优先选择特例）
DFA 状态数量最小化
- 状态的可区分：如果存在串 $x$ 使从 $s1$ 和 $s2$ 一个到达接受另一个到达非接受状态，则 $x$ 区分 $s1$ 和 $s2$
- 最小化算法
  - 基本步骤：接受和非接受状态
  - 归纳步骤： $s$ 和 $t$ 可区分，且 $s'$ 到 $s$ ， $t'$ 到 $t$ 有标号 $a$ 的边， $s'$ 和 $t'$ 可区分
  - 最终没有区分开的态等价
- 死状态：未定义时到达的状态

Table of Contents

Table of Contents

Lexical Analysis

词法分析器的作用

词法单元的规约（正则表达式）

词法分析的识别（状态转换图）

词法分析器生成工具及设计

有穷自动机

正则表达式到 DFA