2023-12-17 08:24来源：m.sf1369.com作者：宇宇
赋值操作符: = 赋值符号。 += 加等赋值。 -= 减等赋值。 *= 乘等赋值。 /= 除等赋值。 运算操作符： + 加运算符 - 减运算符 * 乘运算符 / 除运算符 % 求余运算符 ++ 自增1运算符 -- 自减1运算符 关系操作符： < 小于。 <= 小于或者等于。 > 大于。 >= 大于或者等于。 == 等于。 != 不等于（大于或小于）。 逻辑操作符: ?: if-then-else & 逻辑与。位操作符。将&左右表达式按二进制按位进行与操作（同位均为1则该位为1，否则为0）。 && 与操作。 | 逻辑或。 || 或操作。 ^ XOR。 == 等于 != 不等于 ! 逻辑非操作。 关键字： 1.用于类和接口的声明：class,extends,implements,interface. 2。包引入和包声明：import,package 3.数据类型：byte,boolean,char,double,int,long,float,short. 4某些数据类型的可选值：flase,ture,null. 5.流程控制：break,case,continue,default,do,else,for,if,return,switch,while 6.异常处理：catch,finally,throw,throws,try, 7.修饰符：abstract,final,native,private,protected,public,static,synchronilzed,transient,volatitle. 8.操作符： instanceof 9.创建对象:new 10.引用：this,supper 11.方法返回类型：void * 12.保留字：const,goto 注意： 1.所有关键字均为小写； 2.程序中的标识符不能以关键字命名，（标识符：包、类、接口、变量、方法的名字。）。识别java语言的关键字，不要和其他语言如c/c++的关键字混淆。 friendly，sizeof不是java的关键字
有限自动机FA
描述程序设计语言中的单词字，进一步为词法分析程序的自动构造寻找特殊的方法和工具。
主要内容：
确定有限自动机DFA
确定有限自动机DFA的实现
非确定有限自动机NFA
NFA到DFA的转换
DFA的化简
确定有限自动机DFA
确定有限自动机（DFA：Deterministric Finite Automata ) 为一个五元组(∑,SS,S0,f,TS)，其中：
■∑是一个有穷字母表，它的每个元素称为一个输入字符；
■SS是一个有穷集，它的每个元素称为一个状态；
■S0∈ SS是唯一的一个初始状态；
■f是在SS× ∑→ SS上的转换函数
■TS?SS，是一个终止状态集，又称为接受状态集
DFA的两种表示方式
状态转换图：
结点表示状态，转换边表示转换函数，边的箭头方向指向转换函数中定义的转换方向。标识出初始状态和终止状态。
状态转换表：
可用二维数组描述。标识出初始状态和终止状态。
Trans（ SI ，a）＝ SJ
一个DFA的例子：
DFA M=({a,b},{S,U,V,Q}, S,f,{Q}),其中f定义为：
f ( S, a )=U f ( V, a )=U
f ( S, b )=V f ( V, b )=Q
f ( U, a )=Q f ( Q, a )=Q
f ( U, b )=V f ( Q, 1 )=Q
例子的状态转换图和状态转换表
DFA接受的字符串
对于∑*中的任何字符串t,若存在一条从初始结点到某一终止结点的路径，且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFA M所接受（识别）。
DFA M 所能接受的字符串的全体记为L(M).
DFA的确定性
初始状态唯一。
转换函数f:SS×∑→SS是一个单值函数，也就是说，对任何状态S∈SS,和输入符号a ∈ ∑, f(S,a)唯一地确定了下一个状态。即至多确定一个状态。
没有空边。即没有输入为ε（λ）
DFA的实现1
状态转换表的形式：
1.当前状态State置为初始状态
2.读一个字符 → CurrentChar
3.如果CurrentChar≠Eof并且T(State,CurrentChar)≠error
则当前状态转为新的状态T(State,Current)，读下一字符。
重复第3步工作。
4.如果当前字符为Eof并且当前状态属于终止状态，则接受当前字符串，程序结束。否则报错
特点：程序短小，但占用存储空间多
DFA的实现2
状态转换图的形式：
■每个状态对应一个带标号的case语句
■转向边对应goto语句
Li: case CurrentChar of
a ：goto Lj
b : goto Lk
other : Error( )
特点：程序长，但占用存储空间少
非确定有限自动机NFA
定义1：一个非确定有限自动机(NFA)A是一个五元组A=(∑,SS,S0,f,TS).其中
■∑是字母表
■SS是状态集
■S0是初始状态集
■f是转换函数，但不要求是单值的
■f: SS × (∑∪{λ}) → 2SS
■TS是终止状态集
定义2：设A是一个NFA，A= (∑,SS,S0,f,TS)
则定义L(A)为从任意初始状态到任意终止状态所接受的字符串。
L(A)={β|s0=>βs’, s0∈ S0,s’∈TS}
定义3：设A1和A2是同一个字母表上的自动机，如果有L(A1)=L(A2),则称A1和A2等价。
NFA到DFA的转换
定理1 对于每一个非确定自动机A,存在一个确定自动机A’,使得L(A)=L(A’).
转换：
符号合并: 同一状态的不同输出边标有相同的字符。
λ合并: 含有λ边
符号合并：A：NFA, A’:FA
1.令A’的初始状态为S0’=[S1,S2,…Sk],其中S1…Sk是A的全部初始状态。
2.若S’=[S1,…,Sm]是A’的一个状态，a∈∑则定义
f’(S’,a)=f(S1,a)∪f(S2,a)…∪f(Sm,a)
3.重复步骤直至不出现新的状态为止。
4.若S’=[S1,…,Sn]是A’的一个状态,且存在一个Si是A的终止状态，则令S为A’的终止状态。
λ合并 （Close(S)）
1.对S状态寻找λ边，如果有令Ss＝{S}
2.对任意状态Si∈Ss,如果有：f(Si,λ)= Sj
则消除λ边：Ss= Ss∪Sj
重复上述操作直至没有λ边
3.对a∈∑ f(Ss,a)= ∪ f(Sk,a)
Ss={S1,…,Sm},k=1,…,m.
4.如果Ss中包含初始状态则Ss也为初始状态，
如果有终止状态，则Ss为终止状态。
NFA到DFA的转换过程:
1. NFA初始状态集的λ合并集作为DFA的初始状态。
2. 对DFA中一状态S，对a∈∑,进行符号合并和λ合并得到的状态设为S’,定义DFA的转换函数为f(S,a)=S’.
3. 直至没有新状态产生为止。
上面的例子从NFA转化为DFA
DFA的化简（极小化）
状态等价
对DFA中的两个状态S1和S2，如果将它们看作是初始状态，所接受的符号串相同，则定义S1和S2是等价的。
方法
状态合并法
状态分离法
DFA的化简
状态合并法（状态吸收方法）
寻找等价状态S1和S2
如果S2为初始状态，则S1和S2对调
S2的出现修改为S1
删除状态S2。
状态分离法
初始化为两个不等价状态集组：非终止状态组和终止状态组。
对每组中的某个状态分离出与之不等价的状态组，直至所有状态组内部状态都等价为止。
正则表达式与有限自动机等价
定理：对任一确定有限自动机A，存在一正则表达式e,使得L(A)=L(e),反之亦然。
关系图：
正则表达式到NFA的转换规则
首先扩展转换图：
DFA到正则表达式的转换规则
词法分析器的工作过程
词法分析器的设计
人工构造词法分析器过程：
1.确定词法分析器的接口，即确定词法分析器是作为语法分析的一个子程序还是作为独立一遍。
2.确定单词分类和Token结构。
3.根据2步，构造每一类单词的描述。
正则表达式→NFA→DFA
4.根据3步设计算法实现DFA。
利用工具自动生成：ScanGen Lex
单元总结
两个工具： 有限自动机、正则表达式
三个算法： 正则表达式到FA的转换
NFA到DFA的转换
DFA的化简
一个实现： DFA的实现
