[编译原理]构造LR分析器和SLR移进归约分析表

目录

目标

1、基础知识引入

1.1 文法

1.2 拓广文法

1.3 全部的项目集

2. 计算文法的LR(0)项目集的、识别活前缀的DFA

 2.1 分析得到各个项目集

2.2 构建SLR分析表中的移进部分

2.3 构建SLR分析表中的归约部分

3. LR分析构建分析器

3.1 过程分析

3.2 JavaScript代码实现

3.3 java代码实现(强哥翻译)


 

 

写在前面:本篇文章以编程实现的角度进行分析,分析的过程中难免会有错误,请多多指教。不过最终以实现目标为主。

目标

        通过文法构造SLR分析表,然后构造SLR(1)分析器。然后通过编码将其实现本篇主题)。

1、基础知识引入

可以参考本篇文章梳理基础知识,建议先阅读本篇文章。

编译原理-LR(0)文法算法实现https://www.jianshu.com/p/7e4b4f47de7b

1.1 文法

  • (1)E - > E - T
  • (2)E - > T
  • (3)T - > T * F
  • (4)T - > F
  • (5)F - > - F
  • (6)F - > id

1.2 拓广文法

        在文法的基础上增加一个产生式 E ' - >  E

  • (0)E' - > E
  • (1)E - > E - T
  • (2)E - > T
  • (3)T - > T * F
  • (4)T - > F
  • (5)F - > - F
  • (6)F - > id

1.3 全部的项目集

  • (0)E' - > .E          E' - > E.
  • (1)E - > .E - T     E - > E. - T     E - > E - .T     E - > E - T.
  • (2)E - > .T          E - > T.       
  • (3)T - > .T * F     T - > T. * F    T - > T *. F      T - > T * F.
  • (4)T - > .F          T - > F.
  • (5)F - > .- F        F - > -. F        F - > - F.
  • (6)F - > .id          F - > id.

2. 计算文法的LR(0)项目集的、识别活前缀的DFA

        简而言之,就是各种状态转移形成的项目闭包。

 2.1 分析得到各个项目集

[编译原理]构造LR分析器和SLR移进归约分析表_第1张图片

个人理解分析过程:

首先将所有的项目标记一个状态,假设 0 表示这个项目没有用过, 1 表示 这个项目使用过。

然后从初态集(I0)开始分析,初态集里出现的项目全部置为 1 ,代表已经使用了。

第一次,判断项目集(I0)所有经过 E 到达的下一状态是否为 0 ,若为 0 则创建项目集(I1),并将该项目状态置为1,将符合条件的转移项目都加进去。

        加入之后判断 A - > α . β , . 后面的 β 是否为初态集中项目的左部,如果是,则将初态集中以 β 为左部的项目加入到新建的项目集(I1)中,然后再次进行A - > α . β 的判断,直到新项目集中没有项目加入为止。

第二次,判断项目集(I0)所有经过 T 到达的下一状态是否为 0 ,若为 0 则创建项目集(I2),并将该项目状态置为1,将符合条件的转移项目都加进去。

        加入之后判断 A - > α . β , . 后面的 β 是否为初态集中项目的左部,如果是,则将初态集中以 β 为左部的项目加入到新建的项目集(I2)中,然后再次进行A - > α . β 的判断,直到新项目集中没有项目加入为止。

...........

第五次,判断项目集(I0)所有经过 -  到达的下一状态是否为 0 ,若为 0 则创建项目集(I5),并将该项目状态置为1,将符合条件的转移项目都加进去。

        加入之后判断 A - > α . β , . 后面的 β 是否为初态集中项目的左部,如果是,则将初态集中以 β 为左部的项目加入到新建的项目集(I5)中,然后再次进行A - > α . β 的判断,直到新项目集中没有项目加入为止。

        即:F -> .-F 经过 - 到达的下一项目为 F - > - . F , 此项目状态为 0 ,因此创建新的项目集I5 , 将 F - > - . F 加入到新建项目集I5中,状态置为1。加入后判断 . 后的F是否为初态集I0项目中的左部,发现符合,则将F - > .-F 和 F - > .id 加入到项目集I5中,之后在判断 . 后的 - 和 id,发现都不是初态项目集中的左部,所以没有新的项目加入,结束循环判断。

