编译技术上机题不完全汇总（Java版）

说在前面的话

编译技术上机终于结束了。因为自己对于编译实在是没什么兴趣，上机的代码写得也不算太齐全，有时候检查松就浑水摸鱼混过去了。挑出几份写的还算像样的贴出来吧。

以下代码都是Java语言写的，也顺便熟悉一下对Java语言的运用。

相关代码已经上传至码云，点击查看

LL1语法分析器

该程序使用的是递归下降方式，对应以下文法：
E -> TE’
E’ -> +TE’|空串
T -> FT’
T’ -> *FT’|空串
F -> (E)|id

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
import java.util.Scanner;
public class LL1 {
    private String lookahead = "";
    private int counter = 0;
    private String[] inputStr = null;
    private boolean isSuccess = true;
    private boolean getIsSuccess() {
        return isSuccess && (counter == inputStr.length-2);
    }
    private void start() {
        E();
    }
    private LL1() {
        Scanner input = new Scanner(System.in);
        inputStr = input.nextLine().split(" ");
        lookahead = inputStr[0];
    }
    private String nextToken() {
        return (inputStr[counter+1].equals("#")) ? "" : inputStr[++counter];
    }
    private void error() {
        isSuccess = false;
    }
    private void match(String t) {
        if (lookahead.equals(t)) {
            System.out.println("match " + t);
            lookahead = nextToken();
        }
        else
            error();
    }
    private void E() {
        if (lookahead.equals("(") || lookahead.equals("id")) {
            System.out.println("E->TE'");
            T();
            E_();
        }
    }
    private void E_() {
        if (lookahead.equals("+")) {
            System.out.println("E'->+TE'");
            match("+");
            T();
            E_();
        } else {
            System.out.println("E'->null");
            //match("");
        }
    }
    private void T() {
        if (lookahead.equals("(") || lookahead.equals("id")) {
            System.out.println("T->FT'");
            F();
            T_();
        }
    }
    private void T_() {
        if (lookahead.equals("*")) {
            System.out.println("T'->*FT'");
            match("*");
            F();
            T_();
        } else {
            System.out.println("T'->null");
            //match("");
        }
    }
    private void F() {
        if (lookahead.equals("(")) {
            System.out.println("F->(E)");
            match("(")
            ;E();
            match(")");
        }
        else if(lookahead.equals("id")) {
            System.out.println("F->id");
            match("id");
        }
    }
    public static void main(String[] args) {
        LL1 ll = new LL1();
        ll.start();
        if (ll.getIsSuccess())
            System.out.println("SUCCESS");
        else
            System.out.println("ERROR");
    }
}

LR语法分析器

