CoderZQYのBlog

个人不定期更新的学习周报

0%

operator_precedence

发表于 更新于 分类于

编译原理实验4——算符优先文法实现表达式求值

1、概述

​ 算符优先分析法(Operator Precedence Parse)是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。

  • 优点：简单，有效，适合表达式的分析。
  • 缺点：只适合于算符优先文法，是一个不大的文法类。

2、FirstVT集和LastVT集

2.1 FirstVT集

  • 定义：FirstVT(P) = {a|P=>a…或P=>Qa…，a属于Vt，Q属于Vn}
  • 求法：
    • 若P→a…或P→Qa…，则将a加入FirstVT(P);
    • 若P→Q…，则FirstVT(Q)加入FirstVT(P);
    • 直至FirstVT(P)不再增大。

2.2 LastVT集

  • 定义：LastVT(P) = {a|P=>…a或P=>…aQ，a属于Vt，Q属于Vn}
  • 求法：
    • 若P→…a或P→…aQ，则a属于LastVT(P);
    • 若P→…Q，则LastVT(Q)含于LastVT(P);
    • 直至LastVT(P)不再增大。

3、算符优先关系表

终结符之间的优先关系

对算符文法G，a、b属于Vt 定义

  • a = b: G中有P→. . .ab. . .或P→. . .aQb. . .
  • a < b: G中有P→. . .aQ. . .且Q=>b…或Q=>Rb…
  • a > b: G中有P→. . .Qb. . . 且Q=>. ..a或Q=>…aR

4、分析句子

4.1 界定右句型的句柄

  • < 标记句柄的左端
  • = 出现在句柄的内部
  • > 标记句柄的右端

4.2 发现句柄的过程：

  • 从左端开始扫描串，直到遇到第一个>为止。
  • 向左扫描，跳过所有的=，直到遇到一个<为止。
  • 句柄包括从上一步遇到的 ‘<’ 右部，到第一个 ‘>’ 左部之间的所有符号，包括介于期间或者两边的非终结符

4.3 非终结符的处理

因为非终结符不能影响语法分析，所以不需要区分它们，于是只用一个占位符来代替它们

4.4 算法的主体思想

  • 用栈存储已经看到的输入符号，用优先关系指导移动归约语法分析器的动作，如果栈顶的终结符和下一个输入符之间的优先关系是<或=，则将输入符移进栈，表示还没有发现句柄的右端，如果是>关系，就调用归约
  • 算法描述：
    • 输入：输入字符串ω和优先关系表
    • 输出：如果ω是语法产生的一个句子，则输出其用来归约的产生式；如果有错误，则转入错误处理

5、Java代码实现

5.1 Producter类

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
public class Producter {
    private String producter;   // 产生式

    public Producter(String producter) {
        this.producter = producter;
    }

    public Character getLeft(){
        String[] arr = producter.split("->");
        return arr[0].charAt(0);
    }

    public String getRight(){
        String[] arr = producter.split("->");
        return arr[1];
    }
    /**
     * 判断一个产生式是否符合算符优先文法要求
     * 如果没有多个连续非终结符号相连的就是算符优先文法
     * @return
     */
    public boolean isOperPrior(){
        String right = getRight();
        for (int i = 0; i < right.length(); i++) {
            if(right.charAt(i)>='A' && right.charAt(i)<='Z'){
                if(i+1<right.length() && right.charAt(i+1)>='A' && right.charAt(i+1)<='Z'){
                    return false;
                }
            }
        }
        return true;
    }
    @Override
    public String toString() {
        return producter;
    }
}

