郑州大学编译原理实验四LR(0)分析算法JAVA

实验四 LR分析方法的设计与实现（选做）

一、实验目的

通过LR分析方法的实现，加深对自下而上语法分析方法及语法分析程序自动生成过程的理解。

二、实验要求

输入上下文无关文法，对给定的输入串，给出其LR分析过程及正确与否的判断。
1．参考数据结构
typedef struct{/文法/
char head;//产生式左部符号
char b[20];//用于存放产生式
int point;
int lg;//产生式的长度
}regular;
typedef struct{
int l; //文法数量
int m; //vn 数量
int n; //vt 数量
regular re[20];
nfinal vn[20];//非终结符
final vt[20];//终结符
}condition;
condition cd[20];//项目
regular first[20];//产生式
2. 使用闭包函数（CLOSURE）和转换函数(GO(I,X))构造文法G’的LR(0)的项目集规范族。

3. 构造LR（0）分析表

4. LR分析算法描述

5、对给定输入串输出其准确与否的分析过程。

package StringToJAVA;

import javafx.util.Pair;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.*;

/**
 * @author [25'h]
 * @datetime 2022.11.03
 */
public class LastReducing {
    public static List<Node> allNode = new ArrayList<>();
    public static String startLabel;//开始符
    public static ArrayList<String> terSymbol = new ArrayList<>();// 终结符
    public static ArrayList<String> non_ter = new ArrayList<>();// 非终结符
    public static HashMap<String, List<String>> formula = new HashMap<>();//产生式
    public static List<Pair<String, String>> formulaList = new ArrayList<>();// 所有的推导式子，使用Pair对象存储
    public static Integer[][] ACTION;// ACTION表格
    public static Boolean[][] SorRActionTable;// 判断ACTION表是状态还是文法式子序号
    public static Integer[][] GOTO;// GOTO表格
    public static String objString;// 目标串
    public static Node startNode;// LR分析表起始
    public static Stack<Integer> conStack = new Stack<>();// 状态栈
    public static Stack<String> subStack = new Stack<>();// 字符栈

    public static void main(String[] args) {
        File file = new File("src/StringToJAVA/test4.txt");
        BufferedReader bufferedReader;
        try {
            // 读取文法和目标式子
            bufferedReader = new BufferedReader(new FileReader(file));
            startLabel = bufferedReader.readLine();
            // 读取非终结符
            non_ter.addAll(Arrays.asList(bufferedReader.readLine().split(" ")));

            // 读取终结符
            terSymbol.addAll(Arrays.asList(bufferedReader.readLine().split(" ")));
            //将产生式右部或表达式分离
            String s;
            while ((s = bufferedReader.readLine()).contains("->")) {
                String[] split = s.split("->");
                String[] split1 = split[1].split("\\|");
                formula.put(split[0], Arrays.asList(split1));// 存入formula中
                // 再以Pair格式存储
                for (String s1 : split1) {
                    formulaList.add(new Pair<>(split[0], s1));
                }
            }
            objString = s;
        } catch (Exception e) {
            e.printStackTrace();
        }

        List<EachFormal> firstEachFormal = Collections.singletonList(new EachFormal(null, startLabel, -1));// 创建第一个分析表的头
        startNode = generateNode(firstEachFormal);//生成分析表，返回开始表表格
        // 根据状态初始化辅助表大小
        ACTION = new Integer[allNode.size()][terSymbol.size() + 1];
        SorRActionTable = new Boolean[allNode.size() + 1][terSymbol.size() + 1];
        GOTO = new Integer[allNode.size() + 1][non_ter.size()];

        generateActionGotoTable();// 生成分析表
        show();// 显示分析表和文法
        reducing();// 归约
    }

    private static void reducing() {
        terSymbol.add("#");// ACTION中列有#
        //stack初始值
        conStack.push(allNode.indexOf(startNode));
        subStack.push("#");
        int index = 0;
        String sub;
        // 若不为-1表示没结束
        while (ACTION[conStack.peek()][terSymbol.indexOf((sub = objString.substring(index, index + 1)))] != -1) {
            showTwoStack();// 显示
            // 状态变化
            if (SorRActionTable[conStack.peek()][terSymbol.indexOf(sub)]) {
                conStack.push(ACTION[conStack.peek()][terSymbol.indexOf(sub)]);
                subStack.push(sub);
                index++;
                //使用归约
            } else if (!SorRActionTable[conStack.peek()][terSymbol.indexOf(sub)]) {
                Pair<String, String> pair = formulaList.get(ACTION[conStack.peek()][terSymbol.indexOf(sub)]);
                String value = pair.getValue();
                StringBuffer buffer = new StringBuffer();
                // 将栈中作为右部，使用左部代替
                for (int i = 0; i < value.length(); i++) {
                    buffer.insert(0, subStack.pop());
                    conStack.pop();
                }
                if (!value.equals(buffer.toString())) {
                    throw new RuntimeException("错误");
                }
                // 使用左部代替
                subStack.push(pair.getKey());
                conStack.push(GOTO[conStack.peek()][non_ter.indexOf(pair.getKey())]);

            }
        }
        showTwoStack();
    }