该程序事先需要手工构造action表和goto表，对应以下文法：
E -> E+T | T
T -> T*F | F
F -> (E) | id

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
import java.util.*;
public class LR {
    private String[] inputStr = null;
    private int counter = 0;
    private String [][] expression = {
            {" ", ""},
            {"E", "E+T"},
            {"E", "T"},
            {"T", "T*F"},
            {"T", "F"},
            {"F", "(E)"},
            {"F", "@"}
    };
    private String[][] action = {
            {"s 5", "err", "err", "s 4", "err", "err"},
            {"err", "s 6", "err", "err", "err", "acc"},
            {"err", "r 2", "s 7", "err", "r 2", "r 2"},
            {"err", "r 4", "r 4", "err", "r 4", "r 4"},
            {"s 5", "err", "err", "s 4", "err", "err"},
            {"err", "r 6", "r 6", "err", "r 6", "r 6"},
            {"s 5", "err", "err", "s 4", "err", "err"},
            {"s 5", "err", "err", "s 4", "err", "err"},
            {"err", "s 6", "err", "err", "s 11", "err"},
            {"err", "r 1", "s 7", "err", "r 1", "r 1"},
            {"err", "r 3", "r 3", "err", "r 3", "r 3"},
            {"err", "r 5", "r 5", "err", "r 5", "r 5"}
    };
    LR() {
        Scanner input = new Scanner(System.in);
        inputStr = input.nextLine().split(" ");
    }
    private int getA(String str) {
        switch (str) {
            case "id": return 0;
            case "+": return 1;
            case "*": return 2;
            case "(": return 3;
            case ")": return 4;
            default: return 5;
        }
    }
    private String[][] goTo = {
            {"1", "2", "3"},
            {"err", "err", "err"},
            {"err", "err", "err"},
            {"err", "err", "err"},
            {"8", "2", "3"},
            {"err", "err", "err"},
            {"err", "9", "3"},
            {"err", "err", "10"},
            {"err", "err", "err"},
            {"err", "err", "err"},
            {"err", "err", "err"},
            {"err", "err", "err"},
    };
    private int getIndex(String str) {
        switch (str) {
            case "E": return 0;
            case "T": return 1;
            default: return 2;
        }
    }
    private LinkedList<String> stack = new LinkedList<>();
    private String getNextString() {
        return inputStr[counter++];
    }
    private void print(int index) {
        String tempStr = expression[index][0] + "->" + expression[index][1];
        System.out.println("按" + tempStr.replaceFirst("@", "id") + "规约");
    }
    private void analysis() {
        //令next的值为第一个符号
        String next = getNextString();
        //初始化栈
        stack.addLast("0");
        while (true) {
            //令state为栈顶的状态
            int state = Integer.parseInt(stack.getLast());
            String[] tempArray = action[state][getA(next)].split(" ");
            //如果为移进动作
            if (tempArray[0].equals("s")) {
                System.out.println("移进");
                //把next和新状态依次压入栈
                stack.addLast(next);
                stack.addLast(tempArray[1]);
                //令next是下一个输入符号
                next = getNextString();
                //如果为规约动作
            } else if (tempArray[0].equals("r")) {
                //栈顶退掉两倍的符号
                for(int i = 0; i < 2*expression[Integer.parseInt(tempArray[1])][1].length(); i++) {
                    stack.removeLast();
                }
                //令temp是现在的栈顶状态
                int temp = Integer.parseInt(stack.getLast());
                //把非终结符和新状态压入栈
                stack.addLast(expression[Integer.parseInt(tempArray[1])][0]);
                stack.addLast(goTo[temp][getIndex(expression[Integer.parseInt(tempArray[1])][0])]);
                //输出产生式
                print(Integer.parseInt(tempArray[1]));
            } else if (tempArray[0].equals("acc")) {
                System.out.println("接受");
                break;
            }else {
                System.out.println("ERROR");
                break;
            }
        }
    }
    public static void main(String[] args) {
        LR lr = new LR();
        lr.analysis();
    }
}

基于LR语法分析器的语法制导翻译

