[编译原理] 算符优先分析实验报告_算符优先分析表实验心得

1.实验原理

算符优先分析法（Operator Precedence Parsing）是一种用于解析表达式的语法分析方法。它通过确定运算符之间的优先级和结合性来分析和构建表达式的语法树。

算符优先分析法的基本思想是，为每个运算符赋予一个优先级，然后利用这些优先级来确定运算符之间的顺序。在算符优先分析法中，每个运算符都有一个左优先级和一个右优先级，用来指示它在与相邻运算符结合时的优先级。通常，左结合性指示运算符与其左边的运算符结合，右结合性指示运算符与其右边的运算符结合。

算符优先分析法的优点是简单而高效，特别适用于具有相对简单运算符优先级关系的表达式。然而，对于包含复杂优先级规则的表达式，算符优先分析法可能无法适应，需要使用其他更复杂的语法分析方法。

2.设计思想

3.实验算法及流程图

4.实验代码

友情提示: 有bug, 基本能跑, 谨慎CV

OPP.java

import java.util.*;

public class OPP {

    /**
     * 优先级常量
     */
    final int STATE1 = 1; // less than
    final int STATE2 = 2; // same as
    final int STATE3 = 3; // bigger than
    final int ERORR = 4; // error


    /**
     * 栈
     */
    Stack<String> S = new Stack<>();

    /**
     * 语法表
     */
    Map<String, ArrayList<String>> grammarMap = new HashMap<>();

    /**
     * 算符优先表
     */
    Map<String, HashMap<String, Integer>> OPPMap = new HashMap<>();

    Scanner scanner = new Scanner(System.in);

    public OPP(){
        init();
    }

    /**
     * 算符优先分析核心算法
     * @return 句子是否正确
     */
    boolean parse(){
        S.push("#");
        while(true){
            int j;
            String a = loadCharacter(); // 输入串的首字符
            if(isVT(S.peek())){
                j = topIndex(S);
            } else {
                j = topIndex(S)-1;
            }
            if (jdg(S.get(j), a) == ERORR) {
                return false;
            }
            while(jdg(S.get(j), a) == STATE3){
                while (true) {
                    String Q = S.get(j);
                    if(isVT(S.get(j-1))){
                        j = j-1;
                    } else {
                        j = j-2;
                    }
                    if(jdg(S.get(j), Q) == STATE1){
                        break;
                    }
                }
                // 进行归约
                String N = reduce(j+1);
                if(N.equals("@")) return false;
                S.push(N);
            }
            if(jdg(S.get(j), a) == STATE1 || jdg(S.get(j), a) == STATE2){
                S.push(a);
            }
            if(a.equals("#")){
                break;
            }
        }
        return true;
    }

    /**
     * 一些初始化工作
     */
    private void init() {
        // 初始文法的构建
        grammarMap.put("A", new ArrayList<>());
        grammarMap.get("A").add("A+B");
        grammarMap.get("A").add("B");
        grammarMap.get("A").add("C+C");
        grammarMap.get("A").add("C*C");
        grammarMap.put("B", new ArrayList<>());
        grammarMap.get("B").add("B*C");
        grammarMap.get("B").add("C");
        grammarMap.put("C", new ArrayList<>());
        grammarMap.get("C").add("i");
        grammarMap.get("C").add("n");
        grammarMap.get("C").add("(A)");
        grammarMap.put("D", new ArrayList<>());
        grammarMap.get("D").add("+");
        grammarMap.get("D").add("-");
        grammarMap.put("D", new ArrayList<>());
        grammarMap.get("D").add("*");
        grammarMap.get("D").add("/");

        // 算符优先表构建
        OPPMap.put("+", new HashMap<>());
        OPPMap.get("+").put("+",3);
        OPPMap.get("+").put("*",1);
        OPPMap.get("+").put("i",1);
        OPPMap.get("+").put("(",1);
        OPPMap.get("+").put(")",3);
        OPPMap.get("+").put("#",3);

        OPPMap.put("*", new HashMap<>());
        OPPMap.get("*").put("+",3);
        OPPMap.get("*").put("*",3);
        OPPMap.get("*").put("i",1);
        OPPMap.get("*").put("(",1);
        OPPMap.get("*").put(")",3);
        OPPMap.get("*").put("#",3);

        OPPMap.put("i", new HashMap<>());
        OPPMap.get("i").put("+",3);
        OPPMap.get("i").put("*",3);
//        OPPMap.get("i").put("i",1);
//        OPPMap.get("i").put("(",1);
        OPPMap.get("i").put(")",3);
        OPPMap.get("i").put("#",3);

        OPPMap.put("(", new HashMap<>());
        OPPMap.get("(").put("+",1);
        OPPMap.get("(").put("*",1);
        OPPMap.get("(").put("i",1);
        OPPMap.get("(").put("(",1);
        OPPMap.get("(").put(")",2);
//        OPPMap.get("(").put("#",3);

        OPPMap.put(")", new HashMap<>());
        OPPMap.get(")").put("+",3);
        OPPMap.get(")").put("*",3);
//        OPPMap.get(")").put("i",1);
//        OPPMap.get(")").put("(",1);
        OPPMap.get(")").put(")",3);
        OPPMap.get(")").put("#",3);

        OPPMap.put("#", new HashMap<>());
        OPPMap.get("#").put("+",1);
        OPPMap.get("#").put("*",1);
        OPPMap.get("#").put("i",1);
        OPPMap.get("#").put("(",1);
//        OPPMap.get("#").put(")",2);
        OPPMap.get("#").put("#",2);
    }

