词法分析
2016-12-28 本文已影响84人
435fa00b72e7
词法分析
- 词法分析器:
字符流->记号流
- 词法分析器的手工构造
- 比较符号的转移图
转移图.png - 标识符的转移图
- 转移图
标识符转移图.png - 关键字表(哈希表的构造)
- 转移图
- 比较符号的转移图
- 正则表达式(ε空集,c为所有ε的子集)
- 选择 M|N
- 连接 MN
- (kleene)闭包 M*
- 正则表达式语法糖
- 有限状态自动机
- FA
有限状态自动机.png -
确定的有限状态自动机详细图 DFA
- FA
- 当输入无法到达接受状态时,则称为无法被自动机接受
+ 非确定的有限状态自动机 NFA
-
非确定的有限状态自动机.png
转换
- RE转换成NFA:(thompson算法)
- NFA转换成DFA:(子集构造算法)
-
delta(q)->ε闭包
-
ε闭包(深度优先算法)
set closure = {}; void eps_closure(x){ closure+= {x}; foreach(y:x--ε--y){ if(!visited(y)){ eps_closure(y); } } }
-
ε闭包(宽度优先算法)
set closure={}; Q=[]; void eps_closure(x){ Q=[x]; while(Q not empty){ q<-deQueue(Q); closure+=q; //下面改成了从q出发的所有节点,所以为宽度优先 foreach(y:q--ε-->y){ if(!visited(y)){ enQueue(Q,y); } } } }
-
子集构造算法:工作表算法
q0 <- eps_closure(n0); Q <- (q0); workList <- q0; while(workList!=[]){ remove q from workList; foreach(character c){ t <- e-closure(delta(q,c)); d[q,c]<-t; if(t is not in Q){ add t to Q and worList; } } }
-
实例
-
-
p0={n0}
-
p1={n1,n2,n3,n4,n6,n9}
(是由p0通过添加a生成的)-
p2={n5,n8,n3,n4,n6,n9}
(是由p1通过添加b生成的)-
p3={n7,n8,n9,n3,n4,n6}
(是由p1通过c生成)- p2通过b还是生成自身,p3通过c还是生成自身
-
习题1.png
因为p1,p2,p3都有n9,所以都是终结
- DFA的最小化(Hopcroft)
- 第一步,分割开可接收的和不可接收的
- 第二步,逐步使用可接收的字符进行分割
- DFA的生成分析算法
-
转移表
nextToken(){ state = 0;//状态值,即p1 stack = [];//栈 while(state!=ERROR){ c = getchar(); if(state is ACCEPT){ clear(stack); } push(state); state = table[state][c]; } while(state is not ACCEPT){ state = pop(); rollback();//回滚到上一个state } }
-
跳转表
nextToken(){ state = 0; stack = []; goto q0; } q0: c=getchar(); if(state is ACCEPT){ clear(stack); } push(state); if(c=='a'){ goto q1; } ... }
-