词法分析器的作用
- 读入字符流，组成词素，输出词法单元
- 过滤空白、换行、制表符、注释
- 将词素添加到符号表
- 逻辑上独立于语法分析，但通常和语法分析处于同一趟
- 独立词法分析
- 概念
- 词法单元 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$
词法分析的识别（状态转换图）
- 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
- 基本规则部分
- 归纳部分
- NFA 合并：引入新的开始状态
- 转化为 DFA 中一个状态包含 NFA 中不同的结束状态：冲突
- 关键字是其它模式的一个特例（优先选择特例）
- DFA 状态数量最小化
- 状态的可区分：如果存在串 $x$ 使从 $s1$ 和 $s2$ 一个到达接受另一个到达非接受状态，则 $x$ 区分 $s1$ 和 $s2$
- 最小化算法
- 基本步骤：接受和非接受状态
- 归纳步骤：$s$ 和 $t$ 可区分，且 $s’$ 到 $s$，$t’$ 到 $t$ 有标号 $a$ 的边， $s’$ 和 $t’$ 可区分
- 最终没有区分开的态等价
- 死状态：未定义时到达的状态