一、课程设计内容
1.1、前置条件：有效文法及正确的算符优先表
1.2、功能需求：根据文法及算符优先表，实现算符优先分析过程，输入串采用教材133页习题2中（2）中的字符串（#(((a,a),x,(a)),a)#）。
1.3、开发环境： Java(jdk1.8)
Windows 10
二、数据结构设计
2.1、类
2.1.1、文法对象类
public class Grammar {
private String left;
private String right;
public Grammar(String l, String r) {
this.left = l;
this.right = r;
}
public String getLeft() {
return left;
}
public String getRight() {
return right;
}
}
2.1.2、文法集合对象
public class GrammarList {
private List<Grammar> list = new ArrayList<>();
private List<String> leftList = new ArrayList<>();
private List<String> rightList = new ArrayList<>();
public void addGrammar(Grammar grammar) {
leftList.add(grammar.getLeft());
rightList.add(grammar.getRight());
list.add(new Grammar(grammar.getLeft(), grammar.getRight()));
}
public List<Grammar> getGrammarList() {
return list;
}
public List<String> getLeftList() {
return leftList;
}
public List<String> getRightList() {
return rightList;
}
}
2.2、全局变量
2.2.1、当前操作符
String signTemp
2.2.2、符号栈
Stack<String> signStack
2.2.3、字符串栈
Stack<String> opStack
2.2.4、分析步骤计数
int num
三、程序总体设计
public class Main {
public static void main(String[] args) {
Priority[][] matrix = MakeMatrix.getMatrix();
Map<String, Integer> keyMap = MakeMatrix.getKeyMap();
// 1、输入字符串
String str = "#(((a,a),x,(a)),a)#"; // ^ 用x代替
String[] strings = str.split("");
// 2、创建文法
Grammar grammar0 = new Grammar("S", "a");
Grammar grammar1 = new Grammar("S", "x");
Grammar grammar2 = new Grammar("S", "(R)");
Grammar grammar3 = new Grammar("T", "S,T");
Grammar grammar4 = new Grammar("T", "S");
Grammar grammar5 = new Grammar("R", "T");
// 3、添加文法
GrammarList list = new GrammarList();
list.addGrammar(grammar0);
list.addGrammar(grammar1);
list.addGrammar(grammar2);
list.addGrammar(grammar3);
list.addGrammar(grammar4);
list.addGrammar(grammar5);
// 4、算符优先分析
Analyse runner = new Analyse();
runner.analyse(list, matrix, keyMap, strings);
}
}
四、详细设计
4.1、向文法集合中添加文法
public void addGrammar(Grammar grammar)
4.2、获取文法集合
public List<Grammar> getGrammarList()
4.3、获取算符优先矩阵
public static Priority[][] getMatrix()
4.4、获取终结符对应行列
public static Map<String, Integer> getKeyMap()
4.5、进行算符优先分析
GrammarList list 文法集合
Priority[][] matrix 算符优先矩阵
Map<String, Integer> keyMap 终结符行列号
String[] strings 输入串
public void analyse(GrammarList list, Priority[][] matrix, Map<String, Integer> keyMap, String[] strings)
4.6、规约函数
String now 规约串
private boolean gy(String now, GrammarList list)
4.7、打印信息
Stack<String> opStack 字符串栈
String signTemp 符号栈顶元素
int index 分析步骤序号
String action 分析动作(移进/归约)
private void outputProcess(Stack<String> opStack, String signTemp, String[] strings, int index, String action)
4.8、流程图
五、测试数据设计
输入串：#(((a,a),x,(a)),a)#
六、程序输出结果分析
七、设计重点难点分析
八、参考文献
九、附录
9.1、Main.class
import analysestring.Analyse;
import enums.Priority;
import grammar.Grammar;
import grammar.GrammarList;
import makematrix.MakeMatrix;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Priority[][] matrix = MakeMatrix.getMatrix();
Map<String, Integer> keyMap = MakeMatrix.getKeyMap();
String str = "#(((a,a),x,(a)),a)#"; // ^ 用x代替
String[] strings = str.split("");
Grammar grammar0 = new Grammar("S", "a");
Grammar grammar1 = new Grammar("S", "x");
Grammar grammar2 = new Grammar("S", "(R)");
Grammar grammar3 = new Grammar("T", "S,T");
Grammar grammar4 = new Grammar("T", "S");
Grammar grammar5 = new Grammar("R", "T");
GrammarList list = new GrammarList();
list.addGrammar(grammar0);
list.addGrammar(grammar1);
list.addGrammar(grammar2);
list.addGrammar(grammar3);
list.addGrammar(grammar4);
list.addGrammar(grammar5);
Analyse runner = new Analyse();
runner.analyse(list, matrix, keyMap, strings);
}
}
9.2、Grammar.class
public class Grammar {
private String left;
private String right;
public Grammar(String l, String r) {
this.left = l;
this.right = r;
}
public String getLeft() {
return left;
}
public String getRight() {
return right;
}
}
9.3、GrammarList.class
import java.util.ArrayList;
import java.util.List;
public class GrammarList {
private List<Grammar> list = new ArrayList<>();
private List<String> leftList = new ArrayList<>();
private List<String> rightList = new ArrayList<>();
public void addGrammar(Grammar grammar) {
leftList.add(grammar.getLeft());
rightList.add(grammar.getRight());
list.add(new Grammar(grammar.getLeft(), grammar.getRight()));
}
public List<Grammar> getGrammarList() {
return list;
}
public List<String> getLeftList() {
return leftList;
}
public List<String> getRightList() {
return rightList;
}
}
9.4、Priority.class
public enum Priority {
NULL(0, "无关系"),
SMALL(1, "小于"),
EQUAL(2, "等于"),
BIG(3, "大于");
private int state;
private String stateInfo;
private Priority(int state, String stateInfo) {
this.state = state;
this.stateInfo = stateInfo;
}
public int getState() {
return this.state;
}
public String getStateInfo() {
return this.stateInfo;
}
}
9.5、MakeMatrix.class
import enums.Priority;
import java.util.HashMap;
import java.util.Map;
public class MakeMatrix {
private static Map<String, Integer> key = new HashMap<>();
static {
key.put("a", 0);
key.put("x", 1);
key.put("(", 2);
key.put(")", 3);
key.put(",", 4);
key.put("#", 5);
}
private static Priority[][] operationMatrix = {
{Priority.NULL, Priority.NULL, Priority.NULL, Priority.BIG, Priority.BIG, Priority.BIG},
{Priority.NULL, Priority.NULL, Priority.NULL, Priority.BIG, Priority.BIG, Priority.BIG},
{Priority.SMALL, Priority.SMALL, Priority.SMALL, Priority.EQUAL, Priority.SMALL, Priority.NULL},
{Priority.NULL, Priority.NULL, Priority.NULL, Priority.BIG, Priority.BIG, Priority.BIG},
{Priority.SMALL, Priority.SMALL, Priority.SMALL, Priority.BIG, Priority.SMALL, Priority.NULL},
{Priority.SMALL, Priority.SMALL, Priority.SMALL, Priority.NULL, Priority.NULL, Priority.NULL}};
public static Priority[][] getMatrix() {
return operationMatrix;
}
public static Map<String, Integer> getKeyMap() {
return key;
}
}
9.6、Analyse.class
import enums.Priority;
import grammar.Grammar;
import grammar.GrammarList;
import java.util.List;
import java.util.Map;
import java.util.Stack;
public class Analyse {
private String signTemp = new String("");
private Stack<String> signStack = new Stack<>();
private Stack<String> opStack = new Stack<>();
private int num = 0;
public void analyse(GrammarList list, Priority[][] matrix, Map<String, Integer> keyMap, String[] strings) {
for (int i = 0; i < strings.length; i++) {
if (i == 0) {
opStack.push(strings[i]);
signStack.push(strings[i]);
signTemp = strings[i];
outputProcess(opStack, signTemp, strings, i + 1, "开始");
continue;
}
if (strings[i].equals(strings[0])) {
outputProcess(opStack, signTemp, strings, i, "结束");
System.out.println("程序结束");
break;
}
int v1 = keyMap.get(signTemp);
int v2 = keyMap.get(strings[i]);
if (matrix[v1][v2].equals(Priority.BIG)) { // 大于 则规约
String now = opStack.peek(); // 取出单字符大小的字符串
if (signStack.peek().equals(",")) {
if (now.equals("S")) {
// 用 T -> S 规约
outputProcess(opStack, signTemp, strings, i, "归约");
if (!gy(now, list)) {
break;
}
i--;
continue;
}
if (now.equals("T")) {
// 用T -> S,T 规约
outputProcess(opStack, signTemp, strings, i, "归约");
StringBuilder sb = new StringBuilder();
sb.append(opStack.pop());
sb.append(opStack.pop());
sb.append(opStack.peek());
if (!gy(new String(sb.reverse()), list)) {
break;
}
i--;
continue;
}
}
if (now.equals("T")) {
if (signTemp.equals("(")) {
outputProcess(opStack, signTemp, strings, i, "归约");
if (!gy(now, list)) {
break;
}
i--;
continue;
}
}
outputProcess(opStack, signTemp, strings, i, "归约");
if (!gy(now, list)) {
break;
}
i--;
} else if (matrix[v1][v2].equals(Priority.SMALL)) { // 小于 则移进
outputProcess(opStack, signTemp, strings, i, "移进");
opStack.push(strings[i]);
signStack.push(strings[i]);
signTemp = signStack.peek();
} else if (matrix[v1][v2].equals(Priority.EQUAL)) { // 去括号
StringBuilder sb = new StringBuilder();
while (!opStack.peek().equals("R")) {
outputProcess(opStack, signTemp, strings, i, "归约");
gy(opStack.peek(), list);
}
outputProcess(opStack, signTemp, strings, i, "移进");
opStack.push(strings[i]);
signStack.push(strings[i]);
signTemp = signStack.peek();
outputProcess(opStack, signTemp, strings, i + 1, "归约");
signStack.pop();
signTemp = signStack.peek();
sb.append(opStack.pop());
sb.append(opStack.pop());
sb.append(opStack.peek());
if (!gy(new String(sb.reverse()), list)) {
break;
}
continue;
} else { // Priority.NULL 出错
System.out.println("规约出错 Priority.NULL");
break;
}
}
}
private boolean gy(String now, GrammarList list) {
List<Grammar> grammars = list.getGrammarList();
if (list.getRightList().contains(now)) {
for (int j = 0; j < grammars.size(); j++) {
String right = grammars.get(j).getRight();
if (right.equals(now)) {
opStack.pop();
opStack.push(grammars.get(j).getLeft());
if (right.equals("T") || right.equals("S")) { // 当T->S 和R->T时 无关符号
break;
}
signStack.pop();
signTemp = signStack.peek();
break;
}
}
return true;
} else {
System.out.println("规约出错: 找不到规约串");
return false;
}
}
private void outputProcess(Stack<String> opStack, String signTemp, String[] strings, int index, String action) {
if (num == 0) {
System.out.println("步骤 栈 当前符号 剩余符号 动作");
}
StringBuilder sbStack = new StringBuilder();
StringBuilder sbStrs = new StringBuilder();
Stack<String> temp = new Stack<>();
while (!opStack.isEmpty()) {
temp.push(opStack.pop());
}
while (!temp.isEmpty()) {
sbStack.append(temp.peek());
opStack.push(temp.pop());
}
for (int i = index; i < strings.length; i++) {
sbStrs.append(strings[i]);
}
num++;
System.out.printf("%-5d" + " " + "%-20s" + " " + "%-10s" + " " + "%-20s" + " " + action + " ", num, sbStack, signTemp, sbStrs, action);
}
}