    private int cnt = 0;
    /**
     * 读一个字符
     * @return 当前字符
     */
    private String loadCharacter() {
        //if (scanner.hasNext()) {
        cnt ++;
        if (cnt != 8) {
            String binarySet = scanner.next();
            StringBuilder word = new StringBuilder();
            for ( int i = 1; binarySet.charAt(i)!=','; i++){
                word.append(binarySet.charAt(i));
            }
            String description = String.valueOf(word);
            if(description.equals("plus")) return "+";
            if(description.equals("minus")) return "-";
            if(description.equals("times")) return "*";
            if(description.equals("slash")) return "/";
            if(description.equals("number")) return "n";
            if(description.equals("ident")) return "i";
            if(description.equals("lparen")) return "(";
            if(description.equals("rparen")) return ")";
            throw new RuntimeException("unknown character");
        } else {
            return "#";
        }
    }

    /**
     * 寻找归约语句
     * @param l 从栈顶字符到下标为l的字符进行归约
     * @return 归约结果
     */
    private String reduce(int l){
        // 从栈中获取待归约字符串
        StringBuilder stringBuilder = new StringBuilder();
        int stackSize = topIndex(S);
        for( int i = l; i<=stackSize; i++){ // todo:这里真的是这样吗
            stringBuilder.append(S.get(i));
        }
        // 先把字符串提出来在把它从栈中删除
        for ( int i = l; i<=stackSize; i++){
            S.pop();
        }
        String str = stringBuilder.toString();
        // 遍历语法表找到可归约的串
        for (Map.Entry<String, ArrayList<String>> entry : grammarMap.entrySet()){
            if (entry.getValue().contains(str)) {
                return entry.getKey();
            }
        }
        return "@";
    }

    /**
     * 比较两个算符的优先级
     * @param a
     * @param b
     * @return 比较结果
     */
    private int jdg(String a, String b){
        a = simplify(a);
        b = simplify(b);
        if(OPPMap.get(a).get(b) == null){
            return ERORR;
        } else {
            return OPPMap.get(a).get(b);
        }
    }

    private String simplify(String a) {
        String temp = "";
        switch(a){
            case "-": temp = "+";break;
            case "/": temp = "*";break;
            case "n": temp = "i";break;
            default: temp = a;
        }
        return temp;
    }

    /**
     * 返回栈顶索引
     * @param s
     * @return 栈顶索引
     */
    private int topIndex(Stack<String> s) {
        return s.size()-1;
    }

    /**
     * 判断是否是非终结符
     * @param s
     * @return 结果
     */
    private boolean isVT(String s) {
        return !(s.charAt(0) >= 'A' && s.charAt(0) <= 'Z');
    }
}
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

OPPDemo.java

public class OPPDemo {
    public static void main(String[] args){
        OPP opp = new OPP();
        if(opp.parse()){
            System.out.println("Yes,it is correct.");
        } else {
            System.out.println("No,it is wrong.");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

5.实验结果与分析

输入:
(lparen,()
(ident,a)
(plus,+)
(number,15)
(rparen,))
(times,*)
(ident,b)
预计输出:
Yes,it is correct.
实际输出:

输入:
(lparen,()
(ident,a)
(plus,+)
(number,15)
(rparen,))
(plus,+)
(times,*)
(ident,b)
预计输出:
No,it is wrong.
实际输出: