词法分析
对词法分析器的要求
词法分析器的功能和输出形式
功能：
输入源程序，输出单词符号
单词符号:
关键字:保留字，基本字(全体视为一种或一字一种)
标识符：变量名，数组名(统归为一种)
常数： 整形，实型(按类型分种(整，实，布尔…))
运算符：+,-,*,/,…(一符一种或具有一定共性的运算符视为一种)
界符：;，,，(，)，…(一符一种)
输出：
二元式形式（单词种别，单词符号的属性值）
词法分析器的设计
一、输入，预处理
输入串放入输入缓冲区
预处理：可剔掉一些无用符号：空白符，跳格符，回车符，换行符等
二、单词符号的识别：超前搜索
标识符：以字母开头的“字母|数字”串。
三、状态转换图
有限方向图，结点表示状态，状态间用箭弧连接，箭弧上的标记（符号）代表射出结点状态下有可能出现的输入字符或字符类。
一个状态转换图可用于识别（或接受）一定字符串。
正规表达式与有限自动机
正规式与正规集
定义： 
例：Σ={a,b}
①a为首的任意符号串集合
正规式：a(a|b)*
②a为尾的任意符号串集合
正规式： (a|b)*a
③每个a至少有一个b紧跟其后的符号串集合
正规式为：b*(abb*)* 或b*(ab+)*
两正规式表示的正规集相同，则二者等价。
2.性质
①U|V=V|U
②U|(V|W)=(U|V)|W
③U(VW)=(UV)W
④U(V|W)=UV|UW (V|W)U=VU|WU
⑤εU=Uε=U
DFA(确定有限自动机)
DFA M含有m个状态，n个输入字符，则状态转换图有m个结点，每个结点至多有n条箭弧射出，每条箭弧用Σ中一个不同的输入字符做标记 
- 对∑*中任意字α，若存在从初态到某一终态的通路，且通路上所有弧标记符连接成的字等于α，则称α可为DFA所识别(读出或接受)。
- 若M的初态结点同时也是终态结点，则空字ε可为M所识别。
- DFA M所能识别的字的全体记为L(M)。
NFA(不确定有限自动机)
定义：
DFA和NFA区别
- DFA初态唯一，NFA不一定
- DFA后继唯一，NAF不一定
FA的等价
- 已知两FA，M1，M2 若L(M1)=L(M2)，则称M1等价于M2。
- 任意NFA,存在DFA，使L(DFA)=L(NFA)。
NFA确定化(NFA→DFA)——子集法
相关运算
