编译原理实验三——LR(0)语法分析
代码分为五个部分
- 读入文法并进行处理、扩展
- 求项目集规范族
- 构造 DFA
- 构造分析表
- 分析输入串
经过实验梳理了一遍 LR(0) 语法解析的过程,按照书上的顺序实现不是很复杂。
前面的实验都是用 C++ 写的,这次用 Java 写感觉各有千秋,各有方便和不方便的地方,比如 Java 无法 new 泛型定长数组HashMap<Character, String>[]
,C++ 的话直接声明Map<char, string>[]
就能用了。
Google 了一下貌似说就是 Java 不支持。详细解释:
作者:ylxfc 链接:https://www.zhihu.com/question/20928981/answer/39234969
来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
核心的问题在于Java范型和C#范型存在根本区别:Java的范型停留在编译这一层,到了运行时,这些范型的信息其实是被抹掉的;而C#的范型做到了MSIL这一层。Java的做法不必修改JVM,减少了潜在的大幅改动和随之而来的风险,也许同时也反映出Java Bytecode规范在设计之初的先天不足;C#则大刀阔斧,连CLR一起改以支持更彻底的范型,换句话说,在范型这一点上,感觉C#更C++一点。在Java中,Object[]数组可以是任何数组的父类,或者说,任何一个数组都可以向上转型成它在定义时指定元素类型的父类的数组,这个时候如果我们往里面放不同于原始数据类型,但是满足后来使用的父类类型的话,编译不会有问题,但是在运行时会检查加入数组的对象的类型,于是会抛ArrayStoreException
:
String[] strArray = new String[20];
Object[] objArray =strArray;
objArray[0] = new Integer(1); // throws ArrayStoreException at runtime
因为Java的范型会在编译后将类型信息抹掉,这样如果Java允许我们使用类似Map<Integer, String>[] mapArray = new Map<Integer, String>[20];
这样的语句的话,我们在随后的代码中可以把它转型为Object[]
然后往里面放Map<Double, String>
实例。这样做不但编译器不能发现类型错误,就连运行时的数组存储检查对它也无能为力,它能看到的是我们往里面放Map的对象,我们定义的<Integer, String>
在这个时候已经被抹掉了,于是而对它而言,只要是Map,都是合法的。想想看,我们本来定义的是装Map<Integer, String>
的数组,结果我们却可以往里面放任何Map,接下来如果有代码试图按原有的定义去取值,后果是什么不言自明。
主要解析器文件代码放在下面,完整代码在 https://github.com/heart4lor/LR0
Parser.java
import java.util.*;
public class Parser {
// part1.读入文法并进行处理、扩展
private static HashMap<String, ArrayList<Integer>> index = new HashMap<>();
private static Grammar[] grammars = new Grammar[1024];
private static HashSet<Character> terminator = new HashSet<>();
private static HashSet<Character> non_terminator = new HashSet<>();
private static void input() {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入文法的数目:");
int n = scanner.nextInt();
scanner.nextLine();
System.out.println(String.format("请输入%d个文法:", n));
for (int i = 1; i <= n; i++)
{
String line = scanner.nextLine();
grammars[i] = new Grammar(line);
for (char c : (grammars[i].getFirst() + grammars[i].getSecond()).toCharArray())
{
if(Character.isUpperCase(c))
non_terminator.add(c);
else
terminator.add(c);
}
}
terminator.add('#');
String first = grammars[1].getFirst();
grammars[0] = new Grammar(String.format("%s'->%s", first, first)); // 扩展文法
for (int i = 0; i <= n; i++)
{
if(!index.containsKey(grammars[i].getFirst()))
index.put(grammars[i].getFirst(), new ArrayList<>());
index.get(grammars[i].getFirst()).add(i); // 合并文法左部相同的产生式id
}
}
// part2.求项目集规范族
// 求闭包
private static ArrayList<Item> getClosure(Item item) {
ArrayList<Item> items = new ArrayList<>();
Queue<Item> queue = new LinkedList<>();
queue.offer(item);
while(!queue.isEmpty()) { // bfs
Item now = queue.poll();
items.add(now);
int dot = now.getDot();
if(dot >= now.getSecond().length())
continue;
char c = now.getSecond().charAt(dot);
if(Character.isUpperCase(c)) { // 非终结符,继续搜索
String first = String.valueOf(c);
for (int i: index.get(first)) {
Item next = new Item(grammars[i].toString(), 0, i);
if(next.hasNextDot())
queue.offer(next);
}
}
}
return items;
}
public static void main(String[] args) {
input();
Item item0 = new Item(grammars[0].toString(), 0, 0);
ArrayList<ArrayList<Item>> itemsGroup = new ArrayList<>(); // 项目集规范族
itemsGroup.add(getClosure(item0));
// part3.构造DFA
ArrayList<Edge> DFA = new ArrayList<>(); // 初始化DFA
for (int i = 0; i < itemsGroup.size(); i++) { // from
ArrayList<Item> items = itemsGroup.get(i); // 项目集
for (Item now : items) { // 项目
if (now.hasNextDot()) {
char path = now.getSecond().charAt(now.getDot()); // path
ArrayList<Item> nextItems = getClosure(now.nextDot());
int index = itemsGroup.indexOf(nextItems); // to
if (index == -1)
{
index = itemsGroup.size();
itemsGroup.add(nextItems);
}
DFA.add(new Edge(i, index, path));
}
}
}
System.out.println(String.format("\n项目集规范族 %d个:", itemsGroup.size()) + itemsGroup);
System.out.println(String.format("DFA %d条路径:", DFA.size()) + DFA);
// part4.构造分析表
int n = itemsGroup.size();
HashMap<Character, String>[] actionTable = new HashMap[n];
HashMap<Character, Integer>[] gotoTable = new HashMap[n];
for(int i = 0; i < n; i++) {
actionTable[i] = new HashMap<>();
gotoTable[i] = new HashMap<>();
}
actionTable[1].put('#', "acc");
for (Edge edge : DFA) { // DFA中的每一条路径,为非终结符填Goto表,终结符填Action表
char path = edge.getPath();
int from = edge.getFrom();
int to = edge.getTo();
if(Character.isUpperCase(path))
gotoTable[from].put(path, to);
else
actionTable[from].put(path, String.format("S%d", to));
}
for (int i = 0; i < n; i++)
for (Item item : itemsGroup.get(i))
if(!item.hasNextDot() && i != 1)
for (char c : terminator)
actionTable[i].put(c, String.format("r%d", item.getBelong()));
int t_size = terminator.size();
int nt_size = non_terminator.size();
System.out.println("\nLR(0)分析表:");
System.out.print("\taction\t");
for (int i = 1; i < t_size; i++)
System.out.print("\t\t");
System.out.print("goto");
for (int i = 0; i < nt_size; i++)
System.out.print("\t");
System.out.print("\n\t");
for (char c : terminator)
System.out.print(String.format("%-4c\t", c));
for (char c : non_terminator)
System.out.print(String.format("%-4c\t", c));
for (int i = 0; i < n; i++) {
System.out.print(String.format("\n%d\t", i));
for (char c : terminator)
System.out.print(String.format("%-4s\t", actionTable[i].get(c)));
for (char c : non_terminator)
System.out.print(String.format("%-4s\t", gotoTable[i].get(c)));
}
// part5. 分析输入串
Scanner scanner = new Scanner(System.in);
System.out.println("\n请输入要分析的输入串:");
String str = scanner.nextLine();
Stack<Integer> statusStack = new Stack<>();
statusStack.push(0);
Stack<Character> charStack = new Stack<>();
charStack.push('#');
int status = statusStack.peek();
int pos = 0;
int cnt = 1;
System.out.println("步骤\t\t状态栈\t\t\t\t符号栈\t\t\t\t\t输入串\t\taction\t\tgoto");
String action = actionTable[status].get(str.charAt(pos));
while (!action.equals("acc")) {
System.out.print(String.format("%d\t\t%-16s\t%-16s\t%8s\t%8s\t\t", cnt++, statusStack, charStack, str.substring(pos), action));
char a = action.charAt(0);
if(a == 'S') {
status = Integer.parseInt(action.substring(1));
statusStack.push(status);
charStack.push(str.charAt(pos++));
}
else {
int index = Integer.parseInt(action.substring(1));
Grammar grammar = grammars[index];
int len = grammar.getSecond().length();
while(len-- > 0) {
statusStack.pop();
charStack.pop();
}
char c = grammar.getFirst().charAt(0);
charStack.push(c);
status = statusStack.peek();
status = gotoTable[status].get(c);
statusStack.push(status);
System.out.print(status);
}
action = actionTable[status].get(str.charAt(pos));
System.out.println();
if (action == null) {
System.out.print(String.format("%d\t\t%-16s\t%-16s\t%8s\t%8s\t\t", cnt, statusStack, charStack, str.substring(pos), "err"));
return;
}
}
System.out.print(String.format("%d\t\t%-16s\t%-16s\t%8s\t%8s\t\t", cnt, statusStack, charStack, str.substring(pos), action));
}
}
coding代码失效,求新链接
原文链接已更新到github