文法同之前的LR分析器。程序结构大体类似。

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
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class LRS {
    class StateVal {
        String state;
        String val;
        StateVal(String state, String value) {
            this.state = state;
            this.val = value;
        }
    }
    private String[] inputStr = null;
    private int counter = 0;
    private String [][] expression = {
            {" ", ""},
            {"E", "E+T"},
            {"E", "T"},
            {"T", "T*F"},
            {"T", "F"},
            {"F", "(E)"},
            {"F", "@"}
    };
    private String[][] action = {
            {"s 5", "err", "err", "s 4", "err", "err"},
            {"err", "s 6", "err", "err", "err", "acc"},
            {"err", "r 2", "s 7", "err", "r 2", "r 2"},
            {"err", "r 4", "r 4", "err", "r 4", "r 4"},
            {"s 5", "err", "err", "s 4", "err", "err"},
            {"err", "r 6", "r 6", "err", "r 6", "r 6"},
            {"s 5", "err", "err", "s 4", "err", "err"},
            {"s 5", "err", "err", "s 4", "err", "err"},
            {"err", "s 6", "err", "err", "s 11", "err"},
            {"err", "r 1", "s 7", "err", "r 1", "r 1"},
            {"err", "r 3", "r 3", "err", "r 3", "r 3"},
            {"err", "r 5", "r 5", "err", "r 5", "r 5"}
    };
    private LRS() {
        Scanner input = new Scanner(System.in);
        inputStr = input.nextLine().split(" ");
    }
    private int getA(String str) {
        switch (str) {
            case "id": return 0;
            case "+": return 1;
            case "*": return 2;
            case "(": return 3;
            case ")": return 4;
            default: return 5;
        }
    }
    private String[][] goTo = {
            {"1", "2", "3"},
            {"err", "err", "err"},
            {"err", "err", "err"},
            {"err", "err", "err"},
            {"8", "2", "3"},
            {"err", "err", "err"},
            {"err", "9", "3"},
            {"err", "err", "10"},
            {"err", "err", "err"},
            {"err", "err", "err"},
            {"err", "err", "err"},
            {"err", "err", "err"},
    };
    private int getIndex(String str) {
        switch (str) {
            case "E": return 0;
            case "T": return 1;
            default: return 2;
        }
    }
    private boolean isNumeric(String str){
        Pattern pattern = Pattern.compile("[0-9]*");
        Matcher isNum = pattern.matcher(str);
        return isNum.matches();
    }
    private LinkedList<String> stack = new LinkedList<>();
    private LinkedList<StateVal> calStack = new LinkedList<>();
    private String getNextString() {
        return inputStr[counter++];
    }
    private void print(int index) {
        String tempStr = expression[index][0] + "->" + expression[index][1];
        System.out.println("按" + tempStr.replaceFirst("@", "id") + "规约");
    }
    private void init() {
        System.out.println("-1");
    }
    private void analysis() {
        //令next的值为第一个符号
        String next = getNextString();
        //初始化栈
        if (next.charAt(0) == '-') {
            this.init();
            return ;
        }
        stack.addLast("0");
        while (true) {
            //令state为栈顶的状态
            int state = Integer.parseInt(stack.getLast());
            String[] tempArray = null;
            //如果next为数字
            if (isNumeric(next)) {
                tempArray = action[state][getA("id")].split(" ");
            } else {
                tempArray = action[state][getA(next)].split(" ");
            }
            //如果为移进动作
            if (tempArray[0].equals("s")) {
                System.out.println("移进");
                //把next和新状态依次压入栈
                stack.addLast(next);
                stack.addLast(tempArray[1]);
                //给计算栈里压入数据
                calStack.addLast(new StateVal(next, next));
                //令next是下一个输入符号
                next = getNextString();
                //如果为规约动作
            } else if (tempArray[0].equals("r")) {
                //栈顶退掉两倍的符号
                for(int i = 0; i < 2*expression[Integer.parseInt(tempArray[1])][1].length(); i++) {
                    stack.removeLast();
                }
                //令temp是现在的栈顶状态
                int temp = Integer.parseInt(stack.getLast());
                //把非终结符和新状态压入栈
                stack.addLast(expression[Integer.parseInt(tempArray[1])][0]);
                //更改计算栈的栈顶状态
                int top = calStack.size() - 1;
                switch (Integer.parseInt(tempArray[1])) {
                    case 1:
                        calStack.get(top-2).val = Integer.toString(
                                Integer.parseInt(calStack.get(top-2).val) +
                                Integer.parseInt(calStack.get(top).val));
                        //相当于top-2
                        calStack.removeLast();
                        calStack.removeLast();
                        break;
                    case 3:
                        calStack.get(top-2).val = Integer.toString(
                                Integer.parseInt(calStack.get(top-2).val) *
                                        Integer.parseInt(calStack.get(top).val));
                        //相当于top-2
                        calStack.removeLast();
                        calStack.removeLast();
                        break;
                    case 5:
                        calStack.get(top-2).val = Integer.toString(
                                Integer.parseInt(calStack.get(top-1).val));
                        //相当于top-2
                        calStack.removeLast();
                        calStack.removeLast();
                        break;
                    default:
                        calStack.getLast().state = expression[Integer.parseInt(tempArray[1])][0];
                        break;
                }
                stack.addLast(goTo[temp][getIndex(expression[Integer.parseInt(tempArray[1])][0])]);
                //输出产生式
                print(Integer.parseInt(tempArray[1]));
            } else if (tempArray[0].equals("acc")) {
                System.out.println("接受");
                System.out.println("计算结果为：" + calStack.getLast().val);
                break;
            }else {
                System.out.println("ERROR");
                System.out.println("请重新输入");
                break;
            }
        }
    }
    public static void main(String[] args) {
        LRS lrs = new LRS();
        lrs.analysis();
    }
}

求first集

