[编译原理] 构造预测分析表预测分析器的编码实现

目录

前言

1、 通过文法构造first集合和follow集合

1.1 文法

1.2 构建 First集

 1.3 构建follow集合

2.、通过文法构建预测分析表

2.1 预测分析表

2.2 构造过程

3. 通过预测分析器分析序列

3.1 分析输入序列id + id  * id;的过程

 3.2 过程分析

4. 编码实现

4.1 对数据约定

4.2 编码效果展示

4.3 编写代码JavaScript实现

4.4 编写代码java实现

---

前言

        本博客主要记录 给定文法 通过算法得到预测分析表，然后通过预测分析表 分析输入序列的过程。

1、 通过文法构造first集合和follow集合 1.1 文法

（1）L -> E ; L | @（2）E -> TE' （3）E' -> + T E' | - T E' | @ （4）T -> F T'（5）T' -> * F T' | / F T' | mod F T' | @（6）F -> (E) | id | num

        所使用的文法必须为消除左递归后的最左子式，上述文法即为消除左递归后的文法。

1.2 构建 First集

        要构建follow集合首先需要得到first集合，下面分析first集合的官方解释和步骤。

（约定 @ 代替 ε，因为编码实现敲不出来 ε ）

1. 定义：

          对于任意文法符号串α ，FIRST(α)是可从α推导得到的串的首符号的集合

          如果α-->@，则@也在FIRST(α)中（ 即α可空）；

          FIRST(α)={t|α-->tβ, t∈T}U{@|α-->@}；

2. 做法：

首先明确FIRST集合是对推导符号后面的首符号（仅仅只是一个符号）进行判断的。

3. 步骤：

        假设 α-->tβ，求FIRST(α)

        ① 如果首符号t是终结符则直接放入first集合中。

        ②如果t不是非终结符：

           i．如果t—>@，则将@加入FIRST(α)，并且将β进行①② *** 作判断。

           ii．如果t不是@，那么求first（t），并将first（t）的结果放入FIRST(@)中。
 

        简而言之，用个人的理解来说：

（1）first集合是从文法中得到的，分析文法时是自下而上分析，如下 应该从F开始分析，最后分析L。

 （2）分析某个产生式的first(A)集合时，看其右部，每次取其第一个字符，如果是终结符则加入到该first(A)集合中，如果为非终结符B，则 first(A) = fitst(B) U {A对应的右部其他终结符};

 （3）该文法的所有first 集合为：