    private static void showTwoStack() {
        conStack.forEach(System.out::print);
        System.out.printf("%-20s", "");
        subStack.forEach(System.out::print);
        System.out.println();
    }

    // 生产分析表
    private static void generateActionGotoTable() {
        for (int i = 0; i < allNode.size(); i++) {
            HashMap<String, Node> nodeToNode = allNode.get(i).nodeToNode;
            // 若是没有后续节点，就属于该使用推导式进行归约了
            if (nodeToNode.size() == 0) {
                // 取出该节点的推导式
                EachFormal eachFormal = allNode.get(i).nodeList.get(0);
                // 判断这个推导式在formulaList的索引k
                int k;
                for (k = 0; k < formulaList.size(); k++) {
                    Pair<String, String> pair = formulaList.get(k);
                    if (pair.getKey().equals(eachFormal.left) && pair.getValue().equals(eachFormal.right)) {
                        break;
                    }
                }
                // 讲第k行写上用eachFormal进行归约，使用索引k代替
                for (int m = 0; m < terSymbol.size() + 1; m++) {
                    ACTION[i][m] = k;
                    SorRActionTable[i][m] = false;
                }
                continue;
            }
            // 有后续节点
            for (String s : nodeToNode.keySet()) {
                // 若终结符，使用ACTION
                if (terSymbol.contains(s)) {
                    int k = terSymbol.indexOf(s);
                    ACTION[i][k] = allNode.indexOf(nodeToNode.get(s));
                    SorRActionTable[i][k] = true;
                } else {// 若非终结符，使用GOTO
                    int k = non_ter.indexOf(s);
                    GOTO[i][k] = allNode.indexOf(nodeToNode.get(s));
                }
            }
        }
        //找一下出口，出口中的推导式第左边是null，因为一开始我定义的分析表的头左就是null，并且index需要是最后的
        for (int i = 0; i < allNode.size(); i++) {
            for (EachFormal eachFormal : allNode.get(i).nodeList) {
                if (eachFormal.left == null && eachFormal.right.length() == eachFormal.index) {
                    ACTION[i][terSymbol.size()] = -1;
                    break;
                }
            }
        }
    }


    private static List<EachFormal> trickBack(String curS) {
        ArrayList<EachFormal> resList = new ArrayList<>();
        List<String> list = formula.get(curS);// 获取推导式左为curS的式子
        for (String s : list) {
            String sub = s.substring(0, 1);
            resList.add(new EachFormal(curS, s, 0));
            // 首字母为非终结符继续扩展，不能是本身，否则会栈溢出
            if ((non_ter.contains(sub) && !sub.equals(curS))) {
                resList.addAll(trickBack(sub));
            }
        }
        return resList;
    }

    private static Node generateNode(List<EachFormal> startFormal) {
        ArrayList<EachFormal> temp = new ArrayList<>();
        // 点向前移动一个符号，下一个符号必为startFormal，因为调用前会判断
        for (EachFormal eachFormal : startFormal) {
            temp.add(new EachFormal(eachFormal).addIndex());// 不能直接修改，应该用克隆对象
        }
        Node resNode = new Node();
        List<EachFormal> nodeList = resNode.nodeList;
        // 对于每个传入的推到式，进行扩展，只有下一个为非终结符时才会扩展
        for (EachFormal eachFormal : temp) {
            String right = eachFormal.right;
            nodeList.add(new EachFormal(eachFormal));
            if (eachFormal.index >= right.length()) {// 若已经是推导式结尾，跳过
                continue;
            }
            String sub = right.substring(eachFormal.index, eachFormal.index + 1);
            // 若是终结符，或者和当前推导式左相同，那么跳过
            if (terSymbol.contains(sub) || sub.equals(eachFormal.left)) {
                continue;
            }
            //是非终结符进行扩展
            List<EachFormal> list = trickBack(sub);
            nodeList.addAll(list);
        }
        // 若生成的Node已经存在，那么不需要创建这个新的Node节点了
        Node node1 = hasExitedNode(resNode);
        if (node1 != resNode) {
            // 已经存在，没必要进行后续链接
            return hasExitedNode(node1);
        }
        // 进行Node节点之间的后续生产和节点链接
        HashMap<String, List<EachFormal>> tempHashMap = new HashMap<>();
        // 判断点后的符号有几种，进而确定该节点有几条分支
        for (EachFormal eachFormal : nodeList) {
            String right = eachFormal.right;
            if (eachFormal.index >= right.length()) continue;
            // 取出紧接符号
            String sub = right.substring(eachFormal.index, eachFormal.index + 1);
            // 将紧接符号相同推导式的进入一组
            if (tempHashMap.containsKey(sub)) {
                List<EachFormal> eachFormals = tempHashMap.get(sub);
                eachFormals.add(eachFormal);
            } else {
                List<EachFormal> objects = new ArrayList<>();
                objects.add(eachFormal);
                tempHashMap.put(sub, objects);
            }
        }
        //对于每一个分支进行新Node节点的生产
        for (String s : tempHashMap.keySet()) {
            Node node = generateNode(tempHashMap.get(s));
            resNode.nodeToNode.put(s, node);
        }
        // 返回生产节点，用于节点之间的链接
        return resNode;
    }

