实验二 简单计算器的设计与实现
实验二 简单计算器的设计与实现
一、实验目的
综合运行词法分析器、语法分析器等原理实现一个具有加、乘功能的简单计算器，该计算器满足乘法优先级高于加法优先级，且仅处理非负整数。
二、实验内容
1. 对输入的符号串首先进行词法分析，提取操作数及操作符，以输出的单词符号为输入进行语法分析。
2. 要求以算符优先分析的方法完成语法分析工作，识别输入串是否是文法描述语言的句子。
3. 对句子进行求值，求值方式可以是遍历语法树或者是建立一个逆波兰式，对逆波兰式进行求值。
三、实验要求
1. 从文件读入算术表达式/或者从终端输入；
2. 词法分析，用二元组表示输出结果；
3. 语法分析，算符优先分析方法进行自下而上的语法分析并构造语法树；
4. 识别出的句子进行求值，遍历语法树求值或者先建立逆波兰式再求值；
四、输出
P -> (E) | i
T -> T*F | F
E -> E+T | T
F -> P↑F | P
非终结符: P T E F
终结符: ( ) i * + ↑
firstVt(E) : + , * , ↑ , ( , i
firstVt(T) : * , ↑ , ( , i
firstVt(F) : ↑ , ( , i
firstVt(P) : ( , i
lastVt(E) : + , * , ↑ , ) , i
lastVt(T) : * , ↑ , ) , i
lastVt(F) : ↑ , ) , i
lastVt(P) : ) , i
优先关系表:
- ( ) i * + ↑ #
( < = < < < < -
) - > - > > > >
i - > - > > > >
* < > < > > < >
+ < > < < > < >
↑ < > < > > < >
# < - < < < < =
常量 : 6
界符 : (
运算符 : *
常量 : 5
运算符 : +
常量 : 4
界符 : )
带判断的产生式: i*(i+i)
规约串为: i
归约到: P
规约串为: i
归约到: P
规约串为: i
归约到: P
规约串为: P+P
归约到: P
规约串为: (P)
归约到: P
规约串为: P*P
归约到: P
恭喜你，该文法是算符优先文法
语法树：
i -> P
i -> P
i -> P
P+P -> P
(P) -> P
P*P -> P
表达式的值为： 54
下面是构造形象语法树：
是否进行手动构建 >
五、代码 (使用Maven，因为用到了Lombok依赖)
词法分析器代码链接：词法分析器
下面是算符优先分析法代码
目前实现计算FirstVt和LastVt集合, 构造优先关系表, 规约过程，简单语法树
代码中有手动构建语法树，如果选择自动构建，输入n 或者 N即可
package main.experiment2;
import lombok.Getter;
import main.experiment1.Pair;
import main.experiment1.WordAnalysis;
import java.util.*;
import java.util.function.BiFunction;
import java.util.stream.Collectors;
/**
* @author Diminish
* @version 1.0
* @since 17
*/
@Getter
public class Grammar {
/**
* firstVt 集合
* Key : 非终结符
* Value : 集合内容
* */
private final Map<String, List<String>> firstTerminators = new TreeMap<>();
/**
* lastVt 集合
* Key : 非终结符
* Value : 集合内容
* */
private final Map<String, List<String>> lastTerminators = new TreeMap<>();
/**
* 非终结符集合
* */
private List<String> nonTerminators = new ArrayList<>();
/**
* 终结符集合
* */
private List<String> terminators = new ArrayList<>();
/**
* <p>语法</p>
* */
private final Map<String, List<String>> grammar = new HashMap<>();
/**
* 语法开始符号
* */
private String startTerminator = null;
/**
* 优先关系表
* */
private String[][] precedenceRelationList;
/**
* 语法树
* */
private Node root;
/**
* <p>默认语法：</p>
* <p>A -> A+B | B</p>
* <p>B -> B*C | C</p>
* <p>C -> i</p>
* */
Grammar () {
grammar.put("A", List.of("A+B", "B"));
grammar.put("B", List.of("C*C", "C"));
grammar.put("C", List.of("i"));
startTerminator = "A";
initializeGrammar();
}
/**
* <p>构造指定语法</p>
* @param start 每个句型的开始符号
* @param generateExpression 每个开始符号对应的表达式
* */
Grammar (List<String> start, List<List<String>> generateExpression) {
for (int i = 0; i < start.size(); i++) {
grammar.put(start.get(i), generateExpression.get(i));
if (startTerminator == null) {
startTerminator = start.get(i);
}
}
initializeGrammar();
}
/**
* 构造终结符 非终结符 firstVt lastVt集合
* */
private void initializeGrammar () {
constructNonTerminator(this);
constructTerminator(this);
constructFirstTerminator();
constructLastTerminator();
initializePrecedenceRelationList();
constructPrecedenceRelationList();
}
/**
* 打印输出语法
* */
public void showGrammar () {
for (var i : grammar.entrySet()) {
System.out.print(i.getKey() + " -> ");
for (var v = 0 ; v < i.getValue().size(); v++) {
if (v + 1 == i.getValue().size()) {
System.out.println(i.getValue().get(v));
} else {
System.out.print(i.getValue().get(v) + " | ");
}
}
}
}
/**
* 打印输出非终结符
* */
public void showNonTerminator () {
System.out.print("非终结符: ");
for (var v : nonTerminators) {
System.out.print(v + " ");
}
System.out.println();
}
/**
* 打印输出终结符
* */
public void showTerminator () {
System.out.print("终结符: ");
for (var v : terminators) {
System.out.print(v + " ");
}
System.out.println();
}
/**
* 打印输出 firstVt集合
* */
public void showFirstTerminators () {
var entryArrayList = sort(firstTerminators);
for (var firstTerminator : entryArrayList) {
System.out.print("firstVt(" + firstTerminator.getKey() + ")" + " : ");
show(firstTerminator);
}
}
/**
* 打印输出 lastVt集合
* */
public void showLastTerminators () {
var entryArrayList = sort(lastTerminators);
for (var lastTerminator : entryArrayList) {
System.out.print("lastVt(" + lastTerminator.getKey() + ")" + " : ");
show(lastTerminator);
}
}
private void show (Map.Entry<String, List<String>> lastTerminator) {
int length = lastTerminator.getValue().size();
for (int i = 0; i < length; i++) {
if (i + 1 >= length) {
System.out.print(lastTerminator.getValue().get(i));
} else {
System.out.print(lastTerminator.getValue().get(i) + " , ");
}
}
System.out.println();
}
/**
* 打印优先关系表
* */
public void showPrecedenceRelationList () {
System.out.println("优先关系表:");
for (String[] strings : precedenceRelationList) {
for (int column = 0; column < precedenceRelationList.length; column++) {
if (strings[column] == null) {
System.out.print("- ");
} else {
System.out.print(strings[column] + " ");
}
}
System.out.println();
}
System.out.println("\n");
}
/**
* 初始化优先关系表
* */
private void initializePrecedenceRelationList () {
// 创建新的终结符集合, 加入 #
var terminatorsWithSharp = new ArrayList<>(terminators);
terminatorsWithSharp.add("#");
int length = terminatorsWithSharp.size() + 1;
precedenceRelationList = new String[length][length];
for (int line = 0; line < length; line++) {
for (int column = 0; column < length; column++) {
// (0, 0) 位置空出来
if (line == 0 && column == 0) {
precedenceRelationList[line][column] = "-";
continue;
}
if (line == 0 && line < terminatorsWithSharp.size()) {
precedenceRelationList[line][column] = terminatorsWithSharp.get(column - 1);
} else if (column == 0 && column < terminatorsWithSharp.size()) {
precedenceRelationList[line][column] = terminatorsWithSharp.get(line - 1);
}
}
}
}
/**
* 构造优先关系表
* */
private void constructPrecedenceRelationList () {
// 初始化优先关系表
initializePrecedenceRelationList();
//构造优先关系表
constructList();
}
private void constructList () {
// 带#号的终结符符号集
var terminatorsWithSharp = new ArrayList<>(terminators);
terminatorsWithSharp.add("#");
// 带#的语法
var grammarWithSharp = new HashMap<>(grammar);
grammarWithSharp.put("J", List.of("#" + startTerminator + "#"));
for (var i : grammarWithSharp.entrySet()) {
// 获取第一个句型的产生式
var generateExpressions = i.getValue();
// for循环遍历每一个候选式子
for (var generateExpression : generateExpressions) {
// 计算产生式的长度, 如果不为1, 则分析, 否则直接到下一个产生式
if (!(generateExpression.length() <= 1)) {
// 计算等价
calculateEquality(generateExpression, terminatorsWithSharp);
// 计算小于
calculateLess(generateExpression, terminatorsWithSharp);
//计算大于
calculateGreater(generateExpression, terminatorsWithSharp);
}
}
}
}
/**
* 计算优先关系表中的等价关系
* @param generateExpression 待判断的产生式
* @param terminatorsWithSharp 带有#的终结符集合
* */
private void calculateEquality(String generateExpression, ArrayList<String> terminatorsWithSharp) {
// 长度为2
if (generateExpression.length() == 2) {
for (int j = 0; j < generateExpression.length() - 1; j++) {
// 判断 P -> ...ab...
P_ab_(generateExpression, terminatorsWithSharp);
}
}
// 产生式长度大于2 即3以上
else {
for (int j = 0; j < generateExpression.length() - 1; j++) {
// 判断 P -> ...ab...
P_ab_(generateExpression, terminatorsWithSharp);
// 判断 P -> ...aAb...
P_aQb_(generateExpression, terminatorsWithSharp);
}
}
}
/**
* 计算优先关系表中的低等关系
* @param generateExpression 待判断的产生式
* @param terminatorsWithSharp 带有#的终结符集合
* */
private void calculateLess(String generateExpression, ArrayList<String> terminatorsWithSharp) {
for (int i = 0; i < generateExpression.length() - 1; i++) {
// 判断 P -> ...aR...
// 取第一个
String a = generateExpression.substring(i, i + 1);
// 取第二个
String R = generateExpression.substring(i + 1, i + 2);
// 是否满足 P -> ...aR...
// 即 a 是终结符, R 是非终结符
boolean aIsTerminator = terminatorsWithSharp.stream().anyMatch(t -> t.equals(a));
boolean RIsNonTerminator = nonTerminators.stream().anyMatch(t -> t.equals(R));
if (aIsTerminator && RIsNonTerminator) {
// a < firstVt(R)
var firstVtR = firstTerminators.get(R);
// 遍历将对应位置 置为小于
for (var eInFirstVtR : firstVtR) {
less(a, eInFirstVtR);
}
}
}
}
/**
* 计算优先关系表中的优先关系
* @param generateExpression 待判断的产生式
* @param terminatorsWithSharp 带有#的终结符集合
* */
private void calculateGreater(String generateExpression, ArrayList<String> terminatorsWithSharp) {
for (int i = 0; i < generateExpression.length() - 1; i++) {
// 判断 P -> ...Rb...
// 取第一个
String R = generateExpression.substring(i, i + 1);
// 取第二个
String b = generateExpression.substring(i + 1, i + 2);
// 是否满足 P -> ...Rb...
// 即 R 是非终结符, b 是终结符
boolean RIsNonTerminator = nonTerminators.stream().anyMatch(t -> t.equals(R));
boolean bIsTerminator = terminatorsWithSharp.stream().anyMatch(t -> t.equals(b));
if (RIsNonTerminator && bIsTerminator) {
// 满足
// lastVt(R) > b
var lastVtR = lastTerminators.get(R);
// 遍历将对应位置 置为大于
for (var eInLastVtR : lastVtR) {
greater(eInLastVtR, b);
}
}
}
}
/**
* 将优先关系表中的 a b 的关系变为 等价
* @param a 列
* @param b 行
* */
private void equal (String a, String b) {
operatePrecedenceRelationList(a, b, (x, y) -> {
precedenceRelationList[x][y] = "=";
return true;
});
}
/**
* 将优先关系表中的 a b 的关系变为 小于
* @param a 列
* @param b 行
* */
private void less (String a, String b) {
operatePrecedenceRelationList(a, b, (x, y) -> {
precedenceRelationList[x][y] = "<";
return true;
});
}
/**
* 将优先关系表中的 a b 的关系变为 大于
* @param a 列
* @param b 行
* */
private void greater (String a, String b) {
operatePrecedenceRelationList(a, b, (x, y) -> {
precedenceRelationList[x][y] = ">";
return true;
});
}
/**
* 将优先关系表中的 a b 关系变为 {@code sign}
* @param a 列
* @param b 行
* @param function 自定义的赋值函数
* */
private boolean operatePrecedenceRelationList(String a, String b, BiFunction<Integer, Integer, Boolean> function) {
int x = 0;
int y = 0;
for (int line = 1; line < precedenceRelationList.length; line++) {
if (precedenceRelationList[line][0].equals(a)) {
x = line;
}
}
for (int column = 1; column < precedenceRelationList.length; column++) {
if (precedenceRelationList[0][column].equals(b)) {
y = column;
}
}
if (x == 0 && y == 0) {
throw new RuntimeException("小于错误");
} else {
return function.apply(x, y);
// precedenceRelationList[x][y] = "sign"
}
}
/**
* 用于判断 P -> ...ab...
* @param generateExpression 待判断的产生式
* @param terminatorsWithSharp 带有#的终结符集合
* */
private void P_ab_ (String generateExpression, List<String> terminatorsWithSharp) {
for (int j = 0; j < generateExpression.length() - 1; j++) {
// 取第一个符
String a = generateExpression.substring(j, j + 1);
// 取第二个
String b = generateExpression.substring(j + 1, j + 2);
// 是否满足 P -> ...ab...
// 即 a 和 b 都是终结符
boolean aIsTerminator = terminatorsWithSharp.stream().anyMatch(t -> t.equals(a));
boolean bIsTerminator = terminatorsWithSharp.stream().anyMatch(t -> t.equals(b));
if (aIsTerminator && bIsTerminator) {
// 满足说明 a 等价与 b
equal(a, b);
}
}
}
/**
* 用于判断 P -> ...aQb...
* @param generateExpression 待判断的产生式
* @param terminatorsWithSharp 带有#的终结符集合
* */
private void P_aQb_ (String generateExpression, List<String> terminatorsWithSharp) {
for (int j = 0; j < generateExpression.length() - 2; j++) {
// 取第一个符
String a = generateExpression.substring(j, j + 1);
// 取第二个符
String Q = generateExpression.substring(j + 1, j + 2);
// 取第三个符
String b = generateExpression.substring(j + 2, j + 3);
// 是否满足 P -> ...aQb...
// 即 a 和 b 都是终结符, Q是非终结符
boolean aIsTerminator = terminatorsWithSharp.stream().anyMatch(t -> t.equals(a));
boolean QIsNonTerminator = nonTerminators.stream().anyMatch(t -> t.equals(Q));
boolean bIsTerminator = terminatorsWithSharp.stream().anyMatch(t -> t.equals(b));
// 判断是否满足
if (aIsTerminator && QIsNonTerminator && bIsTerminator) {
// 满足说明 a 等价与 b
equal(a, b);
}
}
}
/**
* 排序, 根据值的长度排序, 按照值的长度从大到小排序
* @return 排好序的链表
*/
private List<Map.Entry<String, List<String>>> sort (Map<String, List<String>> firstOrLastTerminators) {
var entryArrayList = new ArrayList<>(firstOrLastTerminators.entrySet());
entryArrayList.sort((o1, o2) -> o2.getValue().size() - o1.getValue().size());
return entryArrayList;
}
/**
* 判断是不是终结符
* @param c 需要判断的符号
* @return 判断结果
* */
private boolean isTerminator (String c) {
return terminators.stream().anyMatch(terminator -> terminator.equals(c));
}
/**
* 判断是不是非终结符
* @param c 需要判断的符号
* @return 判断结果
* */
private boolean isNonTerminator (String c) {
return nonTerminators.stream().anyMatch(nonTerminator -> nonTerminator.equals(c));
}
/**
* 构造非终结符
* */
private void constructNonTerminator(Grammar grammar) {
for (var i : grammar.grammar.entrySet()) {
nonTerminators.add(i.getKey());
}
nonTerminators = nonTerminators.stream().distinct().collect(Collectors.toList());
}
/**
* 构造终结符, 除大写字母以外的字符都是终结符
* */
private void constructTerminator(Grammar grammar) {
for (var i : grammar.grammar.entrySet()) {
for (var v : i.getValue()) {
for (int index = 0; index < v.length(); index++) {
if (v.substring(index, index + 1).matches("[^A-Z]|")) {
terminators.add(v.substring(index, index + 1));
}
}
}
}
terminators = terminators.stream().distinct().collect(Collectors.toList());
}
/**
* 构造 firstVt 集合
* */
private void constructFirstTerminator() {
// 求出来的firstVt集合
Map<String, List<String>> firstTerminators = this.firstTerminators;
List<String> nonTerminators = this.nonTerminators;
// 初始化firstVt集合
for (var i : nonTerminators) {
firstTerminators.put(i, new ArrayList<>());
}
// 记录是否完成
boolean isFinished = false;
// 集合表示对应的非终结符是否求出了firstVt集合, 求出后对应的元素置为true
Map<String, Boolean> flags = new HashMap<>(8);
// 初始化集合, 表示开始时所有的非终结符的firstVt集合没有求出, 所有默认是false
for (var i : firstTerminators.entrySet()) {
flags.put(i.getKey(), false);
}
int index = 0;
while (!isFinished) {
// 记录一个产生式是否计算完了firstVt
boolean isBreak = false;
// index循环
if (index > nonTerminators.size() - 1) {
index = 0;
}
// 获取index位置上的非终结符Vn
String Vn = nonTerminators.get(index);
// 判断Vn对应的flag值, 不为true进行计算, 为true表示计算出来了
if (!flags.get(Vn)) {
// 获取Vn的产生式
List<String> generateExpressions = grammar.get(Vn);
// 逐一进行判断
for (String generateExpression : generateExpressions) {
// P -> a...
// 判断文法产生式是不是以终结符开头，是的话就把该终结符加入 firstVt集合
// a是第一个位置的元素
String a = generateExpression.substring(0, 1);
// 判断 a是不是终结符
if (isTerminator(a)) {
// 是, 即 P 的产生式以终结符开头
// 满足 P -> a.. 把 a 加入 firstVt(P)集合
firstTerminators.get(Vn).add(a);
}
// 如果产生式不是以终结符开头
// 判断 P -> Qa... 成立
// 即 判断文法产生式是不是以 非终结符 终结符 开头，是的话就把该终结符加入 firstVt(P)集合
else {
// Q 是产生式第一个元素
String Q = generateExpression.substring(0, 1);
// a 是产生式第二个元素
// 判断一下是否有第二个元素, 即判断是否越界
try {
a = generateExpression.substring(1, 2);
} catch (Exception e) {
a = "";
}
// 判读 P -> Qa... 成立
boolean pCanGetQa = isNonTerminator(Q) && isTerminator(a);
// 如果 P 的产生式以 Qa开头
if (pCanGetQa) {
// 将 a加入到firstVt(P)中
firstTerminators.get(Vn).add(a);
}
// 匹配第二条件
// 若 a ∈ firstVt(Q) 且 P -> Q... 则 a ∈ firstVt(P)
// 判断 P != Q
if (!Q.equals(Vn)) {
// 判断 P -> Q... 中, Q是非终结符
boolean QisNotTerminator = isNonTerminator(Q);
// 判读 Q 的 firstVt(Q) 是否已经算出来
boolean qFirstVtIsDone = flags.get(Q);
// Q 是 非终结符
if (QisNotTerminator) {
// Q 的 firstVt(Q) 是否已经算出来
if (qFirstVtIsDone) {
// 算出来了
// 将 firstVt(Q) 中的元素加入 firstVt(P)
List<String> firstVtQ = firstTerminators.get(Q);
List<String> firstVtP = firstTerminators.get(Vn);
firstVtP.addAll(firstVtQ);
}
// 没有算出来直接到下一个进行计算
else {
isBreak = true;
break;
}
}
}
}
}
// 没有计算出来就会调到这里
// index++ 后直接下一个产生式扫描
index++;
if (isBreak) {
continue;
}
// 计算出了 firstVt
flags.put(Vn, true);
} else {
index++;
}
// 判断是不是都计算完了firstVt集合
boolean result = true;
for (var flag : flags.entrySet()) {
result = result && flag.getValue();
}
isFinished = result;
}
// 去重
for (var i : firstTerminators.entrySet()) {
i.setValue(i.getValue().stream().distinct().collect(Collectors.toList()));
}
}
/**
* 构造 lastVt 集合
* */
private void constructLastTerminator() {
// 求出来的lastVt集合
Map<String, List<String>> lastTerminators = this.lastTerminators;
List<String> nonTerminators = this.nonTerminators;
// 初始化lastVt集合
for (var i : nonTerminators) {
lastTerminators.put(i, new ArrayList<>());
}
// 记录是否完成
boolean isFinished = false;
// 集合表示对应的非终结符是否求出了firstVt集合, 求出后对应的元素置为true
Map<String, Boolean> flags = new HashMap<>(8);
// 初始化集合, 表示开始时所有的非终结符的firstVt集合没有求出, 所有默认是false
for (var i : lastTerminators.entrySet()) {
flags.put(i.getKey(), false);
}
int index = 0;
while (!isFinished) {
// 记录一个产生式是否计算完了lastVt
boolean isBreak = false;
// index循环
if (index > nonTerminators.size() - 1) {
index = 0;
}
// 获取index位置上的非终结符Vn
String Vn = nonTerminators.get(index);
// 判断Vn对应的flag值, 不为true进行计算, 为true表示计算出来了
if (!flags.get(Vn)) {
// 获取Vn的产生式
List<String> generateExpressions = grammar.get(Vn);
// 逐一进行判断
for (String generateExpression : generateExpressions) {
// P -> ...a
// 判断文法产生式是不是以终结符结尾，是的话就把该终结符加入 lastVt集合
// a是最后一个位置的元素
String a = generateExpression.substring(generateExpression.length() - 1);
// 判断 a是不是终结符
if (isTerminator(a)) {
// 是, 即 P 的产生式以终结符结尾
// 满足 P -> ...a 把 a 加入 lastVt(P)集合
lastTerminators.get(Vn).add(a);
}
// 如果产生式不是以终结符开头
// 判断 P -> ...aQ 成立
// 即 判断文法产生式是不是以 终结符 非终结符 结尾，是的话就把该终结符加入 lastVt(P)集合
else {
// Q 是产生式最后一个元素
String Q = generateExpression.substring(generateExpression.length() - 1);
// a 是产生式倒数第二个元素
// 判断一下是否有倒数第二个元素, 即判断是否越界
try {
a = generateExpression.substring(generateExpression.length() - 2, generateExpression.length() - 1);
} catch (Exception e) {
a = "";
}
// 判读 P -> ...aQ 成立
boolean pCanGetaQ = isNonTerminator(Q) && isTerminator(a);
// 如果 P 的产生式以 aQ 结尾
if (pCanGetaQ) {
// 将 a加入到 lastVt(P)中
lastTerminators.get(Vn).add(a);
}
// 匹配第二条件
// 若 a ∈ lastVt(Q) 且 P -> ...Q 则 a ∈ lastVt(P)
// 判断 P != Q
if (!Q.equals(Vn)) {
// 判断 P -> ...Q中, Q是非终结符
boolean QisNotTerminator = isNonTerminator(Q);
// 判读 Q 的 lastVt(Q) 是否已经算出来
boolean qLastVtIsDone = flags.get(Q);
// Q 是 非终结符
if (QisNotTerminator) {
// Q 的 lastVt(Q) 是否已经算出来
if (qLastVtIsDone) {
// 算出来了
// 将 lastVt(Q) 中的元素加入 lastVt(P)
List<String> lastVtQ = lastTerminators.get(Q);
List<String> lastVtP = lastTerminators.get(Vn);
lastVtP.addAll(lastVtQ);
}
// 没有算出来直接到下一个进行计算
else {
isBreak = true;
break;
}
}
}
}
}
// 没有计算出来就会调到这里
// index++ 后直接下一个产生式扫描
index++;
if (isBreak) {
continue;
}
// 计算出了 lastVt
flags.put(Vn, true);
} else {
index++;
}
// 判断是不是都计算完了lastVt集合
boolean result = true;
for (var flag : flags.entrySet()) {
result = result && flag.getValue();
}
isFinished = result;
}
// 去重
for (var i : lastTerminators.entrySet()) {
i.setValue(i.getValue().stream().distinct().collect(Collectors.toList()));
}
}
/**
* 上课老师讲的分析方法
* @param expression 待分析的产生式
* */
public boolean analyze(String expression) {
System.out.println("带判断的产生式: " + expression);
expression = expression + "#";
int j;
var terminatorsWithSharp = new ArrayList<>(terminators);
terminatorsWithSharp.add("#");
// 读入的字符
String a;
// 指向栈顶元素的指针
int k = 1;
// 用数组模拟栈
String[] S = new String[(int) Math.pow(2, terminators.size())];
S[k] = "#";
// 从 0 开始 逐一读入expression的每一个字符
int index = 0;
do {
// 把下一个输入符号读到a中
a = expression.substring(index, index + 1);
index++;
// 消除 Variable used in lambda expression should be final or effectively final
int finalK = k;
if (terminatorsWithSharp.stream().anyMatch(t -> t.equals(S[finalK]))) {
j = k;
} else {
j = k - 1;
}
while (greatest(S[j], a)) {
String Q;
do {
Q = S[j];
// 消除 Variable used in lambda expression should be final or effectively final
int finalJ = j;
if (terminatorsWithSharp.stream().anyMatch(t -> t.equals(S[finalJ - 1]))) {
j = j - 1;
} else {
j = j - 2;
}
} while (!least(S[j], Q));
String N = stipulationsOfAnAgreement(j + 1, k, S);
k = j + 1;
S[k] = N;
}
if (least(S[j], a) || equality(S[j], a)) {
k = k + 1;
S[k] = a;
} else {
System.out.println("错误, 该文法不是算符优先文法");
return false;
}
} while (!"#".equals(a));
System.out.println("恭喜你，该文法是算符优先文法");
System.out.println("语法树：");
list.forEach(pair -> System.out.println(pair.getFirst() + " -> " + pair.getSecond()));
return true;
}
/**
* 判断 a 和 b 是否是 a > b 的关系
* @param a 列
* @param b 行
* */
private boolean greatest(String a, String b) {
return operatePrecedenceRelationList(a, b, (x, y) -> ">".equals(precedenceRelationList[x][y]));
}
/**
* 判断 a 和 b 是否是 a < b 的关系
* @param a 列
* @param b 行
* */
private boolean least(String a, String b) {
return operatePrecedenceRelationList(a, b, (x, y) -> "<".equals(precedenceRelationList[x][y]));
}
/**
* 判断 a 和 b 是否是 a = b 的关系
* @param a 列
* @param b 行
* */
private boolean equality(String a, String b) {
return operatePrecedenceRelationList(a, b, (x, y) -> "=".equals(precedenceRelationList[x][y]));
}
/**
* 规约
* @param start 规约开始下标
* @param end 规约结束下标
* @param stack 栈
* @return 返回规约后的结果
* */
private String stipulationsOfAnAgreement (int start, int end, String[] stack) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = start; i<= end; i++) {
stringBuilder.append(stack[i]);
}
// 归于到某个非终结符, 默认取第一个
System.out.println("规约串为: " + stringBuilder + "\n归约到: " + nonTerminators.get(0));
list.add(new Pair<>(stringBuilder.toString(), nonTerminators.get(0)));
return nonTerminators.get(0);
}
List<Pair<String, String>> list = new ArrayList<>();
/**
* 判断两个产生式的类型是非终结符
* */
private boolean areNonTerminator(String a, String b) {
return isNonTerminator(a) && isNonTerminator(b);
}
/**
* 计算产生式的值
* */
public int eval (String generateExpression) {
Map<String, Pair<String, String>> result = new TreeMap<>(Comparator.comparingInt(Integer::parseInt));
WordAnalysis.analyseToAllByString(generateExpression, result);
WordAnalysis.printAll();
if (analyze(replaceNumberWithTerminator(generateExpression))) {
String postfix = infixToPostfix(generateExpression);
System.out.println("表达式的值为： " + calculatePostfix(postfix));
System.out.println("\n\n下面是构造形象语法树：");
constructSyntaxTree(replaceNumberWithTerminator(generateExpression));
return calculatePostfix(postfix);
} else {
throw new RuntimeException("该产生式不是算符优先文法");
}
}
private boolean adjustInTwo = false;
/**
* <p>构造语法树</p>
* <p>自底向上构建</p>
* @param inputGenerateExpression 产生式, 对于该产生式构建一棵语法树
*/
public void constructSyntaxTree(String inputGenerateExpression) {
adjustInTwo = false;
Map<Integer, List<Node>> levelMap = new HashMap<>(8);
// 记录次数
int count = 1;
// 将数字替换为终结符
inputGenerateExpression = replaceNumberWithTerminator(inputGenerateExpression);
// 输入的产生式长度
int inputStringLength = inputGenerateExpression.length();
List<Node> nodeList = new ArrayList<>();
String generateExpression;
boolean isFinished = true;
while (isFinished) {
// 第一次进入循环
if (nodeList.size() == 0) {
generateExpression = inputGenerateExpression;
} else {
List<Node> lastLevelNodeList = levelMap.get(count - 1);
if (nodeListIsTheSame(lastLevelNodeList, nodeList)) {
Scanner scanner = new Scanner(System.in);
System.out.print("是否进行手动构建 > ");
String input = scanner.next();
if (input.contains("y") || "S".equals(input) || "s".equals(input)|| "Y".equals(input)) {
count = manualConstruct(levelMap, nodeList, count);
} else {
System.out.println("您选择自动构建, 接下来为您自动构建--------------- ");
count = adjustNodeList(levelMap, nodeList, count);
}
}
levelMap.put(count++, nodeList);
generateExpression = nodeValueToString(nodeList);
nodeList = new ArrayList<>();
}
int length = generateExpression.length();
int maxLength = 0;
// 从产生式开始逐一遍历
for (int index = 0; index < length;) {
int lastIndex = index + 1;
String part = generateExpression.substring(index, lastIndex);
// 找出该产生式的推导式
List<String> partStartExpressions = findStartExpressions(part);
String value = null;
boolean matching = false;
int currentIndex = index;
for (var partStartExpression : partStartExpressions) {
// 获取产生式
var pGenerateExpressions = grammar.get(partStartExpression);
for (var pGenerateExpression : pGenerateExpressions) {
for (int i = lastIndex; i <= length; i++) {
String s = generateExpression.substring(currentIndex, i);
if (s.length() > pGenerateExpression.length()) {
break;
}
if (matchingFirst(pGenerateExpression, s)) {
matching = true;
// 长度判断
if (pGenerateExpression.length() > maxLength) {
maxLength = pGenerateExpression.length();
value = partStartExpression;
part = pGenerateExpression;
index += pGenerateExpression.length();
}
}
}
}
}
if (matching) {
nodeList.add(new Node(List.of(new Node(null, part)), value));
} else {
nodeList.add(new Node(null, part));
index++;
}
maxLength = 0;
}
// 判断终止，如果不能构建语法树，则会进入死循环，用count来判断是否进入死循环
if (count > Math.pow(4, inputStringLength + 1)) {
System.out.println("无法构建该产生式的语法树");
System.out.println("请在运行一次, 使用手动构建语法树");
}
// 判断nodeList是否以开始符号开头
boolean isStartSymbol = nodeList.get(0).getValue().equals(startTerminator);
// 判断nodeList的长度为1
boolean isOne = nodeList.size() == 1;
// 两者满足，结束循环
isFinished = !(isOne && isStartSymbol);
}
// 将最后一次产生的NodeList进行分解，每一个值对应一个节点
List<Node> newNodeList = new ArrayList<>();
Node lastNode = nodeList.get(0).getChild().get(0);
String v = lastNode.getValue();
int length = v.length();
for (int i = 0; i < length; i++) {
String value = v.substring(i, i + 1);
newNodeList.add(new Node(List.of(new Node(null, value)), startTerminator));
}
// 将最后一次产生的NodeList分解后合成的newNodeList加入到层级Map中
levelMap.put(count, newNodeList);
// showLevelMap(levelMap);
root = mapToTree(levelMap);
this.showSyntaxTree(inputGenerateExpression);
}
/**
* 手动构建语法树
* */
private int manualConstruct(Map<Integer, List<Node>> levelMap, List<Node> nodeList, int count) {
int topLevel = levelMap.size();
var current = levelMap.get(topLevel);
var previousCurrent = levelMap.get(topLevel - 1);
var previousPreviousCurrent = levelMap.get(topLevel - 2);
var previousPreviousPreviousCurrent = levelMap.get(topLevel - 3);
String nodeListString = nodeValueToString(nodeList);
String currentString = nodeValueToString(current);
String previousCurrentString = nodeValueToString(previousCurrent);
String previousPreviousCurrentString = nodeValueToString(previousPreviousCurrent);
String previousPreviousPreviousCurrentString = nodeValueToString(previousPreviousPreviousCurrent);
System.out.println("3 > " + previousPreviousPreviousCurrentString + " 孩子节点 : " + nodeChildValueToString(previousPreviousPreviousCurrent));
System.out.println("2 > " + previousPreviousCurrentString + " 孩子节点 : " + nodeChildValueToString(previousPreviousCurrent));
System.out.println("1 > " + previousCurrentString + " 孩子节点 : " + nodeChildValueToString(previousCurrent));
System.out.println("--> " + currentString);
System.out.print("是否对[" + nodeListString + "]进行修改 > ");
Scanner scanner = new Scanner(System.in);
String input = scanner.next();
if (input.contains("y") || "是".equals(input) || "s".equals(input)) {
System.out.print("请输入修改后的内容 > ");
String modify = scanner.next();
System.out.println("已将[" + nodeListString + "]替换为" + modify);
System.out.println("已删除 -> 1 > " + previousCurrentString + " 孩子节点 : " + nodeChildValueToString(previousCurrent));
// 默认情况将 previousPreviousCurrentString 的内容接在 nodeList的后面
// TODO 修改
nodeList.clear();
for (int i = 0; i < modify.length(); i++) {
String value = modify.substring(i, i + 1);
String child = previousPreviousCurrentString.substring(i, i + 1);
nodeList.add(new Node(List.of(new Node(null, child)), value));
}
levelMap.remove(--count);
adjustNodeList(previousPreviousPreviousCurrent, previousPreviousCurrent, nodeList);
return count;
} else {
System.out.println("您放弃修改...");
count = adjustNodeList(levelMap, nodeList, count);
try {
Thread.currentThread().wait(1200);
} catch (Exception ignore) {
return count;
}
}
return count;
}
private String nodeChildValueToString(List<Node> nodeList) {
if (nodeList == null) {
return null;
}
StringBuilder stringBuilder = new StringBuilder();
for (var node : nodeList) {
if (node.getChild() != null) {
for (var child : node.getChild()) {
if (child == null) {
break;
} else {
stringBuilder.append(child.getValue());
}
}
}
}
return stringBuilder.toString();
}
private String replaceNumberWithTerminator(String inputGenerateExpression) {
for (int i = 0; i < inputGenerateExpression.length(); i++) {
if (inputGenerateExpression.substring(i, i + 1).matches("\\d")) {
String s = inputGenerateExpression.substring(i, i + 1);
String terminator = null;
for (var t : terminators) {
if (t.matches("\\w")) {
terminator = t;
break;
}
}
if (terminator != null) {
inputGenerateExpression = inputGenerateExpression.replace(s, terminator);
}
}
}
return inputGenerateExpression;
}
/**
* 打印层级Map
* @param levelMap 层级Map
* */
private void showLevelMap (Map<Integer, List<Node>> levelMap) {
System.out.println("+++++++++++++++++++++++++++++");
for (var s : levelMap.entrySet()) {
System.out.print(s.getKey() + " : ");
for (var k : s.getValue()) {
System.out.print(k.getValue() + " ");
}
System.out.println();
}
System.out.println("+++++++++++++++++++++++++++++");
}
/**
* 调整nodeList
* <pre>
* i + i
* P + P
* F + F (previousPreviousLastLevelNodeList)
* T + T <--- T + T (previousLastLevelNodeList)
* ↓ ↓ ↓ E + E
* E + T <--- E + E (nodeList)
*
* </pre>
*
* */
private void adjustNodeList(List<Node> previousPreviousLastLevelNodeList, List<Node> previousLastLevelNodeList, List<Node> nodeList) {
int length = nodeList.size();
String newValue = previousLastLevelNodeList.get(length - 1).getValue();
int l;
boolean flag = true;
for (l = 2; l < length - 1; l++) {
flag = false;
newValue = previousLastLevelNodeList.get(length - l).getValue();
if (isNonTerminator(newValue)) {
break;
}
}
if (flag) {
l = 1;
}
nodeList.get(length - l).setValue(newValue);
for (int i = 0 ; i < length; i++) {
nodeList.get(i).setChild(
List.of(new Node(null, previousLastLevelNodeList.get(i).getValue()))
);
}
newValue = previousPreviousLastLevelNodeList.get(length - l).getValue();
previousLastLevelNodeList.get(length - l).setValue(newValue);
}
/**
* 调整nodeList
* <pre>
* i + i
* P + P
* F + F (thirdLevel)
* T + T <--- T + T (secondLevel)
* ↓ ↓ ↓ E + E (topLevel)
* E + T <--- E + E (nodeList)
*
* </pre>
*
* */
private int adjustNodeList(Map<Integer, List<Node>> levelMap, List<Node> nodeList, int count) {
List<String> possibleGenerateExpression = findDirectPossible(nodeList);
if (!possibleGenerateExpression.isEmpty()) {
adjustInTwo = true;
return adjust(possibleGenerateExpression, levelMap, nodeList, count);
} else {
List<Node> previousLastLevelNodeList = levelMap.get(count - 2);
List<Node> previousPreviousLastLevelNodeList = levelMap.get(count - 3);
if (previousPreviousLastLevelNodeList == null) {
return count;
}
adjustNodeList(previousPreviousLastLevelNodeList, previousLastLevelNodeList, nodeList);
}
return --count;
}
private int adjust (List<String> possibleGenerateExpression, Map<Integer, List<Node>> levelMap, List<Node> nodeList, int count) {
// count 是 levelMap.size() + 1
for (int i = 0; i < possibleGenerateExpression.size(); i++) {
String value = possibleGenerateExpression.get(0).substring(i, i + 1);
// 不是终结符
if (!isTerminator(value)) {
// 返回寻找到相匹配的
for (var currentLevel : levelMap.entrySet()) {
Node node = currentLevel.getValue().get(i);
if (node.getValue().equals(value)) {
int key = currentLevel.getKey();
for (int j = key + 1; j <= levelMap.size(); j++) {
var list = levelMap.get(j);
list.get(i).setValue(value);
}
}
}
}
}
for (int i = 0; i < nodeList.size(); i++) {
String value = possibleGenerateExpression.get(0).substring(i, i + 1);
nodeList.get(i).setChild(List.of(new Node(null, nodeList.get(i).getValue())));
nodeList.get(i).setValue(value);
}
for (int i = 0; i < nodeList.size(); i++) {
List<Node> nodes = levelMap.get(levelMap.size() - 1);
nodeList.get(i).setChild(List.of(new Node(null, nodes.get(i).getValue())));
}
levelMap.remove(levelMap.size());
count--;
return count;
}
/**
* 寻找可能的推导式
* @param nodeList 产生式
* @return 可能的开始式
* */
private List<String> findDirectPossible(List<Node> nodeList) {
StringBuilder stringBuilder = new StringBuilder();
for (var node : nodeList) {
stringBuilder.append(node.getValue());
}
// 拿到nodeList的产生式
String generateExpression = stringBuilder.toString();
// 匹配到的个数
int matchingCount = 0;
// 最高匹配个数的产生式 possibleGenerateExpressions
List<String> possibleGenerateExpressions = new ArrayList<>();
// 遍历全部产生式, 看看哪个相似度最高
for (var generateExpressions : grammar.entrySet()) {
for (var normalizedGenerateExpression : generateExpressions.getValue()) {
// 长度一样, 匹配字符
if (normalizedGenerateExpression.length() == generateExpression.length()) {
int particularCount = 0;
for (int i = 0; i < normalizedGenerateExpression.length(); i++) {
String nChar = normalizedGenerateExpression.substring(i, i + 1);
String gChar = generateExpression.substring(i, i + 1);
// 终结符一样
if (isTerminator(nChar) && isTerminator(gChar)) {
if (nChar.equals(gChar)) {
possibleGenerateExpressions.add(normalizedGenerateExpression);
} else {
particularCount = 0;
break;
}
} else
if (nChar.equals(gChar)) {
particularCount++;
}
}
// 相似匹配完成
// 相等也加入进来
if (particularCount >= matchingCount && particularCount != 0) {
matchingCount = particularCount;
possibleGenerateExpressions.add(normalizedGenerateExpression);
}
}
}
}
return possibleGenerateExpressions;
}
/**
* 检查两个NodeList是否一样
* @param nodeList 待检查的nodeList
* @param lastLevelNodeList 待检查的nodeList
* @return 检查结果
* */
private boolean nodeListIsTheSame(List<Node> lastLevelNodeList, List<Node> nodeList) {
if (lastLevelNodeList == null) {
return false;
}
if (lastLevelNodeList.size() == nodeList.size()) {
for (int i = 0; i < lastLevelNodeList.size(); i++) {
Node n1 = lastLevelNodeList.get(i);
Node n2 = nodeList.get(i);
if (!n1.getValue().equals(n2.getValue())) {
return false;
}
}
return true;
}
return false;
}
/**
* 将层级Map变为语法树
* @param levelMap 层级Map
* @return 语法树根节点
* */
private Node mapToTree(Map<Integer, List<Node>> levelMap) {
Node root = new Node(startTerminator);
// 得到节点的所有孩子节点值
List<String> childString = new ArrayList<>();
// 上一层的孩子值
List<Node> lastNodeList = null;
for (int i = levelMap.size(); i > 0; i--) {
var nodeList = levelMap.get(i);
if (i == levelMap.size()) {
List<Node> childList = new ArrayList<>();
for (var v : nodeList) {
childList.add(v.getChild().get(0));
}
root.setChild(childList);
lastNodeList = childList;
} else {
for (var s : childString) {
for (var node : nodeList) {
if (s.equals(node.getValue())) {
for (var lastNode : lastNodeList) {
if (lastNode.getValue().equals(s)) {
if (node.getChild() == null) {
lastNode.setChild(List.of(new Node(List.of(new Node(null, s)), s)));
} else {
var list = node.getChild();
List<Node> newNodeList = new ArrayList<>();
String v = list.get(0).getValue();
int length = v.length();
for (int j = 0; j < length; j++) {
String value = v.substring(j, j + 1);
newNodeList.add(new Node(null, value));
};
if (newNodeList.isEmpty()) {
lastNode.setChild(list);
} else {
String string = nodeValueToString(lastNode.getChild());
if (string != null) {
if (!string.equals(nodeValueToString(newNodeList))) {
Scanner scanner = new Scanner(System.in);
System.out.println("lastNode: " + lastNode.getValue());
System.out.print("是否将[" + string + "]替换为[" + nodeValueToString(newNodeList) + "] > ");
String input = scanner.next();
if ("y".equals(input) || "s".equals(input) || "S".equals(input) || "Y".equals(input)) {
lastNode.setChild(newNodeList);
}
}
} else {
lastNode.setChild(newNodeList);
}
}
}
}
}
}
}
}
getLastNodeList(root);
lastNodeList = new ArrayList<>(totalLastNodeList);
totalLastNodeList.clear();
}
childString.clear();
for (var node : nodeList) {
if (node.getChild() != null) {
for (var v : node.getChild()) {
int l = v.getValue().length();
if (l != 1) {
for (int s = 0; s < l; s++) {
childString.add(v.getValue().substring(s, s + 1));
}
} else {
childString.add(v.getValue());
}
}
} else {
childString.add(node.getValue());
}
}
}
root = root.distinct();
return root;
}
List<Node> totalLastNodeList = new ArrayList<>();
/**
* 返回最新的叶子结点
* */
private void getLastNodeList(Node root) {
if (root.getChild() == null) {
totalLastNodeList.add(root);
} else {
for (var node : root.getChild()) {
getLastNodeList(node);
}
}
}
/**
* 将节点链表中的当前节点值归一为字符串
* @param nodeList 节点链表
* @return 归一后的字符串
* */
private String nodeValueToString(List<Node> nodeList) {
if (nodeList == null) {
return null;
}
StringBuilder stringBuilder = new StringBuilder();
for (var n : nodeList) {
stringBuilder.append(n.getValue());
}
return stringBuilder.toString();
}
private List<String> findStartExpressions(String part) {
List<String> partStartExpressions = new ArrayList<>();
for (var generateExpressions : grammar.entrySet()) {
for (var item : generateExpressions.getValue()) {
// 记录是否part中的字符都在item中
boolean allMatching = true;
// 循环逐一匹配part的字符是否与item字符匹配
for (int i = 0; i < part.length(); i++) {
String pChar = part.substring(i, i + 1);
String iChar = item.substring(i, i + 1);
if (!pChar.equals(iChar)) {
allMatching = false;
break;
}
}
// 匹配
if (allMatching) {
// 把推导式放入数组
partStartExpressions.add(generateExpressions.getKey());
}
}
}
return partStartExpressions;
}
private boolean matchingFirst (String partStartExpression, String part) {
// 长度不一样, 直接不匹配
if (partStartExpression.length() != part.length()) {
return false;
}
// 循环逐一匹配part的字符是否与item字符匹配
for (int i = 0; i < part.length(); i++) {
String pChar = part.substring(i, i + 1);
String seChar = partStartExpression.substring(i, i + 1);
if (!pChar.equals(seChar)) {
return false;
}
}
return true;
}
/**
* 输出语法树
* */
public void showSyntaxTree(String inputGenerateExpression) {
System.out.println(inputGenerateExpression + " 的语法树:");
var list = root.show();
list.forEach(System.out::println);
}
/**
* 计算后缀表达式的值
* @param exp 后缀表达式
* @return 计算出来的值
*/
private int calculatePostfix(String exp){
Stack<Integer> stack = new Stack<>();
int length = exp.length();
int index = 0;
while(index < length){
switch (exp.charAt(index)) {
case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' -> stack.push((int) exp.charAt(index) - 48);
case '+' -> {
int a = stack.pop();
int b = stack.pop();
stack.push(a + b);
}
case '-' -> {
int c = stack.pop();
int d = stack.pop();
stack.push(d - c);
}
case '*' -> {
int e = stack.pop();
int f = stack.pop();
stack.push(e * f);
}
case '/' -> {
int g = stack.pop();
int h = stack.pop();
stack.push(h / g);
}
}
index++;
}
return stack.pop();
}
/**
* 中缀转后缀
* @param exp 中缀表达式
* @return 后缀表达式
*/
private String infixToPostfix (String exp) {
Stack<Character> stack = new Stack<>();
StringBuilder suffix = new StringBuilder();
int index = 0;
int length = exp.length();
while(index < length){
switch (exp.charAt(index)) {
case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' -> suffix.append(exp.charAt(index));
case '*', '/', '(' -> stack.push(exp.charAt(index));
// 碰到'+''-'，将栈中所有运算符弹出，送到输出队列中
case '+', '-' -> {
while (stack.size() != 0) {
char temp = stack.pop();
if (temp == '(') {
stack.push('(');
break;
}
suffix.append(temp);
}
stack.push(exp.charAt(index));
}
case ')' -> {
while (!stack.isEmpty() && stack.peek() != '(') {
suffix.append(stack.pop());
}
stack.pop();
}
}
index++;
}
while(!stack.isEmpty()){
suffix.append(stack.pop());
}
return suffix.toString();
}
}
测试用例
package main.experiment2;
import java.util.List;
/**
* @author Administrator
*/
public class Test {
public static void main(String[] args) {
Grammar grammar = new Grammar(
List.of("E", "T", "F", "P"),
List.of(
List.of("E+T", "T"),
List.of("T*F", "F"),
List.of("P↑F", "P"),
List.of("(E)", "i")
)
);
grammar.showGrammar();
grammar.showNonTerminator();
grammar.showTerminator();
grammar.showFirstTerminators();
grammar.showLastTerminators();
grammar.showPrecedenceRelationList();
System.out.println("结果为" + grammar.eval("6*(5+4)"));
}
private static void test1 () {
Grammar grammar = new Grammar(
List.of("E", "T", "F", "P"),
List.of(
List.of("E+T", "T"),
List.of("T*F", "F"),
List.of("P↑F", "P"),
List.of("(E)", "i")
)
);
grammar.showGrammar();
grammar.showNonTerminator();
grammar.showTerminator();
grammar.showFirstTerminators();
grammar.showLastTerminators();
grammar.showPrecedenceRelationList();
System.out.println("结果为" + grammar.eval("6*3"));
// grammar.constructSyntaxTree("2*3");
// grammar.constructSyntaxTree("i+i");
// grammar.constructSyntaxTree("F+F");
// grammar.constructSyntaxTree("T+T*F+i");
// grammar.constructSyntaxTree("i+(i*i)");
// grammar.constructSyntaxTree("i*(i+i)");
}
private static void test2 () {
Grammar grammar = new Grammar(
List.of("S", "A"),
List.of(
List.of("*A"),
List.of("0A1", "*")
)
);
grammar.showGrammar();
grammar.showNonTerminator();
grammar.showTerminator();
grammar.showFirstTerminators();
grammar.showLastTerminators();
grammar.showPrecedenceRelationList();
}
private static void test3 () {
Grammar grammar = new Grammar(
List.of("Z", "A", "B"),
List.of(
List.of("A()"),
List.of("(", "Ai", "B)"),
List.of("i")
)
);
grammar.showGrammar();
grammar.showNonTerminator();
grammar.showTerminator();
grammar.showFirstTerminators();
grammar.showLastTerminators();
grammar.showPrecedenceRelationList();
}
private static void test4 () {
Grammar grammar = new Grammar(
List.of("S", "T"),
List.of(
List.of("a", "b", "(T)"),
List.of("TdS", "S")
)
);
grammar.showGrammar();
grammar.showNonTerminator();
grammar.showTerminator();
grammar.showFirstTerminators();
grammar.showLastTerminators();
grammar.showPrecedenceRelationList();
grammar.constructSyntaxTree("(Sd(T)db)");
}
}
Node类
package main.experiment2;
import lombok.*;
import java.util.ArrayList;
import java.util.List;
/**
* @author Diminish
* @date 2022/4/17 8:23
*/
@Getter
@Setter
@With
@AllArgsConstructor
@Builder
@NoArgsConstructor
public class Node {
private List<Node> child = new ArrayList<>();
private String value;
public Node distinct() {
_distinct(this);
_distinct(this);
_distinct(this);
return this;
}
private void _distinct (Node node) {
if (!(node.getChild() == null)) {
try {
if (!node.value.matches("[A-Z]")) {
node.child = null;
} else {
// 只有一个孩子
boolean isOneChild = node.getChild().size() == 1;
// 孩子节点的值和本节点的值一样
boolean theSameValue = node.getChild().get(0).getValue().equals(node.value);
if (isOneChild && theSameValue) {
node.setChild(node.getChild().get(0).getChild());
}
for (var n : node.getChild()) {
_distinct(n);
}
}
} catch (Exception ignored) {
}
}
}
public Node(String value) {
this.value = value;
}
public boolean isSame (Node node) {
return this.value.equals(node.value);
}
/**
* 遍历语法树
* */
public List<List<String>> show() {
Node root = this;
List<List<String>> res = new ArrayList<>();
helper(root, 0, res);
return res;
}
private void helper(Node root, int depth, List<List<String>> res) {
if (root == null) {
return;
}
//判断是否是新的一层
if (depth + 1 > res.size()) {
res.add(new ArrayList<>());
}
res.get(depth).add(root.value);
//处理子节点
if (root.child != null) {
for (Node node : root.child) {
if (node != null) {
helper(node, depth + 1, res);
}
}
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/122794.html