第六次:判断项目集(I1)所有经过 -  到达的下一状态是否为 0 ,若为 0 则创建项目集(I6),将符合条件的转移项目都加进去。

        即:由于E' - > E. 已经是句柄了,. 后面为空,所以不做讨论。

        E - > E . -T  的下一项目 E - > E - . T的状态为0,所以创建新的项目集 I6,并将E - > E - . T加入到新项目集I6中,状态置为1。加入后,继续判断E - > E - . T ,. 后的T是否为初态集中项目的左部,发现是,所以将T - > .T * F 和 T - > .F 都加入到I6中,有新加入继续判断,T - > .T * F 中 . 后的 T 已经加入过了,所以不再加入。接着判断 T - > .F ,.  后 为 F ,在初态集中项目左部包含F,并且 I6中未加入过 F 的项目,所以将F - > .-F 和 F - > .id 加入到项目集I6中,之后在判断 . 后的 - 和 id,发现都不是初态项目集中的左部,所以没有新的项目加入,结束循环判断。

.........

第九次,判断项目集(I6)所有经过 T  到达的下一状态是否为 0 ,若为 0 则创建项目集(I9),将符合条件的转移项目都加进去。

        E - > E  - .T  的下一项目 E - > E - T .的状态为0,所以创建新的项目集 I9,并将E - > E -  T . 加入到新项目集I9中,状态置为1。(注意这里 I6 所经过 T 到达的 项目有两个 E->E- T. 和T-> T.*F ,第一个状态为 0 所以创建了新的项目集I9,虽然第二个 状态为1 ,但是也是I6通过T到达的,所以也需要加入到I9里面。)然后就是循环判断,下一字符是否在初态集左部出现,出现则加入,往复循环,直至没有为止。

.........

2.2 构建SLR分析表中的移进部分

[编译原理]构造LR分析器和SLR移进归约分析表_第2张图片

  id - * # E T F
0 s4 s5     1 2 3
1   s6   acc      
2     s7        
3              
4              
5 s4 s5         8
6 s4 s5       9 3
7 s4 s5         10
8              
9     s7        
10              

 通过 2.1分析可以得到所有的项目集,接下分析转移部分。

1. 首先遍历 I0 - I10项目集(遍历符号记为 i),然后遍历每个项目集中的项目,获取项目中 . 的位置,然后判断 . 后的字符X,如果不为空(句柄)并且不和上次查找  . 后的字符相同,则在所有项目集中查找该项目首次出现的位置(顺序查找I0-I10),若找到该项目所在的项目集I(j),如果该字符X是非终结符,则直接将table[i][X] = j ;如果X是终结符,则将table[i][X] = Sj;

2.举例:

第一次遍历 I0,然后遍历I0中的项目,E' - > . E  通过 E 到达E' -> E.,在所有项目集中查找该项目,发现 I1中包含E' -> E.,又因为E是非终结符,所以 table[0][E] = 1;

继续遍历 I0 中的项目,此时为 E - > .E - T , . 后的下一字符为 E,前一次已经转移过了,所以跳过。

继续遍历 I0 中的项目,此时为 E - > .T , . 后的下一字符为 T,和前一次转移字符不同,通过 T 到达E -> T. ,在所有项目集中查找该项目,发现 I2中包含E -> T.,又因为T是非终结符,所以 table[0][T] = 2;

.......

继续遍历 I0 中的项目,此时为 F - > .id , . 后的下一字符为 id,和前一次转移字符不同,通过 id 到达F - > id . ,在所有项目集中查找该项目,发现 I4中包含F - > id . ,又因为id 是终结符,所以 table[0][id] = S4;