5.2 F_L工具类，用于求取FirstVT集和LastVT集

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
public class F_L {
    private static Map<Character, Set<Character>> firstVt = new HashMap<>();    //firstVT集合
    private static Map<Character, Set<Character>> lastVt = new HashMap<>();     //lastVT集合
    private static Set<Producter> gs;                                           //文法
    /**
     * 根据输入的语法，获得相应 firstVT和 lastVT集合
     * @param gs 待处理的文法
     */
    public F_L(Set<Producter> producters) {
        gs = producters;                            //初始化文法
        for(Character vn : GSBuilder.getVN(gs)) {
            Set<Character> fvt = new HashSet<>();   //得到firstVT集
            getFirstVT(vn, fvt);
            firstVt.put(vn, fvt);

            Set<Character> lvt = new HashSet<>();   //得到lastVT集
            getLastVT(vn,lvt);
            lastVt.put(vn,lvt);
        }
    }

    public Map<Character, Set<Character>> getFirstVt() {
        return firstVt;
    }

    public Map<Character, Set<Character>> getLastVt() {
        return lastVt;
    }

    /**
     * 显示firstVt集合和lastVt集合
     */
    public void ShowFL() {
        System.out.println("firstVt集合如下:");
        for (Map.Entry<Character, Set<Character>> entry : firstVt.entrySet()) {
            System.out.print("firstVt(" + entry.getKey() + "): {");
            int flag = 0;
            for (Character value : entry.getValue()) {
                flag++;
                System.out.print(value);
                if (flag != entry.getValue().size()) {
                    System.out.print(",");
                }
            }
            System.out.println("}");
        }
        System.out.println("------------------------------------------");
        System.out.println("lastVt集合如下:");
        for (Map.Entry<Character, Set<Character>> entry : lastVt.entrySet()) {
            System.out.print("lastVt(" + entry.getKey() + "): {");
            int flag = 0;
            for (Character value : entry.getValue()) {
                flag++;
                System.out.print(value);
                if (flag != entry.getValue().size()) {
                    System.out.print(",");
                }
            }
            System.out.println("}");
        }
    }

    /**
     * 获得firstVt集合
     * @param s 非终结符
     * @param fvt   对应的firstVT集合
     */
    private static void getFirstVT(Character s, Set<Character> fvt) {
        Map<Character, List<String>> map = GSBuilder.gsHelper(gs);
        for(Character vn : GSBuilder.getVN(gs)) {
            if(vn == s){
                List<String> producters = map.get(vn);
                for (int i = 0; i < producters.size(); i++) {
                    String producter = producters.get(i);
                    char ch = producter.charAt(0);
                    if(ch<'A' || ch>'Z'){           //U->a...
                        fvt.add(ch);
                    }
                    if(ch>='A' && ch<='Z'){         //U->Q...
                        if(producter.length()>1 && (producter.charAt(1)<'A'||producter.charAt(1)>'Z')){ //U->Qa...
                            fvt.add(producter.charAt(1));
                        }
                        if(ch == vn){
                            continue;
                        }
                        getFirstVT(ch, fvt);
                    }
                }
            }
        }

    }

    /**
     * 获得lastVt集合
     */
    private static void getLastVT(Character s, Set<Character> lvt) {
        Map<Character, List<String>> map = GSBuilder.gsHelper(gs);
        for(Character vn : GSBuilder.getVN(gs)) {
            if (vn == s) {
                List<String> producters = map.get(vn);
                for (int i = 0; i < producters.size(); i++) {
                    String producter = producters.get(i);
                    int index = producter.length()-1;
                    char ch = producter.charAt(index);
                    if(ch<'A' || ch>'Z'){           //U->...a
                        lvt.add(ch);
                    }
                    if(ch>='A' && ch<='Z'){         //U->...Q
                        if(producter.length()>1 && (producter.charAt(index-1)<'A'||producter.charAt(index-1)>'Z')){ //U->...aQ
                            lvt.add(producter.charAt(index-1));
                        }
                        if(ch == vn){
                            continue;
                        }
                        getLastVT(ch, lvt);
                    }
                }
            }
        }
    }
}