这份好像不是自己写的……其实写得不咋地，不过用Java语言写的也不多，姑且贴上来。

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
import java.util.*;
public class FirstFollow3 {
    public ArrayList<String[]> in=new ArrayList<String[]>();//在这存放的是拆分后最简单的文法，也是由用户输入
    public ArrayList<String[]> first = new ArrayList<String[]>();//包括左推导符和其First集
    public ArrayList<String[]> follow = new ArrayList<String[]>();
    public ArrayList<String[]> track = new ArrayList<String[]>();//track有一条一条的非终结符串组成的路径数组
    public FirstFollow3(){
        Scanner sc = new Scanner(System.in);
        System.out.println("请分行输入一个完整文法:(end结束)");
        String sline="";
        sline=sc.nextLine();
        while(!sline.startsWith("end")){
            StringBuffer buffer=new StringBuffer(sline);
            int l=buffer.indexOf(" ");
            while(l>=0){//去空格
                buffer.delete(l,l+1);
                l=buffer.indexOf(" ");
            }
            sline=buffer.toString();
            String s[]=sline.split("->");//左推导符
            if(s.length==1)
                s=sline.split("→");//考虑到输入习惯和形式问题
            if(s.length==1)
                s=sline.split("=>");
            if(s.length==1){
                System.out.println("文法有误");
                System.exit(0);
            }
            StringTokenizer fx = new StringTokenizer(s[1],"|︱");//按英文隔符拆开产生式或按中文隔符拆开
            while(fx.hasMoreTokens()){
                String[] one = new String[2];//对于一个语句只需保存两个数据就可以了，语句左部和语句右部的一个简单导出式，假如有或符，就按多条存放
                one[0]=s[0];//头不变,0位置放非终结符
                one[1]=fx.nextToken();//1位置放导出的产生式，就是产生式右部的一个最简单导出式
                in.add(one);
            }
            sline=sc.nextLine();
        }
//求First集过程
        this.process("First");
/*
* 打印First集算法和First集
*/
        System.out.println("\nFirst集算法：");
        //this.print(track);//打印First集算法
        System.out.println("\nFirst集：");
        for(int i=0;i<first.size();i++){
            String[] r=first.get(i);
            System.out.print("First("+r[0]+")={");
            for(int j=1;j<r.length;j++){
                System.out.print(r[j]);
                if(j<r.length-1)
                    System.out.print(",");
            }
            System.out.println("}");
        }
        track.clear();//因为下面还要用，这里就先清空了
        //求Follow集过程
        this.process("Follow");
        System.out.println("\nFollow集算法：");
        for(int i=0;i<track.size();i++){
            String[] one = track.get(i);
            System.out.print("Follow("+follow.get(i)[0]+"):\t");
            for(int j=0;j<one.length;j++)
                System.out.print(one[j]+"\t");
            System.out.println();
        }
        System.out.println("\nFollow集：");
        for(int i=0;i<follow.size();i++){
            String[] r=follow.get(i);
            System.out.print("Follow("+r[0]+")={");
            for(int j=1;j<r.length;j++){
                System.out.print(r[j]);
                if(j<r.length-1)
                    System.out.print(",");
            }
            System.out.println("}");
        }
    }
    public void process(String firstORfollow){
        for(int i=0;i<in.size();i++){
            boolean bool=true;
            for(int j=0;j<i;j++)
                if(in.get(j)[0].equals(in.get(i)[0]))
                    bool=false;
            if(bool){
                ArrayList<String> a=null;
                if(firstORfollow.equals("First"))
                    a=this.getFirst(in.get(i)[0],"First("+in.get(i)[0]+")/");
//                else if(firstORfollow.equals("Follow"))
//                    a=this.getFollow(in.get(i)[0],in.get(i)[0],"");
                String[] sf = new String[a.size()/2+1];
                String[] st = new String[a.size()/2];
                sf[0]=in.get(i)[0];
                for(int j=0; j<a.size(); j++)
                {
                    if(j%2==0)
                        sf[j/2+1]=a.get(j);
                    else
                        st[j/2]=a.get(j);
                }
                if(firstORfollow.equals("First"))
                    first.add(sf);//first集
                //else if(firstORfollow.equals("Follow"))
                 //   follow.add(sf);
                track.add(st);//对应上面求得集的路径，在开始保存该非终结符了，因为已保存了该字符的First或Follow表示法
            }
        }
    }
    public ArrayList<String> getFirst(String s,String track1){//s表示左推导，track表示寻找路径，避免循环查找
        ArrayList<String> result = new ArrayList<String>();
        ArrayList<String> result1 = new ArrayList<String>();
        if(Character.isUpperCase(s.charAt(0))){//如果是非终结符，大写
            for(int i=0;i<in.size();i++){
                String[] one = in.get(i);
                if(s.equals(one[0])){
                    if(track1.substring(0,track1.length()-9).indexOf("First("+s+")")>=0)//假如在查找过程嵌套了这步，证明进入了无限循环，不需再找，此路径无结果
                        ;//有点要注意一下，本来一开始就把第一个开始推导符的First路径放进去了的，所以要避开这一次，不然已开始就结束了
                    else if(one[1].length()==1||one[1].charAt(1)!='\''&&one[1].charAt(1)!='’')
                        result1=getFirst(one[1].charAt(0)+"",track1+"First("+one[1].charAt(0)+")/");
                    else if(one[1].length()>1&&one[1].charAt(1)=='\''||one[1].charAt(1)=='’')//假如接下来一个要求First的非终结符带了一撇，那一撇包括英文表示和中文表示
                        result1=this.getFirst(one[1].substring(0,2),track1+"First("+one[1].substring(0,2)+")/");
                    result=addArrayString(result,result1);
                    result1.clear();
                }
            }
        }
        else{//如果产生式首字符是终结字符
            if(s.equals("ε"))//注意：表示空的字符只能是这种了，其他形式在这个编译器中不能通过，还请原谅
                result1.add("#");
            else
                result1.add(s);
            result1.add(track1);//为了方便，把路径也加入了结果集，不然可能路径不匹配，没办法，因为中间有删去重复项
            result=result1;
        }
        return result;
    }
    public ArrayList<String> getFollow(String s,String element,String track1){//从右至左反推，不是求Follow的等价Follow，因为推到后面的反而范围大
        ArrayList<String> result = new ArrayList<String>();
        ArrayList<String> result1 = new ArrayList<String>();
        if(Character.isUpperCase(s.charAt(0))){
            for(int i=0;i<in.size();i++){
                String[] one = in.get(i);
                int slen=s.length();
                int olen=one[1].length();
                if(element.equals(in.get(0)[0])){//如果是开始符号，或是可以反推到开始符号，证明也可以顺推导开始符号
                    result1.add("#");
                    result1.add(in.get(0)[0]+"→"+in.get(0)[0]+"\t");
                    result = addArrayString(result,result1);
                    result1.clear();
                }
                if(one[1].indexOf(s)>=0&&track1.indexOf((char)('a'+i)+"")>=0)//假如之前走过某一步，就不必再走了，那是死循环，之前在这语句前面加了个else,结果又部分内容显示不出来，总算发现了，就算反推到开始符号，也不一定就到结果了的，开始符号也可以反推，所以要继续
                    ;
                else if(one[1].indexOf(s)>=0&&(olen-slen==one[1].indexOf(s)||slen==2||one[1].charAt(one[1].indexOf(s)+1)!='’'&&one[1].charAt(one[1].indexOf(s)+1)!='\''))
                {//如果在右产生式中真正存在需要求反推的字符,后面的条件控制它是真正存在，因为里面包含这个字符也不一定是真，就像E’中包含E，但这不是真正的包含
                    int index=-1;
                    index = one[1].indexOf(s,0);
                    while(index>=0){//之前这没有用到循环，结果可能少点东西，仔细一想，必须要，就算是一个推导语句，也可能推出多个相同非终结符的组合，其实这也是一种特殊情况了，不考虑也可能正确了，也可能之前在其他地方把这样的结果求出来了，不求也没事，但就像假如要求T的Follow集，假如可以产生出T+a*T*b，这时还是有用的，万一吧
                        if(olen-slen==index){//如果该非终结符在末尾，那么求导出该产生式的非终结符的倒推
                            result1=getFollow(one[0], element,track1+(char)('a'+i));
                            result=addArrayString(result,result1);
                            result1.clear();
                        }else{//如果后继非终结符在产生式中不是最后
                            int t=index+slen;//指向在产生式非终结符s的后一个字符位置
                            result1=returnFirstofFollow(s, element, track1, one[0], one[1], index, t);
                            result=addArrayString(result,result1);//之前也没写这句话，结果把之前的内容覆盖了，就是之前的数据丢失
                            result1.clear();
                        }
                        index = one[1].indexOf(s,index+1);
                    }//endwhile
                }
                if(one[1].endsWith(element)){//如果最开始要求的Follow集非终结符在末尾
                    result1.add("#");
                    result1.add(in.get(0)[0]+"→"+one[1]+"\t");
                    result=addArrayString(result,result1);//之前也没写这句话，结果把之前的内容覆盖了，就是之前的数据丢失
                    result1.clear();
                }
            }//endfor
        }
        return result;
    }
    public ArrayList<String> returnFirstofFollow(String s,String element,String track1,String one0,String one1,int index,int t){//返回求Follow集中要求的First集部分
        ArrayList<String> result = new ArrayList<String>();
        ArrayList<String> result1 = new ArrayList<String>();
        ArrayList<String > beckFirst;
        String lsh;//记录下一个字符
        if(t+1<one1.length()&&(one1.charAt(t+1)=='’'||one1.charAt(t+1)=='\''))//如果随后的非终结符还带了一撇符
            lsh=one1.substring(t,t+2);
        else//如果没带一撇,就只要截取一个字母就可以了
            lsh=one1.substring(t,t+1);
        String[] ls = null;
        int beflen=2;
        if(track1.length()>0){//这些都是为了算法输出容易理解点用的，其实要不输出这算法，要省下好多东西
            ls=in.get((int)(track1.charAt(track1.length()-1)-'a'));//得到上一步调用的语句
            if(Character.isUpperCase(ls[1].charAt(ls[1].length()-1)))
                beflen=1;
        }
        beckFirst=this.getFirst(lsh,"First("+lsh+")/");//相当于得到后继字符的First集
        for(int j=0;j<beckFirst.size()/2;j++){//调用求First集，返回的不一定只一个结果
            String lh="";
            if(beckFirst.get(j*2).equals("#")){
                result1.add(beckFirst.get(j*2));//这个加了是数据，下面一步就是把地址加上，就是一个结果，要两份数据
                if(ls==null)
                    lh=in.get(0)[0]+"→"+one1+"→"+one1.substring(0,index)+element+"ε"+one1.substring(t+lsh.length(),one1.length());
                else
                    lh=in.get(0)[0]+"→"+one1+"→"+one1.substring(0,index)+ls[1]+one1.substring(index+s.length(),one1.length())+"→."+element+"ε"+one1.substring(t+lsh.length(),one1.length());
                result1.add(lh);
                result=addArrayString(result,result1);
                result1.clear();
                if(1+index+lsh.length()<one1.length())//证明后面还有字符,为什么要这一步，打个比方把，假如要求F的Follow集，而存在产生式FPQ,而P的有个First集为空，那么得还接着求Q的First，类推，假如最后一个字符Q还是返回空，那么求要求产生式左边的推导非终结符的Follow集了，必须把这些结果都算到F的Follow集中去
                    result1=returnFirstofFollow(s, element, track1, one0,one1, index, t+lsh.length());
                else//到最后,那么求要求产生式左边的推导非终结符的Follow集了，其实这和上面一种情况都很特殊了，一般用不上了
                    result1=getFollow(one0, element, track1);
            }
            else{//其实下面这一大坨都是为了易懂一点，Follow集算法清晰一点，好苦啊
                if(Character.isUpperCase(one1.charAt(t))){//如果是有随后的一个非终结符的First集求出的结果
                    if(ls==null)
                        lh=in.get(0)[0]+"→"+one1+"→"+one1.substring(0,index)+element+beckFirst.get(j*2)+one1.substring(t+lsh.length(),one1.length());
                    else
                        lh=in.get(0)[0]+"→"+one1+"→"+one1.substring(0,index)+ls[1]+one1.substring(index+s.length(),one1.length())+"→."+element+beckFirst.get(j*2)+one1.substring(t+lsh.length(),one1.length());
                }
                else{//如果不是大写，就是终结符了，那么用First集求出来的结果连接起来还是一样的，所以不要重复打印两次了
                    if(ls==null){
                        if(element==in.get(0)[0]||s.equals(element))
                            lh=in.get(0)[0]+"→"+one1.substring(0,index)+element+one1.substring(t,one1.length())+"\t";
                        else
                            lh=in.get(0)[0]+"→"+one1+"→"+one1.substring(0,index)+element+one1.substring(t,one1.length())+"\t";
                    }
                    else{
                        if(ls[1].length()==1||ls[1].length()==2&&!ls[1].endsWith("’")&&!ls[1].endsWith("\'"))
                            lh=in.get(0)[0]+"→"+one1+"→"+one1.substring(0,index)+element+one1.substring(t,one1.length());
                        else
                            lh=in.get(0)[0]+"→"+one1+"→"+one1.substring(0,index)+ls[1]+one1.substring(index+s.length(),one1.length())+"→."+element+one1.substring(t,one1.length())+"!";
                    }
                }
                result1.add(beckFirst.get(j*2));//这个加了是数据，下面一步就是把地址加上，就是一个结果，要两份数据
                result1.add(lh);
            }
        }
        result=addArrayString(result,result1);//之前也没写这句话，结果把之前的内容覆盖了，就是之前的数据丢失
        result1.clear();
        return result;
    }
    public ArrayList<String> addArrayString(ArrayList<String> a,ArrayList<String> b){//两个字符串数组相加
        ArrayList<String> result = new ArrayList<String>();
        for(int i=0;i<a.size();i+=2){//因为这每一个结果，都保存了两个数据，第一个是结果，第二个位置保存的是得到这结果的路径
            String s = a.get(i);
            if(result.contains(s)||s.equals("")){//如果结果集包含了这个字符串，就不加入结果集了，就是为了去掉重复项
                int index=result.indexOf(s);
                if(result.get(index+1).length()>a.get(i+1).length()){//如果新来的路径比现有的短
                    result.set(index, s);
                    result.set(index+1,a.get(i+1));
                }
                continue;
            }
            result.add(s);
            result.add(a.get(i+1));//还是要把路径继续保存在新的结果集中
        }
        for(int i=0;i<b.size();i+=2){
            String s = b.get(i);
            if(result.contains(s)||s.equals("")){
                int index=result.indexOf(s);
                if(result.get(index+1).length()>b.get(i+1).length()){//如果新来的路径比现有的短
                    result.set(index, s);
                    result.set(index+1,b.get(i+1));
                }
                continue;
            }
            result.add(s);//偶数地址存放的是数据
            result.add(b.get(i+1));//奇数地址存放的是该数据获得的路径
        }
        return result;
    }
    public void print(ArrayList<String[]> list){
        for(int i=0;i<list.size();i++){//循环非终结符个数次数
            String[] one = list.get(i);//得到某一个非终结符运行的所有路径
            String[][] strings= new String[one.length][];
            String[] finals = new String[one.length];//路径最终站点
            int number=0;//记录某一步最终有效站点个数，本来有几条路径，就因该有几个有效站点，但可能有些站点有重复的，即从同一站点发出
            int max=0;
            for(int j=0;j<one.length;j++){
                strings[j]=one[j].split("/");
                if(strings[j].length>max)
                    max=strings[j].length;//求得某一非终结符路径最长一条
            }
            for(int j=0;j<max;j++){//循环最长站点次数
                number=0;
                for(int k=0;k<strings.length;k++){//有多少条路径就循环多少次
                    String lsh="";
                    if(j>=strings[k].length){
                        lsh=strings[k][strings[k].length-1];
                    }else {
                        lsh=strings[k][j];
                    }
                    int m=0;
                    for(m=0;m<number;m++){//记录有效站点
                        if(lsh.equals(finals[m]))
                            break;
                    }
                    if(m==number){
                        finals[number]=lsh;
                        number++;
                    }
                }
                for(int k=0;k<number;k++){//打印每一条路径的某个站点
                    System.out.print(finals[k]);
                    if(k!=number-1)
                        System.out.print(" + ");
                }
                if(j<max-1)
                    System.out.print(" = ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args){
        new FirstFollow3();
    }
}