第二次遍历 I1,然后遍历I1中的项目,因为 E -> E. 的下一个字符为空(句柄),所以跳过。

继续遍历I1中的项目,此时E - > E .- T 的下一个字符为 - ,在所有项目集中查找E - > E - . T ,

发现I6中包含E - > E - . T ,又因为 - 为终结符,所以table[1][-]=S6;

以此类推.......

2.3 构建SLR分析表中的归约部分

  id - * # E T F
0 s4 s5     1 2 3
1   s6   acc      
2   r2 s7 r2      
3   r4 r4 r4      
4   r6 r6 r6      
5 s4 s5         8
6 s4 s5       9 3
7 s4 s5         10
8   r5 r5 r5      
9   r1 s7 r1      
10   r3 r3 r3      

 

1.SLR(1)规约需要用到follow集合,根据文法:

[编译原理]构造LR分析器和SLR移进归约分析表_第3张图片

 可求得:

follow(E)= {#,-}

follow(T)={*} U follow(E) = {#,-,*}

follow(F)= follow(T)= {#,-,*}(不算id)

把每个文法看做成一个句柄:

  • (1)E - > E - T .
  • (2)E - > T .
  • (3)T - > T * F .
  • (4)T - > F .
  • (5)F - > - F .
  • (6)F - > id .

依次遍历上述句柄,在所有的项目集中匹配, 匹配到 Ii 后,获取 . 前面的一个字符X,以此确定follow(X),接着用变量 j 遍历follow(X),在表中输入 table [i][j]  = r +这是第几个产生式句柄。

例如: 第一个产生式句柄(1)E - > E - T . 在 I9中匹配到了 ,

[编译原理]构造LR分析器和SLR移进归约分析表_第4张图片

接着获取 . 前面的字符T,由此得知通过什么转移过来的,对应follow(T),接着遍历follow(T)中的元素  ,所以table[9][#] = r1 ,table[9][-] = r1,table[9][*] = r1。

其他以此类推.......

至此,SLR(1)分析表已经构建完成。

3. LR分析构建分析器

[编译原理]构造LR分析器和SLR移进归约分析表_第5张图片

 

3.1 过程分析

1. 首先初始化栈内容 stack = { # ,0}

为了方便这里将stack栈拆分成两个栈,状态栈 prestate = {0},符号栈 prefix = { # }。

2. 对当前输入进行判断,以上表为例,第一次当前输入取 id 和 状态状态栈顶 0 进行查表分析,table[0][id] = S4,因此进行移进S4操作,S用当前输入id替换后,将id和4分别加入到栈中,

目前栈为prestate = {0,4},prefix = { # ,id}, 当前输入指向下一个字符,为--id*id#。

第二次,当前输入 - ,栈顶状态 4 ,查表table[4][-] = r6,执行归约操作,r6对应产生式F - > id,此时将prestate栈pop栈顶状态4,,prefix栈pop栈顶符号id并加入符号F,接着再次获取当前栈顶状态 0,查表table[0][F] = 3,最后将 3 加入到状态栈中即可。

3.以此类推,直至达到出错格局或接受格局为止!

注意: 每次格局发生变化,都需进行查表操作,并且一个字符对应一个状态。

 

3.2 JavaScript代码实现





    
    
    
    LR分析器测试版
    





    


3.3 java代码实现(强哥翻译)

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

public class Demo3 {
    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 String w;
    public static String[][] action_goto=new String[11][7];
    public static Map ininGrammer=new HashMap<>();
    public static List initItems=new ArrayList<>();
    public static Map> result=new HashMap<>();
    public static List Iis=new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        w=sc.nextLine();
        if (w.charAt(w.length()-1)!='#'){
            w+="#";
        }
        w=w.replaceAll("id","i");
        for (int i = 0; i <11 ; i++) {
            for (int j = 0; j <7 ; j++) {
                action_goto[i][j]="0";
            }
        }
        action_goto[1][3]="acc";
        initMap(ininGrammer);
        initI(initItems);
        for (String key:ininGrammer.keySet()) {
            String[] value_arr = ininGrammer.get(key);
            for (int k = 0; k  Iis=new ArrayList<>();
                    tempChar=ch;
                    for (int k = 0; k 0){
                                            InitItem Ii1 = new InitItem("", "", 1);
                                            tempItem=tempItem.substring(0,index2)+tempItem.substring(index2+1);
                                            tempItem=tempItem.substring(0,index2+1)+"."+tempItem.substring(index2+1);
                                            Ii1.key=result.get(n).get(p).key;
                                            Ii1.item=tempItem;
                                            Ii1.status=1;
                                            Iis.add(Ii1);
                                        }
                                    }catch (Exception e){
                                    }
                                }
                                try {
                                    if (!String.valueOf(initItems.get(k).item.charAt(index+2)).equals("")){
                                        for (int p = 0; p > tempResult=new HashMap<>();
        int tempKey=0;
        for (int key:result.keySet()) {
            if (result.get(key).size()!=0){
                tempResult.put(tempKey++,result.get(key));
            }
        }
        result=tempResult;
//        System.out.println(result);
        for (int i = 0; i > follow=new HashMap<>();
        List tempKeys=new ArrayList<>();
        tempKeys.add("E");
        tempKeys.add("T");
        tempKeys.add("F");
        for (String key:tempKeys) {
            List follow_arr=new ArrayList<>();
            if (key.equals("E")){
                follow_arr.add('#');
            }
            for (String key2:ininGrammer.keySet()) {
                for (int i = 0; i  prefix=new Stack<>();
        prefix.push('#');
        Stack preState=new Stack<>();
        preState.push(0);
        n=0;
        while (true){
            char ch = w.charAt(0);
            Integer num1 = preState.get(preState.size() - 1);
            String refer = getQuery(num1, ch);
            n++;
            res1.add(n);
            String s1 = w.replaceAll("i", "id");
            res3.add(s1);
            String resStr="";
            int x=0,y=0;
            while (true){
                resStr=x=prefix.size()&&y>preState.size()){
                    break;
                }
            }
            String s = resStr.replaceAll("i", "id");
            res2.add(s);

            if (refer.charAt(0)=='0'){
                res4.add("出错处理");
                break;
            }else if (refer.charAt(0)=='s'){
                prefix.push(ch);
                preState.push(refer.charAt(1)-'0');
                res4.add("移进"+refer);
                w=w.substring(1);
            }else if (refer.charAt(0)=='r'){
                char temp = refer.charAt(1);
                String[] str = grammer(temp).split("=");
                for (int i = 0; i "+str[1]+")");
            }else if (refer.equals("acc")){
                res4.add("接收:accept");
                break;
            }
        }
        for (int i = 0; i  concat(List a,List b){
        List c=new LinkedList<>();
        c.addAll(a);
        c.addAll(b);
        return DisRepet(c);
    }
    public static List DisRepet(List arr){
        List arrayList=new ArrayList();
        for (int i = 0; i  map){
        String[] a={"E-T","T"};
        map.put("E",a);
        String[] b={"T*F","F"};
        map.put("T",b);
        String[] c={"i","-F"};
        map.put("F",c);
    }
    public static void initI(List initItems){
        initItems.add(new InitItem("e",".E",0));
        initItems.add(new InitItem("e","E.",0));
    }
}
class InitItem{
    public String key;
    public String item;
    public int status;

    public InitItem() {
    }

    public InitItem(String key, String item, int status) {
        this.key = key;
        this.item = item;
        this.status = status;
    }

    @Override
    public String toString() {
        return "InitItem{" +
                "key='" + key + '\'' +
                ", item='" + item + '\'' +
                ", status=" + status +
                '}';
    }
}

总结:以编程实现为主,个人分析难免有误,请多多指教!

 

你可能感兴趣的