词法分析

词法分析

• 词法分析器:字符流->记号流
• 词法分析器的手工构造
  • 比较符号的转移图
    转移图.png
  • 标识符的转移图
    • 转移图
      标识符转移图.png
    • 关键字表(哈希表的构造)
• 正则表达式(ε空集,c为所有ε的子集)
  • 选择 M|N
  • 连接 MN
  • (kleene)闭包 M^*
• 正则表达式语法糖
• 有限状态自动机
  • FA
    有限状态自动机.png

  • 确定的有限状态自动机详细图 DFA

有限状态自动机图2.png

- 当输入无法到达接受状态时,则称为无法被自动机接受
+ 非确定的有限状态自动机 NFA
-

非确定的有限状态自动机.png

转换

• RE转换成NFA:(thompson算法)

thompson算法图.jpeg

• 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;
             }
         }
     }
    

  • 实例

NFA.png
- 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;
             }
             ...
         }