first(F) = { ( , id , num }

first(T') = { * , / , mod, @}

first(T) = first(F) = { ( , id , num }

first(E') = { + , - , @ };

first(E) = first(T) = first(F) =  { ( , id , num }

first(L) = first(E) U { @ } = { ( , id , num , @ }

 1.3 构建follow集合

        Follow集是从上至下分析文法得到的，下面是分析过程：

（约定 @ 代替 ε，因为编码实现敲不出来 ε ）

假设：

        A -->αBβ，A -->αB，求follow（B）

做法：

        寻找B在à右边出现的规则式，然后按照以下步骤进行 *** 作

步骤：

         ①如果A是开始符, 将$加入FOLLOW(A), 这里 # 是输入结束标记.

         ②对于A -->αBβ，首先判断β是不是可以推出@ （α可能为空）

                     i．如果不能推出@，那么将first（β）加入follow（B）

                     ii．如果推出@，那么将{first（β）- @} U follow(A)

                     iii . 如果 β 为 终结符，直接将 β 加入到 follow（B）中

                (ps:为了便于理解，iii 为个人理解!)

         ③对于A -->αB，将follow(A)结果加入follow（B）。

注意：

        Follow一般从上往下找，而且第一轮的时候有时候不能够将所有的follow都填满，所以要采用迭代的方式不断循环。有时候遇到闭环的时候，先假设按照第一遍 把所有的都算出来后，第二轮的时候将所有集合制空，如果有变化，则在进行一轮，直到没有变化为止。

分析过程：

第一次分析：follow(L) = {#}

        （1）根据规则1 ：L为开始符，将 # 加入其中；

第二次分析：follow（E）= { ; ,  ) }

        （1）根据规则2.iii  和 产生式（1），将终结符 ； 加入到follow(E)

        （2）根据规则2.iii 和 产生式 （6），将终结符 ) 加入到follow（E）

第三次分析：follow（E'）= { ; ,  ) }

        （1）根据规则3  和 产生式（2），将终结符 follow（E） 加入到follow(E')

第四次分析：follow（T）= { + ， - ,  ; , ) }

        （1）根据规则2.ii  和 产生式（2），first(E') 包含 @ ，所以将first(E') - {@} U follow(E)加入到follow（T）中，即 { + ， - ,  ; , ) }。

        （2）根据规则2.ii 和 产生式 （3），first(E') 包含 @ ，所以将first(E') - {@} U follow(E')加入到follow（T）中，即 { + ， - ,  ; , ) }。

ps:此时发现会有重复的存在，编译程序时可以执行去重 *** 作，也可以在此判断之前是否加入过了。

第五次分析：follow（T '）= { + ， - ,  ; , ) }

        （1）根据规则3 和 产生式（4），将 follow（T） 加入到follow（T '）中

第六次分析：follow（ F ）= { * ，/ , mod , + , - , ; , ) }

        （1）根据规则2.ii  和 产生式（4），first(T') 包含 @ ，所以将first(T') - {@} U follow(T)加入到follow（F）中，即 { * ，/ , mod , + , - , ; ,) }。

        （2）根据规则2.ii  和 产生式（5），first(T') 包含 @ ，所以将first(T') - {@} U follow(T ')加入到follow（F）中，即 { * ，/ , mod , + , - , ; , ) }。

ps:此时发现会有重复的存在，编译程序时可以执行去重 *** 作，也可以在此判断之前是否加入过了。

整理得：

follow(L) = {#}follow（E）=  follow（E'）= { ; ,  ) }follow（T）= follow（T '）= { + ， - ,  ; , ) }follow（ F ）= { * ，/ , mod , + , - , ; , ) }

2.、通过文法构建预测分析表 2.1 预测分析表

	id	num	+	-	*	/	mod	(	)	;	#
L	E;L	E;L						E;L			@
E	TE'	TE'						TE'
E‘			+TE'	-TE'					@	@
T	FT'	FT'						FT'
T’			@	@	*FT'	/FT'	modFT'		@	@
F	id	num						(E)

2.2 构造过程

1. 将文法中的产生式右部填写在表中，首先需要确定填写的位置。

        （1）如果该产生式右部不为 @

                i ：获取该产生式左部A对应的first(A) - { @ }集合。

                ii : 遍历 first(A) -{@} 集合,与该产生式 左部A ，在表中确认位置。

        （2）如果该产生式右部为 @

                i ：获取该产生式左部A对应的 follow（A）集合。

                ii : 遍历 follow(A) 集合,与该产生式 左部A ，在表中确认位置。

2. 举例：

（1）填写 L -> E;L | @;  先填写 L -> E;L ;

        左部 ：L ，右部 ：E;L ，不为 @ ，所以遍历first（L）- { @ } 集合。

        first(L) - {@} = { ( , id ,num }

        所以将表中：table[L][(]=E;L  table[L][id]=E;L  table[L][num]=E;L

        接着填写 L-> @

        左部 ：L ，右部 ：@ ，为 @ ，所以遍历 follow（L） 集合。

        follow（L） = { # }

        所以将表中：table[L][#]=@ 

（2）填写 E -> TE' ;

        左部 ：E ，右部 TE' ，不为 @ ，所以遍历 first(L) - {@}集合。

        first(E) - {@} = { ( , id ,num }

        所以将表中：table[E][(]=TE'   table[E][id]=TE'   table[E][num]=TE'

其他产生式以此类推，即可完成预测分析表的构造。

3. 通过预测分析器分析序列 3.1 分析输入序列id + id  * id;的过程

 

 3.2 过程分析

1. 首先初始化栈（栈内容）

        stack =  [ # , L]; （结束标志 # ，开始符号 L ）

        序列后也要加上结束标志 #

2. 四种改变格局的动作（也就是下一步怎么走）：

        （1）匹配终结符

                如果栈顶和当前输入终结符相当且不是结束标志#，则分析器d出栈顶符号（pop），输入指针指向下一个终结符（next（ip））。

        举例：

         此时栈顶d出 终结符id ，输入序列指向下一个字符 + 。

        （2）展开非终结符

                栈顶符号是非终结符X，当前输入是终结符a,驱动器访问预测分析表M[X][a];若M[X][a]是X产生式的某候选项，则用此候选项取代栈顶的X。

        举例：1 到 2的过程

    栈内容 #L ，此时栈顶 L（非终结符）, 当前序列输入 id , 在预测分析表中查 table[L][id]

发现 table[L][id] = E;L，所以 先将栈内容 pop(L) , 再 将 E ; L push进栈 ,注意push的是单个字符，栈是先进后出，所以push完成后，栈中内容为 # L;E。

        注意：如果查表查出来的是 @ ，@ 代表空，所以只d出栈顶字符，不加入。

        （3）报告分析成功

                栈顶和当前输入符号均为#，分析成功并结束。

        （4）报告出错 

                有不在前面几种情况中的事故发生。

4. 编码实现

        为了有更好的视觉呈现效果，采用JavaScript进行编译实现。

4.1 对数据约定

1.字符处理

        id , num ,mod 等 多字符组成的，均采用首字母。如 id 用 i 代替。

2.约定 @ 代替 ε，因为编码实现敲不出来 ε

3. 用数组模拟栈

4.2 编码效果展示

 

错误输入

4.3 编写代码JavaScript实现

4.4 编写代码java实现

package com.wang;
import java.util.*;

public class Demo2 {
    public static List res1= new ArrayList<>();
    public static List res2= new ArrayList<>();
    public static List res3= new ArrayList<>();
    public static List res4= new ArrayList<>();
    public static Stack prefix= new Stack<>();
    public static String w;
    public static String grammer[][]=new String[6][11];
    public static Map init(){
        Map map= new HashMap<>();
        String a[]={"E;L","ε"};
        map.put("L",a);
        String b[]={"Te"};
        map.put("E",b);
        String c[]={"+Te","-Te","ε"};
        map.put("e",c);
        String d[]={"Ft"};
        map.put("T",d);
        String e[]={"*Ft","/Ft","mFt","ε"};
        map.put("t",e);
        String f[]={"(E)","i","n"};
        map.put("F",f);
        return map;
    }

    public static int getPosionX(char x){
        int num=-1;
        switch (x){
            case 'L': num=0;break;
            case 'E': num=1;break;
            case 'e': num=2;break;
            case 'T': num=3;break;
            case 't': num=4;break;
            case 'F': num=5;break;
            default:num=-1;break;
        }
        return num;
    }

    public static int getPosionY(char x){
        int num=-1;
        switch (x){
            case 'i':num=0;break;
            case 'n':num=1;break;
            case '+':num=2;break;
            case '-':num=3;break;
            case '*':num=4;break;
            case '/':num=5;break;
            case 'm':num=6;break;
            case '(':num=7;break;
            case ')':num=8;break;
            case ';':num=9;break;
            case '#':num=10;break;
            default:num=-1;break;
        }
        return num;
    }

    public static List DisRepet(List arr){
        List arrayList=new ArrayList();
        for (int i = 0; i  splice(List list){
        for (int i = 0; i < list.size(); i++) {
            if ('ε'==list.get(i)){
                list.remove(i);
                i--;
            }
        }
        return list;
    }
    public static String[] initTemp(String s[]){
        int index=0;
        s[index++]="L";
        s[index++]="E";
        s[index++]="e";
        s[index++]="T";
        s[index++]="t";
        s[index++]="F";
        return s;
    }
    public static List concat(List a,List b){
        List c=new LinkedList<>();
        c.addAll(a);
        c.addAll(b);
        return DisRepet(c);
    }
    public static String listTransfrom(String str){
        str.replaceAll("i","id").replaceAll("n","num").replaceAll("m","mod");
        return str;
    }

    public static String getQuery(char x,char y){
        int x1 = getPosionX(x);
        int y1 = getPosionY(y);
        if (x1!=-1&&y1!=-1){
            return grammer[x1][y1];
        }else {
            return "-1";
        }
    }

    public static boolean isZJF(){
        Character ch = prefix.get(prefix.size() - 1);
        boolean flag=true;
        if (getPosionY(ch)==-1){
            flag=false;
        }
        return flag;
    }
    public static String queryRefer(char ch){
        String str="";
        switch (ch){
            case 'e':str="E'";break;
            case 't':str="T'";break;
            default:str=ch+"";break;
        }
        return str;
    }
    public static void dealData(int resNum,String refer,String x){
        if (resNum==1){
            String str="";
            for (int i = 0; i "+refer+"展开");
                }else {
                    x=queryRefer(x.toCharArray()[0]);
                    x=listTransfrom(x);
                    res4.add("按"+x+"->"+str+"展开");
                }
            }
        }
    }
    public static void output(int len){
        for (int j = 0; j <25-len ; j++) {
            System.out.print(" ");
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        w=sc.nextLine();

        w = w.replaceAll("id", "i").replaceAll("num", "n").replaceAll("mod", "m");
        w+=";#";
        Map iniGrammer=init();
        Map> first=new HashMap<>();
        String first_temp[]=initTemp(new String[iniGrammer.size()]);
        for (int i = first_temp.length-1; i >=0 ; i--) {
            String[] temp = iniGrammer.get(first_temp[i]);
            List first_map_arr=new ArrayList<>();
            for (int j = 0; j > follow=new HashMap<>();
        for(String key:first_temp){
            String[] temp = iniGrammer.get(key);
            List follow_map_arr=new ArrayList<>();
            if (key.equals("L")){
                follow_map_arr.add('#');
            }
            for(String key2:first_temp){
                if (!key2.equals(key)){
                    String[] brr = iniGrammer.get(key2);
                    for (int k = 0; k  concat = concat(follow.get(key2 + ""), first.get(nextChar + ""));
                                            follow_map_arr=concat(follow_map_arr,concat);
                                            follow_map_arr=DisRepet(follow_map_arr);
                                            follow_map_arr=splice(follow_map_arr);
                                        }else {
                                            //如果不包含 '@' ,则将 first（β）加入follow（B）
                                            follow_map_arr=concat(follow_map_arr,first.get(nextChar+""));
                                            follow_map_arr=DisRepet(follow_map_arr);
                                        }
                                    }catch (Exception e){
                                    }
                                }
                            }else {
                                //4. 如果在末尾则应用规则3
                                follow_map_arr=concat(follow_map_arr,follow.get(key2+""));
                                follow_map_arr=DisRepet(follow_map_arr);
                            }
                        }
                    }
                }
            }
            follow.put(key,follow_map_arr);
        }
//        System.out.println(follow);


        for (int i = 0; i <6 ; i++) {
            for (int j = 0; j <11 ; j++) {
                grammer[i][j]="0";
            }
        }
        for(String key:first_temp){
            String[] iniGrammer_arr = iniGrammer.get(key);
            List first_arr = first.get(key);
            List follow_map_arr = follow.get(key);
            for (int i = 0; i =0 ; i--) {
                    prefix.push(refer.charAt(i));
                }
                dealData(3,refer,x3+"");
                dealData(4,refer,x3+"");
            }else {
                res3.add("出错了");
                res4.add("出错了");
                break;
            }
        }
        for (int i = 0; i 

总结：此方法可能不是最优，如果错误请评论区多多指教。😄

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/web/1321074.html