    // 若allNode中已经存在同形式cur，就合并成一个
    public static Node hasExitedNode(Node cur) {
        for (Node node : allNode) {
            if (node.equals(cur)) return node;
        }
        allNode.add(cur);// 不存在，就记录下来
        return cur;
    }

    public static void show() {
        System.out.println("文法:");
        System.out.println(Arrays.toString(non_ter.toArray()));
        System.out.println(Arrays.toString(terSymbol.toArray()));
        for (String ss : formula.keySet()) {
            System.out.println(ss + "\t" + Arrays.toString(formula.get(ss).toArray()));
        }
        System.out.println("\nACTION GOTO:");
        System.out.printf("%-4s%-30s%s\n", "", Arrays.toString(terSymbol.toArray()), Arrays.toString(non_ter.toArray()));
        for (int i = 0; i < allNode.size(); i++) {
            System.out.printf("%-4s%-30s %s\n", i, Arrays.toString(ACTION[i]), Arrays.toString(GOTO[i]));
        }
        System.out.println();

    }
}

/**
 * 节点类
 */
class Node {
    List<EachFormal> nodeList = new ArrayList<>();// 推导式的集合，每个推导式中存在点的位置
    HashMap<String, Node> nodeToNode = new HashMap<>();//节点之间的连接

    // 用于节点之间相同的判断
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        if (nodeList.size() != node.nodeList.size()) {
            return false;
        }
        for (EachFormal formal : nodeList) {
            if (!node.nodeList.contains(formal)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public int hashCode() {
        return Objects.hash(nodeList, nodeToNode);
    }

    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer();
        for (EachFormal eachFormal : nodeList) {
            buffer.append(eachFormal.toString()).append("\n");
        }
        return buffer.toString();
    }
}

/**
 * 推导式及点的位置
 */
class EachFormal {
    String left;//推导式左
    String right;// 推导式右
    int index;// 点位置，一开始是0

    public EachFormal(String _l, String _r, int _i) {
        left = _l;
        right = _r;
        index = _i;
    }

    /**
     * 克隆对象，懒得实现克隆类了
     */
    public EachFormal(EachFormal eachFormal) {
        left = eachFormal.left;
        right = eachFormal.right;
        index = eachFormal.index;
    }

    public EachFormal addIndex() {
        index++;
        return this;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        EachFormal that = (EachFormal) o;
        return index == that.index &&
                Objects.equals(left, that.left) &&
                Objects.equals(right, that.right);
    }

    @Override
    public int hashCode() {
        return Objects.hash(left, right, index);
    }

    @Override
    public String toString() {
        return "EachFormal{" +
                "left='" + left + '\'' +
                ", right='" + right + '\'' +
                ", index=" + index +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348

text4.txt

E
E T
+ ( ) a
E->E+T|T
T->(E)|a
(a)+a#
1
2
3
4
5
6

输出结果：

"D:\Program Files\Java\jdk1.8.0_291\bin\java.exe" "-javaagent:D:\IntelliJ IDEA 2020.1\lib\idea_rt.jar=59011:D:\IntelliJ IDEA 2020.1\bin" -Dfile.encoding=UTF-8 -classpath "D:\Program Files\Java\jdk1.8.0_291\jre\lib\charsets.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\deploy.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\access-bridge-64.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\cldrdata.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\dnsns.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\jaccess.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\jfxrt.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\localedata.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\nashorn.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\sunec.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\sunjce_provider.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\sunmscapi.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\sunpkcs11.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\zipfs.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\javaws.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\jce.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\jfr.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\jfxswt.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\jsse.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\management-agent.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\plugin.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\resources.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\rt.jar;D:\code_management\algorithm\out\production\algorithm" StringToJAVA.LastReducing
文法:
[E, T]
[+, (, ), a]
T	[(E), a]
E	[E+T, T]

ACTION GOTO:
    [+, (, ), a]                  [E, T]
0   [null, 6, null, 1, null]       [3, 2]
1   [3, 3, 3, 3, 3]                [null, null]
2   [1, 1, 1, 1, 1]                [null, null]
3   [4, null, null, null, -1]      [null, null]
4   [null, 6, null, 1, null]       [null, 5]
5   [0, 0, 0, 0, 0]                [null, null]
6   [null, 6, null, 1, null]       [7, 2]
7   [4, null, 8, null, null]       [null, null]
8   [2, 2, 2, 2, 2]                [null, null]

0                    #
06                    #(
061                    #(a
062                    #(T
067                    #(E
0678                    #(E)
02                    #T
03                    #E
034                    #E+
0341                    #E+a
0345                    #E+T
03                    #E

Process finished with exit code 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33