5.3 PriorityTable 算符优先表类

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
public class PriorityTable {
    // 成员变量为一个Table，下面的方法都是对该表的操作
    private Map<Character, Map<Character, Character>> table = new HashMap<>();
    private static Set<Producter> gs;
    /**
     *
     * @param gs            规则集合
     * @param start         文法的开始状态
     * @param firstVt       firstVT集
     * @param lastVt        lastVT集
     * @return
     */
    public PriorityTable(
            Set<Producter> producterSet,
            char start,
            Map<Character, Set<Character>> firstVt,
            Map<Character, Set<Character>> lastVt) {
        gs = producterSet;
        Map<Character, List<String>> map = GSBuilder.gsHelper(gs);
        for(Character vn : GSBuilder.getVN(gs)) {
            List<String> producters = map.get(vn);
            for (int i = 0; i < producters.size(); i++) {
                String producter = producters.get(i);
                for (int j = 0; j < producter.length(); j++) {
                    char ch = producter.charAt(j);
                    if(ch<'A'||ch>'Z'){
                        if(j+1 < producter.length()){
                            char next = producter.charAt(j+1);
                            if(next>='A' && next<='Z'){                             //...aU...
                                Set<Character> set = firstVt.get(next);
                                Map<Character,Character> tmp = table.containsKey(ch) ? table.get(ch) : new HashMap<>();
                                for(Character c : set){
                                    tmp.put(c, '<');
                                }
                                table.put(ch, tmp);
                                if(j+2 < producter.length()) {
                                    char nnext = producter.charAt(j + 2);
                                    if (nnext <'A' || nnext > 'Z') {             //...aUb...
                                        tmp = table.containsKey(ch) ? table.get(ch) : new HashMap<>();
                                        tmp.put(nnext, '=');
                                        table.put(ch, tmp);
                                    }
                                }
                            }else{                                                  //...ab...
                                Map<Character,Character> tmp = table.containsKey(ch) ? table.get(ch) : new HashMap<>();
                                tmp.put(next, '=');
                                table.put(ch, tmp);
                            }
                        }
                    }else {
                        if (j+1 < producter.length()) {
                            char next = producter.charAt(j + 1);
                            if(next < 'A' || next > 'Z'){                           //...Ub...
                                Set<Character> set = lastVt.get(ch);
                                for(Character c : set){
                                    if (table.containsKey(c)) {
                                        table.get(c).put(next, '>');
                                    } else {
                                        Map<Character,Character> tmp = new HashMap<>();
                                        tmp.put(next, '>');
                                        table.put(c, tmp);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        Set<Character> set = firstVt.get(start);
        Map<Character,Character> tmp = new HashMap<>();
        for(Character c : set){
            tmp.put(c, '<');
        }
        table.put('#', tmp);

        set = lastVt.get(start);
        for(Character c : set){
            if (table.containsKey(c)) {
                table.get(c).put('#', '>');
            } else {
                tmp = new HashMap<>();
                tmp.put('#', '>');
                table.put(c, tmp);
            }
        }

        tmp = table.containsKey('#') ? table.get('#') : new HashMap<>();
        tmp.put('#', '=');
        table.put('#',tmp);
    }

    public void show(){
        Set<Character> vt = getVT(gs);
        vt.add('#');
        int control = 0;
        for (Character value : vt) {    //第一行打印终结符
            if (control == 0) {
                System.out.print("\t");
            }
            control++;
            System.out.print(value);
            if (control != vt.size()) {
                System.out.print("\t");
            }
        }
        System.out.println();
        for (Character value : vt) {
            System.out.print(value);
            for (Character value1 : vt) {
                Character ch = table.get(value).get(value1);
                if (ch != null) {
                    System.out.print("\t" + ch);
                } else {
                    System.out.print("\t" + " ");
                }
            }
            System.out.println();
        }
    }

    // findTable查表
    public char findTable(Character vt_row, Character vt_col){
        if(table.get(vt_row) != null && table.get(vt_row).get(vt_col) != null){
            return table.get(vt_row).get(vt_col);
        }else{
            return '?';
        }
    }
}

5. 4、Analysis工具类，用于分析一个句子是否符合算符优先文法，并给出识别过程

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
public class Analysis {
    private Set<Producter> gs;
    private Set<Character> vt;

    public Analysis(Set<Producter> producters) {
        gs = producters;
        vt = GSBuilder.getVT(gs);
        vt.add('#');
    }

    /**
     * 算符优先分析过程
     * 使用一个符号栈，用它寄存终结符和非终结符,k代表符号栈的深度
     * 在正常情况下，算法工作完毕时，符号栈S应呈现:#N
     */
    public void analysis(String sentence) {
        sentence = preDeal(sentence);
        System.out.println("预处理后的字符串："+sentence);
        System.out.println("------------------分析过程如下--------------------");
        PriorityTable pt = new PriorityTable(gs, 'E', new F_L(gs).getFirstVt(), new F_L(gs).getLastVt());
        int count = 0;
        int k = 0;
        int j = 0;
        int step = 0;
        String gui = null;
        sentence += '#';        //要识别的句子以#结束
        List<Character> listStack = new ArrayList<>();  //用一个List来模拟栈
        System.out.printf("%-8s%-20s%-8s%-10s%-8s\n", "步骤", "栈", "读入", "剩余串", "操作");
        listStack.add('#');     //将#压入栈
        char a = sentence.charAt(step++);
        do {
            if (count != 0) {
                System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", "移进", count, listToString(listStack), a, sentence.substring(step));
            } else {
                System.out.printf("%-8d %-20s %-8c %-10s", count, listToString(listStack), a, sentence.substring(step));
            }
            char ch = listStack.get(k);
            if (isVt(ch)) {
                j = k;
            } else if (j >= 1) {
                j = k - 1;
            }
            char temp = 0;
            while (pt.findTable(listStack.get(j),a) == '>') {
                if (listStack.size() == 2 && a == '#') {
                    break;
                }
                StringBuilder judge = new StringBuilder();
                do {
                    temp = listStack.get(j);
                    if (isVt(listStack.get(j - 1))) {
                        j = j - 1;
                    } else {
                        j = j - 2;
                    }
                } while (pt.findTable(listStack.get(j),temp) != '<');
                for (int i = j + 1; i < listStack.size(); i++) {
                    judge.append(listStack.get(i));
                }
                int c = judge.length();
                while(c > 0){
                    c--;
                    listStack.remove(j+1);
                }
                char res = retLeft(judge.toString());
                count++;
                k = j + 1;
                listStack.add(res);
                gui = "用" + res + "->" + judge.toString() + "规约";
                System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", gui, count, listToString(listStack), a, sentence.substring(step));
            }
            char sym = pt.findTable(listStack.get(j), a);
            if (sym=='<' || sym=='=') {
                count++;
                k++;
                listStack.add(a);
            }else {
                System.out.println("算符优先分析法推导失败，请检查输入表达式！");
                return;
            }
            if (listStack.size() == 2 && a == '#') {
                break;
            }
            if (step < sentence.length()) {
                a = sentence.charAt(step++);
            } else {
                break;
            }
        } while (!(listStack.size() == 2 && a == '#'));
        System.out.printf("%-8s\n", "算符优先分析法推导成功！");
    }

    /**
     * 句子进行预处理，将其中的实数转为 i
     * @param sentence 待检查的句子
     * @return
     */
    private String preDeal(String sentence) {
        char[] expToChar = sentence.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < expToChar.length; i++) {
            char ch = expToChar[i];
            if(!isDigit(ch)){
                sb.append(ch);
            }else {
                while(i+1 < expToChar.length && isDigit(expToChar[i+1])){
                    i++;
                }
                sb.append('i');
            }
        }
        return sb.toString();
    }
    private static boolean isDigit(char ch){
        return (ch >= '0' && ch <= '9') || ch == '.';
    }

    private char retLeft(String right) {
        for(Producter p : gs){
            String str = p.getRight();
            if(str.length() != right.length()){
                continue;
            }
            int i = 0;
            for (; i < str.length(); i++) {
                char ch1 = str.charAt(i);
                char ch2 = right.charAt(i);
                if(ch1<'A' || ch1>'Z'){
                    if(ch1 != ch2){
                        break;
                    }
                }else {
                    if(!(ch2>='A' && ch2<='Z')){
                        break;
                    }
                }
            }
            if(i == str.length()){
                return p.getLeft();
            }
        }
        return '?';
    }

    private boolean isVt(char ch) {
        for (Character value : vt) {
            if (value.equals(ch)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 将字符数组转换成字符串，用于输出打印
     * @param list
     * @return
     */
    public static String listToString(List<Character> list) {
        StringBuffer sb = new StringBuffer();
        for (Character value : list) {
            if (value != ',' && value != '[' && value != ']') {
                sb.append(value);
            }
        }
        return sb.toString();
    }
}

5.5 Calculator计算类，用于计算输入表达式的值

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
public class Calculator {
    private static int index = 0;
    private static Stack<Float> numStack = new Stack<>();
    private static Stack<Character> operStack = new Stack<>();
    private PriorityTable pt;
    private static String expression;

    public Calculator(PriorityTable priorityTable, String express) {
        pt = priorityTable;
        expression = express+'#';
    }

    /**
     * @return 表达式的值
     */
    public float calculate(){
        // 新建两个栈，一个存储数据，一个存储操作符
        operStack.push('#');
        char[] expToChar = expression.toCharArray();
        char ch;
        while(!operStack.isEmpty()){
            ch = expToChar[index];
            if(isDigit(ch)){
                readNum();  //读取一个实数入栈
            } else {
                char pre_op = operStack.peek();
                switch (pt.findTable(pre_op,ch)) {
                    case '<':
                        operStack.push(ch);
                        index++;
                        break;
                    case '=':
                        operStack.pop();
                        index++;
                        break;
                    case '>':
                        float a = numStack.pop();
                        float b = numStack.pop();
                        pre_op = operStack.pop();
                        numStack.push(operate(a, pre_op, b));
                        break;
                }
            }
        }
        return numStack.peek();
    }

    private static boolean isDigit(char ch){
        if(ch >= '0' && ch <= '9'){
            return true;
        }else {
            return false;
        }
    }

    /**
     * 从表达式中读取实数并入操作数栈
     */
    private static void readNum() {
        char[] expressToChar = expression.toCharArray();    //将原表达式转化为char数组
        numStack.push((float) expressToChar[index] - '0');
        index++;
        while (isDigit(expressToChar[index])) {
            numStack.push(numStack.pop() * 10 + (float) expressToChar[index] - '0');
            index++;
        }
        if ('.' == (expressToChar[index])) {
            index++;
            float cost = 1;
            while (isDigit(expressToChar[index])) {
                numStack.push(numStack.pop() + (float) (expressToChar[index] - '0') * (cost /= 10));
                index++;
            }
        }
    }

    private static float operate(float f1, char pre_op, float f2) {
        switch(pre_op) {
            case '+':
                return f1+f2;
            case '-':
                return f2-f1;
            case '*':
                return f2*f1;
            case '/':
                return f2/f1;
            case '^':
                return (float) Math.pow(f2, f1);
            default:
                throw new RuntimeException("输入错误");
        }
    }
}

5.6 GSBuilder工具类，用于接收输入的文法

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
public class GSBuilder {
    // 接受输入，返回GS文法，即产生式的集合：Set<Producter>
    public static Set<Producter> build() throws IOException {
        Set<Producter> gs = new HashSet<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";

        while (!(line = br.readLine().trim()).equals("end")){
            gs.add(new Producter(line));
        }
        return gs;
    }
    // 根据文法GS，获取所有的非终结符集
    public static Set<Character> getVN(Set<Producter> gs){
        Set<Character> vn = new HashSet<>();
        for(Producter producter : gs){
            vn.add(producter.getLeft());
        }
        return vn;
    }

    // 将文法GS转换成Map<非终结符, 对应规则的集合>
    public static Map<Character, List<String>> gsHelper(Set<Producter> gs){
        Map<Character, List<String>> map = new HashMap<>();
        for(Producter producter : gs){
            Character c = producter.getLeft();
            String s = producter.getRight();
            if(!map.containsKey(c)){
                List<String> list = new ArrayList<>();
                map.put(c, list);
            }
            map.get(c).add(s);
        }
        return map;
    }

    // 根据文法GS，获取所有的终结符集
    public static Set<Character> getVT(Set<Producter> gs){
        Set<Character> vt = new HashSet<>();
        for(Producter producter : gs){
            for(Character c : producter.getRight().toCharArray()){
                if(c<'A' || c>'Z'){
                    vt.add(c);
                }
            }
        }
        return vt;
    }
}

5.7 Main主函数测试类

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
public class Main {
    public static void main(String[] args) throws IOException {
        System.out.println("==========================================");

        System.out.println("请输入文法GS（一行一行的输入生成式，end表示结束）：");
        Set<Producter> gs = GSBuilder.build();

        System.out.println("------------------------------------------");
        System.out.print("是否是算符优先文法？");
        for (Producter p : gs) {
            if(!p.isOperPrior()){
                System.out.println("\t不是，请重新输入文法");
                return;
            }
        }
        System.out.println("\t是");

        System.out.println("------------------------------------------");
        new F_L(gs).ShowFL();

        System.out.println("------------------------------------------");
        System.out.println("构造的算符优先关系表如下：");
        PriorityTable pt = new PriorityTable(gs, 'E', new F_L(gs).getFirstVt(), new F_L(gs).getLastVt());
        pt.show();
        System.out.println("==========================================");
        System.out.println("请输入要检查的串：");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String sentence = br.readLine();
        new Analysis(gs).analysis(sentence);
        System.out.println("------------------计算表达式的值--------------------");
        System.out.println(new Calculator(pt, sentence).calculate());
    }
}
/*
Test Example:
E->E+T
E->T
T->T*F
T->F
F->i
F->(E)
end
 */

6、运行效果

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
==========================================
请输入文法GS（一行一行的输入生成式，end表示结束）：
E->E+T
E->T
T->T*F
T->F
F->i
F->(E)
end
------------------------------------------
是否是算符优先文法？	是
------------------------------------------
firstVt集合如下:
firstVt(T): {(,i,*}
firstVt(E): {(,i,*,+}
firstVt(F): {(,i}
------------------------------------------
lastVt集合如下:
lastVt(T): {),i,*}
lastVt(E): {),i,*,+}
lastVt(F): {),i}
------------------------------------------
构造的算符优先关系表如下：
	#	(	)	i	*	+
#	=	<	 	<	<	<
(	 	<	=	<	<	<
)	>	 	>	 	>	>
i	>	 	>	 	>	>
*	>	<	>	<	>	>
+	>	<	>	<	<	>
==========================================
请输入要检查的串：
1.23*(7+3)
预处理后的字符串：i*(i+i)
------------------分析过程如下--------------------
步骤      栈                   读入      剩余串       操作      
0        #                    i        *(i+i)#   移进      
1        #i                   *        (i+i)#    用F->i规约 
2        #F                   *        (i+i)#    移进      
3        #F*                  (        i+i)#     移进      
4        #F*(                 i        +i)#      移进      
5        #F*(i                +        i)#       用F->i规约 
6        #F*(F                +        i)#       移进      
7        #F*(F+               i        )#        移进      
8        #F*(F+i              )        #         用F->i规约 
9        #F*(F+F              )        #         用E->F+F规约
10       #F*(E                )        #         移进      
11       #F*(E)               #                  用F->(E)规约
12       #F*F                 #                  用T->F*F规约
13       #T                   #                  算符优先分析法推导成功！
------------------计算表达式的值--------------------
12.3
-------------本文结束感谢您的阅读-------------