郑州大学编译原理实验三算符优先分析算法JAVA

一、实验目的

根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。

二、实验内容

1、输入文法。可以是如下算术表达式的文法（你可以根据需要适当改变）：
E→E+T|E-T|T
T→T*F|T/F|F
F→（E）|i

2、对给定表达式进行分析，输出表达式正确与否的判断。
程序输入/输出示例：
输入：1+2;
输出：正确
输入：(1+2)/3+4-(5+6/7);
输出：正确
输入：((1-2)/3+4
输出：错误
输入：1+2-3+(*4/5)
输出：错误

3、参考数据结构
char *VN=0,*VT=0;//非终结符和终结符数组
char firstvt[N][N],lastvt[N][N],table[N][N];
typedef struct //符号对(P,a)
{
char Vn;
char Vt;
} VN_VT;
typedef struct //栈
{
VN_VT *top;
VN_VT *bollow;
int size;
}stack;

4、根据文法求FIRSTVT集和LASTVT集

5、构造算符优先分析表

6、构造总控程序

7、对给定的表达式，给出准确与否的分析过程
8、给出表达式的计算结果。（本步骤可选作）

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

/**
 * @author [25'h]
 * @datetime 2022.11.02
 */
public class Reducing {
    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 HashMap<String, Set<String>[]> firstvtAndLastvt = new HashMap<>();//FIRST  和  FOLLOW
    /*
        firstvtAndLastvt的数据含义：
            - key : 非终结符
            - value : 非终结符对应的FIRSTVT  和  FOLLOWVT 集
                - 1     非终结符对应的FIRSTVT
                - 2     非终结符对应的FOLLOWVT
    */
    public static boolean[] booleansFirst;// 辅助变量
    public static boolean[] booleansLast;
    public static String[][] table;//优先表
    public static String objString;// 目标匹配字符串

    public static LinkedList<String> deque;

    public static void main(String[] args) {
        File file = new File("src/StringToJAVA/test3.txt");
        BufferedReader bufferedReader;
        try {
            // 读取文法和目标式子
            bufferedReader = new BufferedReader(new FileReader(file));
            startLabel = bufferedReader.readLine();
            // 读取非终结符
            non_ter.addAll(Arrays.asList(bufferedReader.readLine().split(" ")));
            booleansFirst = new boolean[non_ter.size()];// 初始化辅助变量
            booleansLast = new boolean[non_ter.size()];
            // 初始化firstAndFollow中的Map对象
            for (String s : non_ter) {
                firstvtAndLastvt.put(s, new HashSet[]{new HashSet(), new HashSet()});
            }
            // 读取终结符
            terSymbol.addAll(Arrays.asList(bufferedReader.readLine().split(" ")));
            table = new String[terSymbol.size() + 1][terSymbol.size() + 1];
            //将产生式右部或表达式分离
            String s;
            while ((s = bufferedReader.readLine()).contains("->")) {
                String[] split = s.split("->");
                formula.put(split[0], Arrays.asList(split[1].split("\\|")));
            }
            // 赋值目标串
            objString = s;
        } catch (Exception e) {
            e.printStackTrace();
        }
        // 生成firstvt和lastvt
        generateFirstVTAndLastVT();
        // 生成优先分析表
        generateTable();
        // 归约
        reducing();
        show();
    }

    private static void reducing() {
        // 终结符中添加结尾符号
        terSymbol.add("#");
        deque = new LinkedList<>();
        deque.push("#");
        for (int i = 0; i < objString.length(); i++) {
            // 取出下一个字符
            String sub = objString.substring(i, i + 1);
            if (terSymbol.contains(sub)) {// 是终结符
                // 栈最上面的终结符是temp
                String temp = terSymbol.contains(deque.peek()) ? deque.peek() : deque.get(1);
                // 看看跟上一个终结符和sub大优先级关系
                String bol = table[terSymbol.indexOf(temp)][terSymbol.indexOf(sub)];
                // 是> 就归约
                if (bol.equals(">")) {
                    func(sub);
                }
                // 归约后终结符入栈
            }
            deque.push(sub);// 直接压入
            showCurStack(i);
        }
    }

    //输出当前的栈状态
    private static void showCurStack(int i) {
        StringBuffer b = new StringBuffer();
        for (int j = deque.size() - 1; j >= 0; j--) {
            b = b.append(deque.get(j));
        }
        if (i != objString.length() - 1)
            b = b.append("\t\t\t").append(objString.substring(i + 1));
        System.out.println(b.toString());
    }


    private static void func(String curTer) {
        String te;
        // 栈顶非终结符读出
        if (!terSymbol.contains(deque.peek())) {
            deque.pop();
        }
        do {
            te = deque.pop();// 当前规约串的终结符te
// te左的非终结符
            if (!terSymbol.contains(deque.peek())) {
                deque.pop();
            }
        } while (!table[terSymbol.indexOf(deque.peek())][terSymbol.indexOf(te)].equals("<"));
        // 栈顶终结符
        te = deque.peek();
        deque.push("N");// 标记
        // 若还是>,则递归调用
        if (table[terSymbol.indexOf(te)][terSymbol.indexOf(curTer)].equals(">")) {
            func(curTer);
        }
    }

    private static void generateTable() {
        // 对于每个公式都要取出终结符
        for (String non : formula.keySet()) {
            List<String> list = formula.get(non);//non这个非终结符对应的生成式
            for (String f : list) {// 对于每个式子f
                ArrayList<String> li = new ArrayList<>();// 每个式子的终结符记下来，因为他们之间的关系是=
                // 对式子f要查找终结符位置
                for (int i = 0; i < f.length(); i++) {
                    // 对于f中每个元素sub
                    String sub = f.substring(i, i + 1);
                    // 若是终结符
                    if (terSymbol.contains(sub)) {
                        li.add(sub);//几下终结符
                        // 左边有非终结符
                        if (i != 0 && non_ter.contains(f.substring(i - 1, i))) {
                            //赋值“>”
                            pre(f.substring(i - 1, i), sub);
                        }
                        //右边有非终结符
                        if (i != f.length() - 1 && non_ter.contains(f.substring(i + 1, i + 2))) {
                            //赋值“<”
                            post(f.substring(i + 1, i + 2), sub);
                        }
                    }
                }
                // 想等情况赋值，注意是 j = i + 1
                for (int i = 0; i < li.size(); i++) {
                    for (int j = i + 1; j < li.size(); j++) {
                        table[terSymbol.indexOf(li.get(i))][terSymbol.indexOf(li.get(j))] = "=";
                    }
                }
            }
        }
        // 关于#的赋值
        Set<String>[] sets = firstvtAndLastvt.get(startLabel);
        for (String s : sets[0]) {
            table[terSymbol.size()][terSymbol.indexOf(s)] = "<";
        }
        for (String s : sets[1]) {
            table[terSymbol.indexOf(s)][terSymbol.size()] = ">";
        }
        table[terSymbol.size()][terSymbol.size()] = "=";

    }

    private static void post(String non, String ter) {
        int index = terSymbol.indexOf(ter);
        Set<String> set = firstvtAndLastvt.get(non)[0];
        for (String s : set) {
            table[index][terSymbol.indexOf(s)] = "<";
        }
    }

    private static void pre(String non, String ter) {
        int index = terSymbol.indexOf(ter);
        Set<String> set = firstvtAndLastvt.get(non)[1];
        for (String s : set) {
            table[terSymbol.indexOf(s)][index] = ">";
        }
    }

    //生成firstvt和lastvt
    private static void generateFirstVTAndLastVT() {
        for (String s : non_ter) {
            if (!booleansFirst[non_ter.indexOf(s)])
                generateEachFirstVT(s);
            if (!booleansLast[non_ter.indexOf(s)]) {
                generateEachLastVT(s);
            }
        }
    }

    /*
    生成每个非终结符non的Lastvt集
     */
    private static void generateEachLastVT(String non) {
        Set<String> curList = firstvtAndLastvt.get(non)[1];
        for (String s : formula.get(non)) {
            // lastvt本质就是firstvt反过来的求法
            modify(non, curList, new StringBuffer(s).reverse().toString(), 1);
        }
        booleansLast[non_ter.indexOf(non)] = true;
    }

    /*
    生成每个非终结符non的Firstvt集
     */
    private static void generateEachFirstVT(String terNon) {
        Set<String> curList = firstvtAndLastvt.get(terNon)[0];
        for (String s : formula.get(terNon)) {
            modify(terNon, curList, s, 0);
        }
        booleansFirst[non_ter.indexOf(terNon)] = true;
    }


    private static void modify(String non, Set<String> curList, String s, int i) {
        String firstSub = s.substring(0, 1);
        if (terSymbol.contains(firstSub)) {// 终结符开头
            curList.add(firstSub);
        } else {// 非终结符开头
            // 终结符是第二个位置
            if (s.length() >= 2 && terSymbol.contains(s.substring(1, 2))) {
                curList.add(s.substring(1, 2));
            }
            // firstSub和non相同，避免栈溢出返回
            if (firstSub.equals(non)) return;
            if (i == 0) {// 求firstvt，用booleansFirst
                if (!booleansFirst[non_ter.indexOf(firstSub)]) {
                    generateEachFirstVT(firstSub);
                }
            } else {// 求lastvt，booleansLast
                if (!booleansLast[non_ter.indexOf(firstSub)]) {
                    generateEachLastVT(firstSub);
                }
            }
            curList.addAll(firstvtAndLastvt.get(firstSub)[i]);

        }
    }

    private static void show() {
        System.out.println(startLabel);
        System.out.println(Arrays.toString(non_ter.toArray()));
        System.out.println(Arrays.toString(terSymbol.toArray()));
        for (String s : formula.keySet()) {
            System.out.println(s + "\t" + Arrays.toString(formula.get(s).toArray()));
        }
        System.out.println();
        for (String s : firstvtAndLastvt.keySet()) {
            System.out.println(s + "\t" + Arrays.toString(firstvtAndLastvt.get(s)[0].toArray()) + "\t" + Arrays.toString(firstvtAndLastvt.get(s)[1].toArray()));
        }
        System.out.println();
        for (String[] strings : table) {
            System.out.println(Arrays.toString(strings));
        }
    }

}
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

test3.txt文件：

E
E T F
i * / + - ( )
E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|i
(1+2)/3+4-(5+6/7)#
1
2
3
4
5
6
7

输出结果：

"D:\Program Files\Java\jdk1.8.0_291\bin\java.exe" "-javaagent:D:\IntelliJ IDEA 2020.1\lib\idea_rt.jar=54769: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.Reducing
#(			1+2)/3+4-(5+6/7)#
#(1			+2)/3+4-(5+6/7)#
#(1+			2)/3+4-(5+6/7)#
#(1+2			)/3+4-(5+6/7)#
#(N)			/3+4-(5+6/7)#
#N/			3+4-(5+6/7)#
#N/3			+4-(5+6/7)#
#N+			4-(5+6/7)#
#N+4			-(5+6/7)#
#N-			(5+6/7)#
#N-(			5+6/7)#
#N-(5			+6/7)#
#N-(5+			6/7)#
#N-(5+6			/7)#
#N-(5+6/			7)#
#N-(5+6/7			)#
#N-(N)			#
#N#
E
[E, T, F]
[i, *, /, +, -, (, ), #]
T	[T*F, T/F, F]
E	[E+T, E-T, T]
F	[(E), i]

T	[(, i, *, /]	[), i, *, /]
E	[(, i, *, +, -, /]	[), i, *, +, -, /]
F	[(, i]	[), i]

[null, >, >, >, >, null, >, >]
[<, >, >, >, >, <, >, >]
[<, >, >, >, >, <, >, >]
[<, <, <, >, >, <, >, >]
[<, <, <, >, >, <, >, >]
[<, <, <, <, <, <, =, null]
[null, >, >, >, >, null, >, >]
[<, <, <, <, <, <, null, =]

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
34
35
36
37
38
39
40

相关阅读:
如何结构化解决问题
 高企申报需要的专利数量是多少？
2022快手电商短视频运营白皮书：Q2对比Q1GMV总值增长率达12%
【C++类和对象】定义 | 封装 | 访问限定符 | 作用域 | 对象模型 | this指针
 Redis四大特殊数据类型的学习和理解
 TCP、IP和HTTP的区别和联系
 孙宇晨接受瑞士媒体Bilan采访：熊市不会持续太久
 机器学习入门介绍
 Eslint配置
 ‘vue’不是内部或外部命令，也不是可运行的程序或批处理文件
原文地址：https://blog.csdn.net/weixin_54884881/article/details/127696087

郑州大学编译原理实验三算符优先分析算法JAVA

一、 实验目的

二、 实验内容

一、实验目的

二、实验内容